不修正区间 ：
第一种越界情况，修正区间之后由于后面的数据不归并了，实际上也就是拷贝了原数组的数据到tmp，然后又拷贝回原数组，所以没必要修正， 直接break 掉。
if (end1 >= n) { break; }
第二种越界情况，同第一种，实际上也是拷贝原数组的数据，也可以 break 。
else if (begin2 >= n) { break; }
但是第三种越界情况，就需要修正一下，否则这次归并无法完成，之后的归并也都错误了，让 end2=n−1 。
else if (end2 >= n) { end2 = n - 1;//修正end2边界，以完成数组尾部剩余子数组的归并 //break; }
而这种情况只能边归并边拷贝，因为有些区间是未处理的，如果贸然进行拷贝会把随机值，或者错误数据拷贝进来。
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); • 1
循环内拷贝，不修正区间，归并一部分，拷贝一部分：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int j = i; if (end1 >= n) { break; } else if (begin2 >= n) { break; } else if (end2 >= n) { end2 = n - 1; //break; } while (begin1 <= end1 && begin2 <= end2) { // 保持稳定性 if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) tmp[j++] = a[begin1++]; while (begin2 <= end2) tmp[j++] = a[begin2++]; memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } // 这里不能外部拷贝，因为有些情况是直接 break 出来的，tmp 中不是正确数据 // memcpy(a, tmp, sizeof(int) * n); // 会把错误数据拷入 gap *= 2; } free(tmp); tmp = NULL; }
1.5 特性及复杂度
由于归并排序的数组划分每次都是严格地二分,每次排序子数组划分结构都是稳定的满二叉树(或接近满二叉树)结构，因此归并排序的时间复杂度在各种情况下都不会有变化(不会像快排,希尔排那样由于所处理的序列的逆序数的差异而导致算法时间复杂度有所变化)。然而由于有序序列归并操作需要额外开辟数组来完成,因此归并排序有较大的空间消耗,这是归并排序的一个缺陷
对于归并递归版本，每次都是区间二分，然后开始递归的。所以递归层数是严格logN ，每次递归中时间复杂度为O(N) ，所以总体时间复杂度为O(N*logN) ；对于非递归，gap每次乘 2 ，每次 gap 处理的时间复杂度为 O(N) ，时间复杂度也是 O(N *logN)。
对于归并排序的空间复杂度，递归和非递归有一些计算上的区别，但是结果不影响。
归并排序首先需要一个 tmp 数组，空间复杂度为 O(N) 。如果对于递归，还会开 logN 层栈帧，所以递归版本消耗的总空间大约为O(N+logN) ，当 N 足够大时，logN 省略，所以为 O(N)；对于非递归，那么就仅仅只有tmp 的消耗。
所以综上所述，归并的空间复杂度为 O(N)。
特性：归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度：O(N*logN) 。
空间复杂度：O(N) 。
稳定性：稳定。
2、计数排序
2.1 算法思想
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
计数排序的动图：
计数排序实际上就是将数组中对应数据出现的次数，将数据出现次数映射到一个新数组中。在与数据相等值的下标处，将这个下标位置的元素自增。每出现一个数字就自增一次。
平常的映射就是直接在其相等下标位置处理，叫做 绝对映射 ；还有一种映射方式叫 相对映射
绝对映射：
所谓绝对映射，就是开辟一个辅助数组count ，数组大小为待排序数组的最大元素的大小 max ，然后遍历数组，将数据映射到辅助数组 count 中
然后根据count 数组中的元素，根据元素对应的下标，将下标的值填入 a 数组中，如果 count 数组中该位置为 0 ， 则不需要填。
最后 a 数组中的元素就已经被排序好了。
绝对映射 的缺点：当最大元素很大，或者是出现负数时，就无法映射了。因为空间开大了浪费空间，并且无法在负数下标自增。所以这就引出了 相对映射 。
相对映射：
相对映射是根据数据之间的相对情况来开辟数组大小，并在转换后的相对位置执行映射。
比如有这样一组数据：{328,325,323,321} ，对于这组数据我们开 329 个空间肯定是浪费的。
我们相对映射的思路就是遍历序列，找到序列最大值 max 和最小值 min ，然后开辟max−min+1 个空间，让空间尽可能充分利用。
之后映射自增时，也使用相对位置，这个相对位置就是数组元素减去数组元素的最小值：a[i] - min 。
在最后将元素放到原数组中时，也需要将数组下标加上最小值：i + min 放回去就可以。
通过相对映射，对于元素有负数，和空间浪费的情况都可以解决。（ps：元素有负数的情况，无需特殊处理，因为相对映射的原因，这些步骤都可以正确进行，不信可以试验一下)。
2.2 代码实现
接口实现步骤：
1.找出待排序的数组中最大和最小的元素。
2.统计数组中每个值为 i 的元素出现的次数，存入数组 count 的第 i 项。
3.对所有的计数累加（从 count 中的第一个元素开始，每一项和前一项相加）。
4.反向填充目标数组：将每个元素 i 放在新数组的第 count(i) 项，每放一个元素就将count(i) 减1。
接下来使用相对映射的思路：
// 计数排序 正负数都可以排 void CountSort(int* a, int n) { // 1. 找最小值和最大值 int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } // 2. 根据差值构建 count 数组 int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); exit(-1); } // 初始化 memset(count, 0, sizeof(int) * range); // 3. 将值映射到count数组中 for (int i = 0; i < n; i++) { count[a[i] - min]++; // 映射到相对位置 } int cnt = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[cnt++] = i + min; } } free(count); }
2.3 特性及复杂度
计数排序的时间复杂度其实是由 range 和 N 的关系来衡量的，当我们不确定range和 N 的大小时，我们可以认为 计数排序的时间复杂度取O(max(N,range)) 较大的一个。
空间复杂度则是 O(range)。
实际上通过时空复杂度上看，我们发现计数排序在数据集中的情况下是很强的，能达到几乎 O(N) 的时间复杂度，并且空间复杂度也不会太大。但是对于范围分散，跨度大的序列就不适合，不仅时间没啥优势，空间占比也是个大问题。所以计数排序的适用范围是有限的，如：字符串、浮点数等就不适合
特性：计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
时间复杂度：O(MAX(N,范围)) 。
空间复杂度：O(范围) 。
稳定性：稳定。
3、八大排序算法总结
排序的稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。简单来说，在排相等的两个数时，这两个数不交换，比如遇到 5 5 时，不发生交换。
4、排序性能测试
void TestOP() { srand(time(0)); const int N = 10000000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } // clock 获取程序运行到这块的时间 // end1 - begin1 = 排序时间 // 获取的是毫秒 // 时间过小时，计算不出来 int begin1 = clock(); InsertSort(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(); QuickSortT(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); BubbleSort(a6, N); int end6 = clock(); int begin7 = clock(); MergeSort(a7, N); MergeSortNonR(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("QuickSort:%d\n", end5 - begin5); printf("BubbleSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); }
5.总结：
今天我们认识并具体学习了归并排序和非比较排序中的计数排序，以及对八大排序算法进行了总结，到这里我们的排序算法学习就暂告一段落啦。接下来，我们将开始学习C++的相关知识。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
