C语言分析基础排序算法——归并排序

目录

归并排序

递归版本

非递归版本

非递归版本的问题

归并排序小优化

归并排序

归并排序，分为分治以及合并，分治部分可以使用递归或者非递归完成，归并排序的基本思路是：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

递归版本

递归版本的归并排序思路如下：先将数组分为不可再分割的只有一个数据的部分，再取小的部分进行尾插，每排序一次就将排序好的数据拷贝到原来的数组中

//以下面的数组为例
int data[] = { 10,5,6,9,1,3,4,7 };

void _MergeSort(int* data, int* tmp, int left, int right)
{
    //确定递归结束条件
    if (left == right)
    {
        return;
    }

    //分割数组，首先确定当前数组的中间位置
    int mid = (left + right) / 2;
    _MergeSort(data, tmp, left, mid);
    _MergeSort(data, tmp, mid + 1, right);

    //取小的数值尾插到tmp数组中
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (data[begin1] < data[begin2])
        {
            tmp[i++] = data[begin1++];
        }
        else
        {
            tmp[i++] = data[begin2++];
        }
    }
    //存在一个数组先走完的情况
    while (begin1 <= end1)
    {
        tmp[i++] = data[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[i++] = data[begin2++];
    }

    //排序完之后将tmp数组中的数据拷贝回原来的数组
    memcpy(data + left, tmp + left, sizeof(int) * (right - left + 1));
}

//归并排序递归版
void MergeSort(int* data, int sz)
{
    //因为需要将排序好的数据重新拷贝到原来的数组中，所以需要开辟数组
    int* tmp = (int*)malloc(sizeof(int) * sz);
    assert(tmp);
    //防止主函数递归导致每次都会重新开辟空间，所以使用子函数
    _MergeSort(data, tmp, 0, sz - 1);
    free(tmp);
}

非递归版本

在归并排序中，不使用递归版本时，需要考虑如何对数据进行分堆以及区间的控制，基本思路如下：在循环中，排序间隔为gap的部分数值，再改变gap值，重复前面的步骤，直到最后排序完成。具体思路如下：

//以下面的数组为例
int data[] = { 10,5,6,9,1,3,4,7 };

//归并排序非递归版本
void MergeSort_NotRecursion(int* data, int sz)
{
    //因为需要将排序好的数据重新拷贝到原来的数组中，所以需要开辟数组
    int* tmp = (int*)malloc(sizeof(int) * sz);
    assert(tmp);
    //开始间隔为1
    int gap = 1;
    while (gap < sz)
    {
        //注意i每一次更新为两倍的gap，因为gap只是代表一组有多少个数据，需要i找到下一组
        for (int i = 0; i < sz; i += 2 * gap)
        {
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            int j = begin1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (data[begin1] < data[begin2]) 
                {
                    tmp[j++] = data[begin1++];
                }
                else
                {
                    tmp[j++] = data[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[j++] = data[begin1++];
            }

            while (begin2 <= end2)
            {
                tmp[j++] = data[begin2++];
            }
        }
        memcpy(data, tmp, sizeof(int) * sz);
        gap *= 2;
    }

    free(tmp);
}

非递归版本的问题

但是上面的方法存在一个问题，如果数组的数据不是2的次方个，那么将无法完成排序，存在越界问题

//下面是当数组数据为9个时的越界情况
[0, 0] [1 1]
[2, 2] [3 3]
[4, 4] [5 5]
[6, 6] [7 7]
[8, 8] [9 9]

[0, 1] [2 3]
[4, 5] [6 7]
[8, 9] [10 11]

[0, 3] [4 7]
[8, 11] [12 15]

[0, 7] [8 15]

越界的情况分为三种：

  1. end1、begin2、end2越界，例如[8, 11]、[12, 15]
  2. begin2、end2越界，例如[10, 11]
  3. end2越界，例如[8, 15]

对于上面的问题可以考虑对边界进行修正

第一种解决方法：

  1. 当begin2和end1越界时，跳出循环不进行后方数据的调整
  2. 当end2越界时，修正end2为数组最后一个元素的位置

//归并排序非递归版本
void MergeSort_NotRecursion(int* data, int sz)
{
    //因为需要将排序好的数据重新拷贝到原来的数组中，所以需要开辟数组
    int* tmp = (int*)malloc(sizeof(int) * sz);
    assert(tmp);
    //开始间隔为1
    int gap = 1;
    while (gap < sz)
    {    
        //注意i每一次更新为两倍的gap，因为gap只是代表一组有多少个数据，需要i找到下一组
        for (int i = 0; i < sz; i += 2 * gap)
        {
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            int j = begin1;

            if (begin2 >= sz || end1 >= sz)
            {
                break;
            }

            if (end2 >= sz)
            {
                end2 = sz - 1;
            }

            while (begin1 <= end1 && begin2 <= end2)
            {
                if (data[begin1] < data[begin2]) 
                {
                    tmp[j++] = data[begin1++];
                }
                else
                {
                    tmp[j++] = data[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[j++] = data[begin1++];
            }

            while (begin2 <= end2)
            {
                tmp[j++] = data[begin2++];
            }
            memcpy(data + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }
        gap *= 2;
    }

    free(tmp);
}

第二种解决方法：

直接对所有区间进行修正，将越界的区间修正成左区间大于右区间的不存在区间，此时不存在的区间将不会进入循环，而存在的区间也是有效区间，直接整体拷贝即可

void MergeSort_NotRecursion1(int* data, int sz)
{
    int* tmp = (int*)malloc(sizeof(int) * sz);
    assert(tmp);
    int gap = 1;
    while (gap < sz)
    {
        for (int i = 0; i < sz; i += 2*gap)
        {
            int begin1 = i;
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            int j = i;

            //1. end1 begin2 end2越界
            if (end1 >= sz)
            {
                end1 = sz - 1;
                //修正的不存在区间
                begin2 = sz;
                end2 = sz - 1;
            }
            else if (begin2 >= sz)//2. begin2 end2 越界
            {
                //修正的不存在区间
                begin2 = sz;
                end2 = sz - 1;
            }
            else if(end2 >= sz)//3. end2越界
            {
                end2 = sz - 1;
            }

            while (begin1 <= end1 && begin2 <= end2)
            {
                if (data[begin1] <= data[begin2])//当使用<=时防止出现相等时进行交换，使得排序稳定
                {
                    tmp[j++] = data[begin1++];
                }
                else
                {
                    tmp[j++] = data[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[j++] = data[begin1++];
            }

            while (begin2 <= end2)
            {
                tmp[j++] = data[begin2++];
            }
            
        }
        memcpy(data, tmp, sizeof(int) * sz);
        gap *= 2;
    }

    free(tmp);
}

归并排序小优化

如果数据的个数特别大时，再让数据一直递归到只有一个数据的一层时会导致递归太深从而栈溢出，可以考虑在只有十个数据递归时采用其他排序算法进行优化，此处可以采用直接插入排序，因为每进行一次递归，数据会被分成两部分，所以当递归到只有十个数据时时，数据个数就已经比较小了

💡

这个优化只是在一定程度上有节省，当数据量特别大时，消耗和递归基本上一致

void InsertSort(int* data, int sz)
{
    for (int i = 1; i < sz; i++)
    {
        int tmp = data[i];
        int end = i - 1;
        while (end > 0)
        {
            if (data[end] > tmp)
            {
                data[end + 1] = data[end];
                end--;
            }
            else
            {
                break;
            }
        }
        data[end + 1] = tmp;
    }
}

//归并排序递归版本优化
void _MergeSort_modified(int* data, int* tmp, int left, int right)
{
    //确定递归结束条件
    if (left == right)
    {
        return;
    }

    //小区间优化——直接插入排序
    if ((left - right + 1) < 10)
    {
        InsertSort(data, left - right + 1);
    }

    //分割数组，首先确定当前数组的中间位置
    int mid = (left + right) / 2;
    _MergeSort_modified(data, tmp, left, mid);
    _MergeSort_modified(data, tmp, mid + 1, right);

    //取小的数值尾插到tmp数组中
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (data[begin1] < data[begin2])
        {
            tmp[i++] = data[begin1++];
        }
        else
        {
            tmp[i++] = data[begin2++];
        }
    }
    //存在一个数组先走完的情况
    while (begin1 <= end1)
    {
        tmp[i++] = data[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[i++] = data[begin2++];
    }

    //排序完之后将tmp数组中的数据拷贝回原来的数组
    memcpy(data + left, tmp + left, sizeof(int) * (right - left + 1));
}

//归并排序递归版
void MergeSort_modified(int* data, int sz)
{
    //因为需要将排序好的数据重新拷贝到原来的数组中，所以需要开辟数组
    int* tmp = (int*)malloc(sizeof(int) * sz);
    assert(tmp);
    //防止主函数递归导致每次都会重新开辟空间，所以使用子函数
    _MergeSort_modified(data, tmp, 0, sz - 1);
    free(tmp);
}

归并排序的时间复杂度是，空间复杂度为，归并排序时稳定排序算法

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/455405.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

qiankun：vite/webpack项目配置

qiankun：vite/webpack项目配置

相关博文&#xff1a; https://juejin.cn/post/7216536069285429285?searchId202403091501088BACFF113F980BA3B5F3 https://www.bilibili.com/video/BV12T411q7dq/?spm_id_from333.337.search-card.all.click qiankun结构&#xff1a; 主应用base&#xff1a;vue3historyv…
阅读更多...
基于SpringCache实现数据缓存

基于SpringCache实现数据缓存

SpringCache SpringCache是一个框架实现了基本注解的缓存功能,只需要简单的添加一个EnableCaching 注解就能实现缓存功能 SpringCache框架只是提供了一层抽象,底层可以切换CacheManager接口的不同实现类即使用不同的缓存技术,默认的实现是ConcurrentMapCacheManagerConcurren…
阅读更多...
中间件 | Kafka - [常见问题]

中间件 | Kafka - [常见问题]

INDEX 1 为什么快2 消息丢失2.1 消息丢失位置2.2 如何避免消息丢失 3 顺序消费 1 为什么快 kafka使用的是基于文件的顺序存储 代价是只能通过offset标记消费情况并总 partition 数越高&#xff0c;性能越下降&#xff0c;可降低一个数量级 每个 partition 的消息会保存在一个独…
阅读更多...
C++day3——类中的成员函数

C++day3——类中的成员函数

思维导图&#xff1a; 2、设计一个Per类&#xff0c;类中包含私有成员&#xff1a;姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员&#xff1a;成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数和拷贝构造函数。 #in…
阅读更多...
力扣串题：验证回文串2

力扣串题：验证回文串2

bool judge(char *s,int m,int n){while(m<n){if(s[m]!s[n]){return false;}m,n--;}return true; } bool validPalindrome(char * s){for(int i0,jstrlen(s)-1;i<j;i,j--){if(s[i]!s[j]){return (judge(s,i1,j)||judge(s,i,j-1));}}return true; }这个题直接背大佬代码吧…
阅读更多...
彩虹外链网盘界面UI美化版超级简洁好看

彩虹外链网盘界面UI美化版超级简洁好看

彩虹外链网盘界面UI美化版 彩虹外链网盘&#xff0c;是一款PHP网盘与外链分享程序&#xff0c;支持所有格式文件的上传&#xff0c;可以生成文件外链、图片外链、音乐视频外链&#xff0c;生成外链同时自动生成相应的UBB代码和HTML代码&#xff0c;还可支持文本、图片、音乐、…
阅读更多...
Albumentations——广泛应用于工业界、学术界、AI竞赛和开源项目中的CV数据增强工具

Albumentations——广泛应用于工业界、学术界、AI竞赛和开源项目中的CV数据增强工具

Albumentations: fast and flexible image augmentationsDiscover Albumentations: an open-source library offering efficient and customizable image augmentations to boost machine learning and computer vision model performance.https://albumentations.ai/
阅读更多...
HM v.16.22 顺序读源码day1---encmain.cpp

HM v.16.22 顺序读源码day1---encmain.cpp

文章目录 encmain.cpp引入的库执行主体1. 读取输入的配置文件2. 编码启动和过程计时 实现细节1. cTAppEncTop.parseCfg( argc, argv )&#xff1b;2. df::program_options_lite::ParseFailure;3. EnvVar::printEnvVar();4. EnvVar::printEnvVarInUse();5. printMacroSettings()…
阅读更多...
plt保存PDF矢量文件中嵌入可编辑字体（可illustrator编辑）

plt保存PDF矢量文件中嵌入可编辑字体（可illustrator编辑）

背景&#xff1a; 用默认 plt.savefig() 保存图片&#xff0c;图中文字是以瞄点保存&#xff0c;而不是以文字格式。在编辑矢量图中&#xff0c;无法调整文字大小和字体。 方法&#xff1a; import matplotlib.pyplot as plt import numpy as np# ------输出的图片为illustr…
阅读更多...
RabbitMQ备份交换机与优先级队列

RabbitMQ备份交换机与优先级队列

1. 备份交换机 备份交换机可以理解为 RabbitMQ 中交换机的“备胎”&#xff0c;当我们为某一个交换机声明一个对应的备份交换机时&#xff0c;就是为它创建一个备胎&#xff0c;当交换机接收到一条不可路由消息时&#xff0c;将会把这条消息转发到备份交换机中&#xff0c;由备…
阅读更多...
数据仓库的基本概念、基本特征、体系结构

数据仓库的基本概念、基本特征、体系结构

个人看书学习心得及日常复习思考记录&#xff0c;个人随笔。 数据仓库的基本概念、基本特征 数据仓库的定义&#xff1a;数据仓库是一个面向主题的、集成的、不可更新的、随时间不断变化的数据集合&#xff0c;用以更好地支持企业或组织的决策分析处理。 数据仓库中数据的4个…
阅读更多...
26-Java访问者模式 ( Visitor Pattern )

26-Java访问者模式 ( Visitor Pattern )

Java访问者模式 摘要实现范例 访问者模式&#xff08;Visitor Pattern&#xff09;使用了一个访问者类&#xff0c;它改变了元素类的执行算法&#xff0c;通过这种方式&#xff0c;元素的执行算法可以随着访问者改变而改变访问者模式中&#xff0c;元素对象已接受访问者对象&a…
阅读更多...
Unity2019.2.x 导出apk 安装到安卓Android12+及以上的系统版本 安装出现-108 安装包似乎无效的解决办法

Unity2019.2.x 导出apk 安装到安卓Android12+及以上的系统版本 安装出现-108 安装包似乎无效的解决办法

Unity2019.2.x 导出apk 安装到安卓Android12及以上的系统版本 安装出现-108 安装包似乎无效的解决办法 导出AndroidStudio工程后 需要设置 build.gradle文件 // GENERATED BY UNITY. REMOVE THIS COMMENT TO PREVENT OVERWRITING WHEN EXPORTING AGAINbuildscript {repositor…
阅读更多...
python-0007-django模版

python-0007-django模版

介绍 模版是对js&#xff0c;html等资源的封装 新建 在项目路径下新建模版文件夹templates&#xff08;可以为其他名称&#xff09;&#xff0c;要是想细分业务的话&#xff0c;还可以在templates路径下继续建文件夹。如下图&#xff1a; 注册模版 在项目的settings找到T…
阅读更多...
超越营销：交易性邮件如何塑造现代沟通

超越营销：交易性邮件如何塑造现代沟通

在我们的电子邮件自动化系列文章中&#xff0c;我们继续探讨交易性邮件的重要性。这些邮件对于向收件人传递实时更新和可操作信息至关重要&#xff0c;是企业运营不可或缺的一部分。 运营触点 在现代沟通中&#xff0c;交易性邮件扮演着不可或缺的角色&#xff0c;尤其是在企…
阅读更多...
String类及其常用方法

String类及其常用方法

文章目录 1.String类的特性与使用1.1 String类的特性1.2 String对象的创建方式1.3 String 的使用&#xff08;不同的拼接操作&#xff09; 2.String常用方法2.1 String的常用方法一2.2 String常用方法二2.3 String常用方法三 1.String类的特性与使用 1.1 String类的特性 Stri…
阅读更多...
使用Barrier共享鼠标键盘，通过macos控制ubuntu系统

使用Barrier共享鼠标键盘，通过macos控制ubuntu系统

之前文章写过如何使用barrrier通过windows系统控制ubuntu系统&#xff0c;该文章将详细介绍如何使用barrier通过macos系统控制ubuntu系统 一、macOS安装barrier macOS版本barrier链接 1、双击点开安装包 2、将安装包里的barrier拷贝到macOS的达达->应用程序中 3、在达达…
阅读更多...
Spring启动“--”设置参数没生效

Spring启动“--”设置参数没生效

现象 在idea中启动SpringBoot项目时&#xff0c;使用“--”设置的启动参数没有生效&#xff0c;如修改端口号“--server.port8082” 原因 排查发现是因为在使用SpringApplication.run启动项目时&#xff0c;没有将args参数传入run方法。 修复方案 SpringApplication.run参数中…
阅读更多...
当matplotlib遇见“赛博朋克”

当matplotlib遇见“赛博朋克”

本次分享一个Python可视化工具cyberpunk，轻松让图表变得“赛博朋克”。 案例1 import matplotlib.pyplot as plt import mplcyberpunkplt.style.use("cyberpunk") #调用cyberpunk styleplt.plot([1, 3, 9, 5, 2, 1, 1], marker=o) plt.plot([4, 5, 5, 7, 9, 8, 6…
阅读更多...
Linux系统——Nginx脚本拦截拓展

Linux系统——Nginx脚本拦截拓展

可能会有些无聊的人对服务器的Nginx服务进行恶意访问网站、API接口&#xff0c;会影响到用户的体验&#xff0c;我们可以做一个简单的脚本对恶意访问的IP做一个有效的拦截&#xff0c;揪出这些IP地址&#xff0c;然后将其进行禁用。 在Nginx的conf目录下新建一个blockip.conf文…
阅读更多...
最新文章

Copyright @ 2022~2023