5. 归并排序
接下来我们来学习归并排序：
其实归并排序的思想我们在之前做题的过程中也用到过，之前文章里我们有讲过一些顺序表和链表相关的习题，合并两个有序链表 还有 合并两个有序数组，解这两道题我们其实就用到了归并的思想。
就拿合并两个有序链表那个题来说，我们是怎么做的：
两个指针分别遍历两个链表，依次取小的尾插，最终就将两个链表合并成一个有序链表（升序）。
这其实就是归并的思想。
基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
1. 递归版本
思路讲解
那归并排序具体要怎么搞呢？（还是以升序举例）
我们上面提到的合并两个有序链表那种题目，虽然用的是归并的思想，但是是不是有一个前提啊，前提就是两个链表原本就是有序的，所以从前往后遍历才能依次取到从大到小的数据。
但是：
如果现在随便给我们一组数据，让我们对它进行归并排序，是不是没法直接搞啊？
我们可以从中间把它分成两个部分，但是这两组数据一定是有序的吗？
🆗，是不是不是有序的啊，就是需要我们排呢。
那应该怎么办？
我们是不是还可以考虑用递归来搞。
现在有一组数据，我们的思路是什么呢？
首先可以从中间把它分为两组，如果这两组数据都变成有序的话，我们是不是就可以对它们进行归并了，归并之后整体不就有序了嘛。
那现在问题来了，如何让它的左右两个区间变得有序？
🆗，让它的两个左右区间有序，是不是又是与原问题类似但规模较小的子问题啊，那我们就可以递归了，递归的主要思想是啥，就是大事化小。
所以呢，我们对它的左右区间再划分，但是左右区间又各划分成两个子区间，是不是还是需要先把子区间变有序，然后才能归并啊。
所以我们可以要进行多次划分，不断分割成子问题，那啥时候结束呢？
当被划分出来的区间只有一个数时，只有一个数，那是不是就可以认为它是一个有序区间了，那我们就可以开始一层一层的往回合并了。
将所有的区间归并完，排序也就完成了。
举个栗子：
大家可以看一下这张图，这就是对一组数据进行归并排序的一个大致过程。
这里呢，也有一个动图大家可以看一下：
复杂度计算
该算法的基本思想我们理解了，我们来计算一下它的复杂度：
来看这张图：
我们对原始数据一直分解，直到分割成不可再分的子问题，大家看如果我们像上面那样一直从正中间分，最后分解完毕是不是可以看成是一棵满二叉树。
那它的高度（层数）我们可以认为是log2N（logN），那每一层我们都要进行合并：
合并其实就是遍历找小尾插。
注意这里我们尾插要放到一个新数组中，因为直接在原数组进行比较尾插有时候会覆盖掉有些有效数据。
所以要借助一个大小为N（数据个数）的数组，即归并排序的空间复杂度是O(N)。
那我们对每一层进行合并，首先遍历找小尾插，那就是O(N)，然后呢我们排完序还是将数据放到原始的数组中，所以还要将尾插到新数组的数据拷贝回原数组，那也可以认为是O(N)，两个O(N)算时间复杂度就还是O(N)。
那每层O(N)，一共logN层，所以该算法时间复杂度是O(N*logN)。
代码实现
那我们接下来就一起来一步一步地去实现一下归并排序的代码：
首先经过上面的分析，我们需要一个额外的数组来辅助我们完成归并排序，所以我们先开辟一个数组：
那接下来我们就可以开始递归去排了，但是呢，这里我们通常回再搞一个子函数出来，因为直接在当前函数递归的话，每次递归是不是都会malloc一次啊，这样就不太行。
子函数的命名通常可以在原函数前面加一个“_”
🆗，那这个子函数呢就专门用来递归进行排序。
首先第一次我们应该把整体所有数据都传过来：
传给子函数_merger进行处理，那根据我们上面的分析，要先将全体数据分为两个区间，当这两个区间有序时，就可以进行归并了，那如何处理两个子区间，是不是直接递归就行了：
当左右两个子区间有序时，我们就可以进行归并了。
但是递归肯定得有结束条件啊，在这个递归分割得过程中，什么就该停止往回归并了啊，是不是区间只剩一个数的时候啊
那当程序执行到352行，左右两个区间的数据就已经有序了，那我们是不是就剩最后一步，归并了。
接下来就来实现一下归并的代码：
那归并就好搞了，遍历两个区间数据，依次取小的尾插至tmp数组，然后再拷贝回原数组。
那归并就完成了。
那最终排好序的数据我们又放回到了原数组，那tmp数组就没用了，但是它是我们malloc开辟的，所以销毁一下：
那到这里，整个归并排序就完成了：
void _merger(int* arr, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; //[begin,mid] [mid+1,end] _merger(arr, begin, mid, tmp); _merger(arr, mid + 1, end, tmp); //归并 int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; int i = begin; //归并，取小的尾插（升序） while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } //循环结束时哪个区间还有剩余数据，就把剩余数据续到后面 while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } //最后把排好数据再拷回原数组（只拷贝当前归并的区间） memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //归并排序 void merger(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _merger(arr, 0, n - 1, tmp); free(tmp); tmp = NULL; }
我们来测试一下：
没问题。
2. 非递归版本
接下来我们再来学习一下归并排序的非递归实现。
思路讲解
那归并排序不用递归，应该怎么实现呢？
首先呢数组还是需要的：
然后，归并排序非递归的实现呢我们也不需要像快排那样借助栈或者其它的什么数据结构，比较好的一种方法呢就是直接搞，怎么搞呢？
现在有这样一组数据，我们说归并的前提是两组数据如果是有序的，那我们就可以直接对它们归并了。
我们递归实现的思想是什么，就是对原始数据进行划分嘛，分割成子问题，一直分一直分，直到区间只剩一个数时，那就可以认为说有序的了，然后两两进行归并。
那现在不用递归，我们是不是可以反过来啊
先把原始数据一个一个分为一组，每组只有一个数据，那就可以认为是有序了，然后从前到后两两进行归并：
那这样一趟过后，再把每两个数看成一组，每组数据是不是也都是有序的了。
那再继续，两个看成一组，两两归并：
那现在每四个是不是可以看成一个有序区间了，那就四个一组再两两归并：
那对于当前这组数据来说，是不是就完成了啊。
所以，我们可以定义一个变量gap，来控制每组数据的个数，让gap依次取1，2，4…。
代码实现
那我们如何用代码控制着去走这个过程呢？
其实最不好搞的就是去控制好每次归并的区间的边界，那我们肯定还是搞一个循环，每次归并两组数据，每组数据的个数我们用gap控制，gap第一次是1
那归并的代码我们上面写过了，可以直接拷贝过来，然后控制边界就行了
那这个边界我们如何修改才是正确的呢？
应该是这样的，我们对照着例子来验证一下对不对：
是对的哦，大家可以自己走一遍。
然后我们是不是应该再加一层循环，让gap变化起来：
然后还需要注意的一点是，我们控制区间的边界改变了，拷贝的边界也应该修改一下
那代码应该是这样的：
//归并排序（非递归） void MergerSortNonR(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap) { //归并 int begin1 = j; int end1 = j + gap - 1; int begin2 = j + gap; int end2 = j + 2 * gap - 1; int i = j; //归并，取小的尾插（升序） while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } //循环结束时哪个区间还有剩余数据，就把剩余数据续到后面 while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } //最后把排好数据再拷回原数组（只拷贝当前归并的区间） memcpy(arr + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; }
测试一下，就拿我们上面分析的那个例子：
哦豁，确实排好了。
我们再测一组，在原数组上再加一个数：
啥也没打印，其实我们的程序已经崩掉了。
我们来调试一下：
其实呢？
是出现了越界的情况。
发现问题
为什么会这样呢？
我们给定第一组数据非常完美，直接就排好了，我们分析过程也没发现什么问题：
但是第二次我们又增加了一个数据
我们再来分析一下：
第一趟是不是就出现越界了。
往原数组拷贝就拷贝了个随机值。
第一趟gap=1，当j等于8时，end2等于j + 2 * gap - 1=9，访问下标为9 的元素就发生越界了。
因为我们是两组两组进行归并的，但是最后到5的时候就剩它自己一组了。你再向后拿一个数跟它进行归并可不就越界了嘛。
解决问题
那接下来我们就分析一下哪些情况下会出现越界，然后进行相应的处理：
我们每次要归并的两组数据的区间是第一组【begin1，end1】和第二组【begin2，end2】。
首先begin1是肯定不会越界的，每次循环我们是j赋给begin1的，j小于n才进入循环的：
所以呢，出现越界无非就这几种情况：
第一组部分越界，即end1越界
如果end1越界的话，哪那begin2，end2必定也都超过了数组的有效范围，即第二组是不存在的。
那只有一组，也就没法进行归并了，所以这种情况直接break就行了。
第一组没有越界，第二组全部越界（即begin2越界了）
那这种情况第二组也是不存在的，直接break
第一组未越界，第二组部分越界（即begin2没有越界但end2越界了）
这时两组都是有数据的，只不过第二组数据少一些罢了，所以这种情况就不能直接break了，我们要休整一下end2的取值，然后对两组数据进行归并。
那end2的取值应该怎么修改，n是数据个数，n-1就是最后一个元素下标，所以让end2等于n-1就行了。
那我们接下来处理一下这几种情况就行了：
最终代码
所以最终的代码是这样的：
//归并排序（非递归） void MergerSortNonR(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap) { //归并 int begin1 = j; int end1 = j + gap - 1; int begin2 = j + gap; int end2 = j + 2 * gap - 1; //判断越界的情况并进行处理 //第一组部分越界 if (end1 >= n) break; //第二组全部越界 if (begin2 >= n) break; //第二组部分越界 if (end2 >= n) end2 = n - 1; int i = j; //归并，取小的尾插（升序） while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } //循环结束时哪个区间还有剩余数据，就把剩余数据续到后面 while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } //最后把排好数据再拷回原数组（只拷贝当前归并的区间） memcpy(arr + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; }
这下我们再来测试刚才的那组数据：
就没问题了。
归并排序特性总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
因为在归并的时候是取小的尾插嘛，那如果有相等的我们取前面的那一个就行了嘛。
6. 计数排序（非比较排序）
那到现在为止：
前面我们学的所有的排序算法，它们都是一大类的，即比较排序，就是我们在排序的过程中都对数据进行了大小的比较。
那接下来我们还要学习一个非比较排序——计数排序。
当然非比较排序肯定不止这一种，但我们这里重点给大家讲一下这个计数排序，因为计数排序在生活和工作中还是可能应用会比较多一点的，而且在找工作的时候也有可能会被考到。
接下来我们就一起来学习一下：
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。
算法思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
那具体的操作步骤是怎么样的呢？举个例子一起来看一下：
计数排序是这样搞的：
假如现在有这样一个数组待排序：
一共8个数。
对于一组待排序的数据，我们首先要做的是：
统计每个元素出现的次数保存到另一个数组中
那具体要怎么做？
拿这组数据来说，我们可以先找出它的最大值，这里是5，那我们就开辟一个大小为5+1的数组C，这样最后一个下标值正好是5 ，该数组全部初始化为0。
然后，怎么做呢？遍历原数组，原数组的值是几，就让数组C下标为几的元素（初始为0）++，这样遍历一遍过后，数组C存的就是原数组每个元素出现的个数，下标的值就是对应的原数组中的数据。
那统计好次数，下一步怎么做呢？
下面就可以进行排序了，怎么排？
去遍历数组C，下标为0的的值是2，就说明0出现了两次，那就向原数组中（也是从下标为0位置开始），放两个0进去，继续遍历C，下标1位置值是0，就说明原数据没有1，继续向后，下标2的位置值是2，就接着向原数组放两个2…
依次类推，直到遍历完C数组。这时原数组的数据就是排好序之后的：
思考
刚才的例子我们很顺利就排好了，但是呢，还有一些问题值得我们思考一下：
如果待排序的数据大小差别非常大呢？
比如说最小的数据是5，最大的是50000，那我们如果还按上面的思路进行排序的话是不是也得创建一个非常大的数组啊。
那这样空间的耗费是不是就太严重了啊。
所以呢？
计数排序一般适用于范围相对集中的数据。
那除此之外，还有一个问题：
就算数据处的范围比较集中，但是数据都比较大怎么办：
比如是这样的，那我们也要开辟一个大小一百多的数组吗？
是不是也有点不太合适。
思想优化
那这时我们就要想办法优化一下我们的思想了：
怎么优化呢？
刚才我们统计次数其实是用的待排数据的一个绝对映射，什么意思呢？
即待排的数据是几，它的次数就保存在了另一个数组下标为几的位置上。
那现在要优化，我们可以考虑使用数据的相对映射来搞：
什么意思呢？
就拿这组数据来说：
如果还像上面那样的话，我们就得开一个大小为121的数组，因为最大值是120嘛，0到120 就是121个数嘛。
那这样前100个空间是不是都没用上啊。
那现在我们改变一下：
上面这组数据最大值max是120，最小值min是100，所以我们只需开一个大小为（max-min+1）的数组就够了。
那该数组的下标范围就是【0，20】了，如果和上面一样的话100就应该映射到下标为100的位置，那按我们现在的思路100是最小值，就映射到下标为0的位置。
即对于待排数组中的数组arr[i]，就映射到下标为arr[i]-min的位置就行了。
大家再思考一下：
用计数排序如果待排数组中有负数可以吗？
如果用绝对映射是不是不行，假如有个-5，绝对映射的话-5的次数应该存在下标为-5的位置，这不就越界了，数组下标是不能为负的。
但我们现在用相对映射是不是就可以了。
假如有个负数-5，是最小的一个，那它映射到哪个位置，-5-min即-5-(-5)=0，🆗，下标为0的位置，是不是可以啊。
那剩下其它的步骤就还和原来一样了。
那其实这个优化的作用呢就是能少开一些空间。
代码实现
那我们接下来就来实现一下计数排序的代码：
首先第一步是什么：
- 找最大值最小值，确定我们要开的数组大小
大小是max-min+1，我们上面分析过了：
创建用来计数的数组并将全部元素初始化为0
当然这个地方不想手动初始化的话，也可以用calloc，它与malloc的区别就是可以自动将开好的空间初始化为0。
统计个数存入count数组
排序（遍历count数组按个数往原数组放数据）
释放malloc的数组
就写完了：
//计数排序 void CountSort(int* arr, int n) { assert(arr); //找最值 int max = arr[0]; int min = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } int range = max - min + 1; //创建数组 int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range); /*int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { perror("malloc fail"); return; }*/ //统计个数 for (int i = 0; i < n; i++) { count[arr[i] - min]++; } //排序(遍历count数组按个数往原数组放数据） int j = 0; for (int i = 0; i < range; i++) { //count[i]就是每个数据出现的次数 while (count[i]--) { arr[j] = i + min; j++; } } //释放malloc的数组 free(count); count = NULL; }
来测试一下：
来测一组带负数的：
没问题，🆗，那我们的计数排序就完成了。
计数排序特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(N + range)
- 空间复杂度：O(range)
- 稳定性：稳定
7. 性能对比
其实上面讲的这几个算法，我们通过对他们的理解以及时间复杂度就能分辨出来那些算法效率更高。
接下我给出一个程序，让它们对一组大量的相同的数组进行排序，我们打印出它们执行的时间，给大家展示一下（程序的具体实现大家可以不用关心，直接拿去用）：
void TestOP() { srand(time(0)); const int N = 10000; int* a1 = (int*)malloc(sizeof(int) * N); if (a1 == NULL) exit(-1); int* a2 = (int*)malloc(sizeof(int) * N); if (a2 == NULL) exit(-1); int* a3 = (int*)malloc(sizeof(int) * N); if (a3 == NULL) exit(-1); int* a4 = (int*)malloc(sizeof(int) * N); if (a4 == NULL) exit(-1); int* a5 = (int*)malloc(sizeof(int) * N); if (a5 == NULL) exit(-1); int* a6 = (int*)malloc(sizeof(int) * N); if (a6 == NULL) exit(-1); int* a7 = (int*)malloc(sizeof(int) * N); if (a7 == NULL) exit(-1); for (int i = 0; i < N; ++i) { a1[i] = rand(); //a1[i] = rand() + i; a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } int begin1 = clock(); SInsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergerSort(a6, N); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end7 - begin7); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); }
我们来测试一下：
首先第一次10000个数据：
然后我们会分别获取一下，程序运行开始和结束的时间：
最后相减就能得到运行时间，单位是毫秒：
我们来运行一下：
看这个差别就出来了。
再多一点，来10万个：
这次我等的时间就挺长的：
还是10万个，刚才是debug版本下，我们可以换到release下（会对我们的程序进行优化），会快一点：
再增加一点，release下100万个数据，但是像冒泡和直接插入这些比较慢的我们可以把它先屏蔽掉，否则太慢了：
注意：0的那三个屏蔽掉了
🆗，数据越多它们的差距就越明显了。
500万个：
1000万：
快排敢称为“快速排序”确实还是很快的啊。
8. 排序算法复杂度及稳定性分析
9. 源码展示
快排非递归用到的栈
Stack.h
#pragma once #include <stdio.h> #include <stdbool.h> #include <assert.h> #include <stdlib.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int top; int capacity; }ST; //初始化 void StackInit(ST* ps); //销毁 void StackDestroy(ST* ps); //元素压栈 void StackPush(ST* ps, STDatatype x); //元素出栈 void StackPop(ST* ps); //取栈顶元素 STDatatype StackTop(ST* ps); //求栈中元素个数 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" //初始化 void StackInit(ST* ps) { assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); assert(ps->a); ps->capacity = 4; ps->top = 0;//初始化为0，表示指向栈顶元素的下一个 } //销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //元素压栈 void StackPush(ST* ps, STDatatype x) { assert(ps); //如果满了，扩容，扩到原来两倍 if (ps->top == ps->capacity) { STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype)); assert(tmp); ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } //元素出栈 void StackPop(ST* ps) { assert(ps); //栈为空（ps->top==0），就不能再出栈了。 assert(ps->top > 0); ps->top--; } //取栈顶元素 STDatatype StackTop(ST* ps) { assert(ps); //栈为空（ps->top==0），就不能取栈顶元素了。 assert(ps->top > 0); return ps->a[ps->top-1]; } //求栈中元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); //如果ps->top == 0成立，结果为true，表示栈空。 return ps->top == 0; }
sort.h
#pragma once #include <stdio.h> #include <assert.h> #include <string.h> #include <stdlib.h> #include <time.h> //打印数组 void PrintArr(int* arr, int n); //直接插入排序 void SInsertSort(int* arr, int n); //希尔排序 void ShellSort(int* arr, int n); //交换 void swap(int* e1, int* e2); //向下调整（小堆） void AdjustDown(int* arr, int size, int parent); //堆排序（升序） void HeapSort(int* arr, int n); //直接选择排序 void SelectSort(int* arr, int n); //冒泡排序 void BubbleSort(int* arr, int n); //快速排序（递归） void QuickSort(int* arr, int begin, int end); //快速排序（非递归） void QuickSortNonR(int* arr, int begin, int end); //归并排序（递归） void MergerSort(int* arr, int n); //归并排序（非递归） void MergerSortNonR(int* arr, int n); //计数排序 void CountSort(int* arr, int n);
sort.c
#define _CRT_SECURE_NO_WARNINGS #include "sort.h" #include "Stack.h" //打印数组 void PrintArr(int* arr, int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } //直接插入排序 void SInsertSort(int* arr, int len) { for (int i = 0; i < len - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (tmp < arr[end]) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = tmp; } } //希尔排序 void ShellSort(int* arr, int len) { int gap = len; // gap > 1 预排序 // gap == 1 最后一次直接插入排序 while (gap > 1) { //gap /= 2; gap = gap / 3 + 1; for (int i = 0; i < len - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if (tmp < arr[end]) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } } //交换 void swap(int* e1, int* e2) { int tmp = *e1; *e1 = *e2; *e2 = tmp; } //向下调整（大堆） void AdjustDown(int* arr, int size, int parent) { assert(arr); int child = parent * 2 + 1; //没有右孩子，说明是个叶子，循环结束 while (child < size) { //得出较大的那个孩子，有可能有右孩子，但没有左孩子 //所以加上child + 1 < size if (child + 1 < size && arr[child + 1] > arr[child]) { child++; } //如果孩子大于父亲，就交换 if (arr[parent] < arr[child]) { swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } //如果小于孩子，调整结束 else { break; } } } //堆排序 void HeapSort(int* arr, int n) { //建堆：升序大堆，降序小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, n, i); } int count = n - 1; while (count > 0) { swap(&arr[0], &arr[count]); AdjustDown(arr, count, 0); count--; } } //直接选择排序 void SelectSort(int* arr, int n) { assert(arr); int begin = 0; int end = n - 1; while (begin < end) { int maxi = begin; int mini = begin; for (int i = begin+1; i <= end; i++) { if (arr[i] > arr[maxi]) { maxi = i; } if (arr[i] < arr[mini]) { mini = i; } } swap(&arr[mini], &arr[begin]); if (maxi == begin) maxi = mini; swap(&arr[maxi], &arr[end]); begin++; end--; } } //冒泡排序 void BubbleSort(int* arr, int n) { int i = 0; for (i = 0; i < n - 1; i++) { int j = 0; int flag = 0; for (j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); flag = 1; } } // 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理 if (flag == 0) break; } } //三数取中 int GetMidIndex(int* arr, int left, int right) { //int mid = (left + right) / 2; //防止left和right太大溢出 int mid = left + (right - left) / 2; if (arr[mid] > arr[left]) { if (arr[right] > arr[mid]) return mid; else if (arr[left] > arr[right]) return left; else return right; } //arr[mid] < arr[left] else { if (arr[right] < arr[mid]) return mid; else if (arr[left] > arr[right]) return right; else return left; } } //一趟快速排序 [left,right]（hoare版本） int PartSort(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); swap(&arr[mid], &arr[left]); int keyi = left; while (left < right) { //R先走，向左找小 while (left < right && arr[right] >= arr[keyi]) { right--; } //L向右找大 while (left < right && arr[left] <= arr[keyi]) { left++; } if (left < right) swap(&arr[left], &arr[right]); } int meeti = left; swap(&arr[meeti], &arr[keyi]); return meeti; } //一趟快速排序 [left,right]（挖坑法） int PartSort2(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); swap(&arr[mid], &arr[left]); int key = arr[left]; //变量pit标识坑的位置 int pit = left; while (left < right) { //R向左找小于Key的值，填坑 if (left < right && arr[right] >= key) { right--; } arr[pit] = arr[right]; pit = right;//更新坑 //L向右找大于Key的值，填坑 if (left < right && arr[left] <= key) { left++; } arr[pit] = arr[left]; pit = left;//更新坑 } arr[pit] = key; return pit; } //一趟快速排序 [left,right]（前后指针法） int PartSort3(int* arr, int left, int right) { int mid = GetMidIndex(arr, left, right); swap(&arr[mid], &arr[left]); int keyi = left; int prev = keyi; int cur = keyi + 1; while (cur <= right) { /*if (arr[cur] < arr[keyi]) { prev++; swap(&arr[prev], &arr[cur]); }*/ //或 if (arr[cur] < arr[keyi] && ++prev != cur) swap(&arr[prev], &arr[cur]); cur++; } swap(&arr[prev], &arr[keyi]); return prev; } //快速排序[begin,end] void QuickSort(int* arr, int begin, int end) { if (begin >= end) return; if (end - begin <= 8) { // 小区间用直接插入排序，减少递归调用次数 SInsertSort(arr + begin, end - begin + 1); } else { int keyi = PartSort2(arr, begin, end); //[begin,keyi-1] keyi [keyi+1,end] //排keyi左边 QuickSort(arr, begin, keyi - 1); //排keyi右边 QuickSort(arr, keyi + 1, end); } } //快速排序（非递归） void QuickSortNonR(int* arr, int begin, int end) { ST st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { //栈是先进后出，我们取到的顺序是先右后左 int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi = PartSort3(arr, left, right); //[left,keyi-1] keyi [keyi+1,right] if (right > keyi + 1) { StackPush(&st, keyi + 1); StackPush(&st, right); } if (keyi - 1 > left) { StackPush(&st, left); StackPush(&st, keyi - 1); } } StackDestroy(&st); } void _MergerSort(int* arr, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 2; //[begin,mid] [mid+1,end] _MergerSort(arr, begin, mid, tmp); _MergerSort(arr, mid + 1, end, tmp); //归并 int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; int i = begin; //归并，取小的尾插（升序） while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } //循环结束时哪个区间还有剩余数据，就把剩余数据续到后面 while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } //最后把排好数据再拷回原数组（只拷贝当前归并的区间） memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //归并排序（递归） void MergerSort(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergerSort(arr, 0, n - 1, tmp); free(tmp); tmp = NULL; } //归并排序（非递归） void MergerSortNonR(int* arr, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap) { //归并 int begin1 = j; int end1 = j + gap - 1; int begin2 = j + gap; int end2 = j + 2 * gap - 1; //判断越界的情况并进行处理 //第一组部分越界 if (end1 >= n) break; //第二组全部越界 if (begin2 >= n) break; //第二组部分越界 if (end2 >= n) end2 = n - 1; int i = j; //归并，取小的尾插（升序） while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2]) { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } //循环结束时哪个区间还有剩余数据，就把剩余数据续到后面 while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } //最后把排好数据再拷回原数组（只拷贝当前归并的区间） memcpy(arr + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; } //计数排序 void CountSort(int* arr, int n) { assert(arr); //找最值 int max = arr[0]; int min = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } int range = max - min + 1; //创建数组 /*int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range);*/ int* count = (int*)calloc(range, sizeof(int)); if (count == NULL) { perror("malloc fail"); return; } //统计个数 for (int i = 0; i < n; i++) { count[arr[i] - min]++; } //排序(遍历count数组按个数往原数组放数据） int j = 0; for (int i = 0; i < range; i++) { //count[i]就是每个数据出现的次数 while (count[i]--) { arr[j] = i + min; j++; } } //释放malloc的数组 free(count); count = NULL; }
test.c
#define _CRT_SECURE_NO_WARNINGS #include "sort.h" #include "Stack.h" void SInsertSorttest() { int arr[] = { 48,62,35,77,55,14,35,98 }; SInsertSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void ShellSorttest() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; ShellSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void HeapSorttest() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; //int arr[] = { 1,1,1,1,1,1,1,1,1,1 }; HeapSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void SelectSorttest() { //int arr[] = { 34,56,25,65,86,99,72,66 }; int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; SelectSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void BubbleSorttest() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; BubbleSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void QuickSorttest() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1); //QuickSortNonR(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void MergerSorttest() { //int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; int arr[] = { 10,6,7,1,3,9,4,2,5 ,11,-1}; //MergerSort(arr, sizeof(arr) / sizeof(arr[0])); MergerSortNonR(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void CountSorttest() { //int arr[] = { 10,6,7,1,3,9,4,2,5 ,11, }; int arr[] = { -5, 4, 3, -3, -5, -3, -3, 2, 3, 4, 3, 2 }; CountSort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); } void TestOP() { srand(time(0)); const int N = 1000000; int* a1 = (int*)malloc(sizeof(int) * N); if (a1 == NULL) exit(-1); int* a2 = (int*)malloc(sizeof(int) * N); if (a2 == NULL) exit(-1); int* a3 = (int*)malloc(sizeof(int) * N); if (a3 == NULL) exit(-1); int* a4 = (int*)malloc(sizeof(int) * N); if (a4 == NULL) exit(-1); int* a5 = (int*)malloc(sizeof(int) * N); if (a5 == NULL) exit(-1); int* a6 = (int*)malloc(sizeof(int) * N); if (a6 == NULL) exit(-1); int* a7 = (int*)malloc(sizeof(int) * N); if (a7 == NULL) exit(-1); for (int i = 0; i < N; ++i) { a1[i] = rand(); //a1[i] = rand() + i; a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } int begin1 = clock(); //SInsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); //SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergerSort(a6, N); int end6 = clock(); int begin7 = clock(); //BubbleSort(a7, N); int end7 = clock(); printf("SInsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end7 - begin7); printf("QuickSort:%d\n", end5 - begin5); printf("MergerSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { //SInsertSorttest(); //ShellSorttest(); HeapSorttest(); //SelectSorttest(); //BubbleSorttest(); //QuickSorttest(); //MergerSorttest(); //CountSorttest(); //TestOP(); return 0; }
以上就是对一些常见排序算法的讲解，欢迎大家指正！！！
