💦 归并排序
🔑 核心思想 🔑
归并排序 (MERGE-SORT) 是建立在归并操作上的一种有效的排序算法，该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序核心步骤：
❗ 动图演示：❕
🧿 实现代码 —— 递归版 ：
void _MergeSort(int* a, int left, int right, int* temp) { //只有一个值 if (left >= right) return; //[left, mid][mid+1, right] int mid = (right + left) / 2; //递归 _MergeSort(a, left, mid, temp); _MergeSort(a, mid + 1, right, temp); //归并到temp int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; //&&其中一段区间结束就结束了 int index = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { temp[index++] = a[begin1++]; } else { temp[index++] = a[begin2++]; } } //begin2结束了，拷贝剩下的begin1 while (begin1 <= end1) { temp[index++] = a[begin1++]; } //begin1结束了，拷贝剩下的begin2 while (begin2 <= end2) { temp[index++] = a[begin2++]; } //归并后的结果，拷贝至原数组 int i = 0; for (i = left; i <= right; i++) { a[i] = temp[i]; } } void MergeSort(int* a, int n) { //临时数组 int* temp = (int*)malloc(sizeof(int) * n); //子函数递归 _MergeSort(a, 0, n - 1, temp); //释放临时数组 free(temp); }
🧿 实现代码 —— 非递归版 ：
🔑 核心思想 🔑
void MergeSortNonR(int* a, int n) { //临时数组 int* temp = (int*)malloc(sizeof(int) * n); int groupNum = 1; int i = 0; while (groupNum < n) { for (i = 0; i < n; i += 2 * groupNum) { //[begin1, end1][begin2, end2] int begin1 = i, end1 = i + groupNum - 1; int begin2 = i + groupNum, end2 = i + groupNum * 2 - 1; //归并 int index = begin1; //数组的数据个数，并不一定是按整数倍，所以分组可能越界或不存在 //1.[begin2,end2]不存在或越界，修正为一个不存在的区间 if (begin2 >= n) { begin2 = n + 1; end2 = n; } //2.end1越界，修正后归并 if (end1 >= n) { end1 = n - 1; } //3.end2越界，修正后归并 if (end2 >= n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { temp[index++] = a[begin1++]; } else { temp[index++] = a[begin2++]; } } //begin2结束了，拷贝剩下的begin1 while (begin1 <= end1) { temp[index++] = a[begin1++]; } //begin1结束了，拷贝剩下的begin2 while (begin2 <= end2) { temp[index++] = a[begin2++]; } } //拷贝回原数组 for (i = 0; i < n; i++) { a[i] = temp[i]; } //迭代 groupNum *= 2; //输出每层 //PrintArray(a, n); } //释放临时数组 free(temp); }
❗ 归并排序的特性总结：❕
1️⃣ 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题
2️⃣ 时间复杂度：O(N*logN)
3️⃣ 空间复杂度：O(N)
4️⃣ 稳定性：稳定
💦 非比较排序
1、计数排序
🔑 核心思想 🔑
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
计数排序核心步骤：
1️⃣ 统计相同元素出现次数
2️⃣ 根据统计的结果将序列回收到原来的序列中
❗ 动图演示：❕
🧿 实现代码 ：
void CountSort(int* a, int n) { //遍厉一遍找出最小值和最大值 int min = a[0], max = a[0]; int i = 0; for (i = 1; i < n; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } //求出这个区间 int range = max - min + 1; //calloc空间，并初始化为0 int* count = (int*)calloc(range, sizeof(int)); //统计 for (i = 0; i < n; i++) { //相对位置 count[a[i] - min]++; } //根据count数组排序 i = 0; int j = 0; for (j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min; } } free(count); }
❗ 计数排序的特性总结：❕
1️⃣ 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限
2️⃣ 时间复杂度：O(MAX(N,范围))
3️⃣ 空间复杂度：O(范围)
4️⃣ 稳定性：稳定
5️⃣ 只适合整数排序，浮点数/字符串不能排
2、基数排序
🔑 核心思想 🔑
基数排序又称桶排序，它分别按数据的个、十、百、千、万 … 排序，当然也可以先万、千、…
❗ 动图演示：❕
❓ 这里就不实现了，为什么 ❔
因为这种排序实际在校招中和现实中已经很少使用了，各位码友有兴趣的也可以自己了解下
💦 文件排序 (拓展)
⚠ 注意
小文件排序是没有意义的，当然我们这里只是模拟，所以给 100 个数据
🔑 核心思想 🔑
磁盘的读取速度相比内存差距非常大，所以我们不可能像在内存中两两归并。正确的归并方法是大文件平均分割成 N 份，保证每份大小都可以加载到内存，那么就可以把每个小文件加载到内存中，使用快排排序，再写回小文件，这时就达到文件中归并的先决条件
🧿 实现代码 ：
void _MergeFile(const char* File1, const char* File2, const char* mFile) { //读文件1 FILE* fout1 = fopen(File1, "r"); if (fout1 == NULL) { printf("打开文件失败\n"); exit(-1); } //读文件2 FILE* fout2 = fopen(File2, "r"); if (fout2 == NULL) { printf("打开文件失败\n"); exit(-1); } //写文件3,把文件1和文件2写到文件3里 FILE* fin = fopen(mFile, "w"); if (fin == NULL) { printf("打开文件失败\n"); exit(-1); } int num1, num2; //对于内存中没有问题，但是磁盘就有问题了。不管num1和num2谁小谁大，只要读了fout1和fout2它们都会往后走 /*while (fscanf(fout1, "%d\n", &num1) != EOF && fscanf(fout2, "%d\n", &num2) != EOF) { if (num1 < num2) fprintf(fin, "%d\n", num1); else fprintf(fin, "%d\n", num2); }*/ int ret1 = fscanf(fout1, "%d\n", &num1); int ret2 = fscanf(fout2, "%d\n", &num2); //下面保证了谁读谁走；fout1和fout2都不为空再比较 while (ret1 != EOF && ret2 != EOF) { if (num1 < num2) { fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d\n", &num1);//更新字符 } else { fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d\n", &num2); //更新字符 } } /*注意这样会导致少写一个数据 //fout2完了，写剩下的fout1 while (fscanf(fout1, "%d\n", &num1) != EOF) { fprintf(fin, "%d\n", num1); } //fout1完了，写剩下的fout2 while (fscanf(fout2, "%d\n", &num2) != EOF) { fprintf(fin, "%d\n", num2); }*/ //fout2完了，写剩下的fout1 while (ret1 != EOF) { fprintf(fin, "%d\n", num1); ret1 = fscanf(fout1, "%d\n", &num1);//更新字符 } //fout1完了，写剩下的fout2 while (ret2 != EOF) { fprintf(fin, "%d\n", num2); ret2 = fscanf(fout2, "%d\n", &num2); //更新字符 } //关闭文件 fclose(fout1); fclose(fout2); fclose(fin); } void MergeSortFile(const char* file) { FILE* fout = fopen(file, "r"); if (fout == NULL) { printf("打开文件失败\n"); exit(-1); } int n = 10; int a[10]; int i = 0; int num = 0; char subfile[20]; int filei = 1; memset(a, 0, sizeof(int) * n); //从fout文件流里读，直至EOF while (fscanf(fout, "%d\n", &num) != EOF) { //每次循环读10个数据放在内存中(if里先放9个，else再放最后一个) if (i < n - 1) { a[i++] = num; } else { a[i] = num; //快排10个数据 QuickSort(a, 0, n - 1); //生成文件名sub_sort1/2/3... sprintf(subfile, "%d", filei++); //写文件，subfile里存储生成的文件名 FILE* fin = fopen(subfile, "w"); if (fin == NULL) { printf("打开文件失败\n"); exit(-1); } //写回小文件 for (int i = 0; i < n; i++) { fprintf(fin, "%d\n", a[i]); } //关闭文件 fclose(fin); //重置i i = 0; memset(a, 0, sizeof(int) * n); } } //互相归并到文件，实现整体有序 char mFile[100] = "12"; char File1[100] = "1"; char File2[100] = "2"; for (i = 2; i <= n; i++) { //读取File1和File2，归并出mFile _MergeFile(File1, File2, mFile); //拷贝迭代File1的文件名12/123/1234... strcpy(File1, mFile); //循环迭代File2的文件名3/4/5... sprintf(File2, "%d", i + 1); //循环迭代mFile的文件名123/1234/12345... sprintf(mFile, "%s%d",mFile, i + 1); } //关闭文件 fclose(fout); }
💦 性能测试
❓ 测试所有排序 && 怎么保证它是公平的 ❔
数组里放的数据都是一样的
//测试排序的性能对比 void TestOP() { srand(time(0)); const int N = 100000; 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); int* a8 = (int*)malloc(sizeof(int) * N); int* a9 = (int*)malloc(sizeof(int) * N); int* a10 = (int*)malloc(sizeof(int) * N); int* a11 = (int*)malloc(sizeof(int) * N); int* a12 = (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]; a8[i] = a1[i]; a9[i] = a1[i]; a10[i] = a1[i]; a11[i] = a1[i]; a12[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin2_1 = clock(); ShellSortPro(a3, N); int end2_1 = clock(); int begin3 = clock(); SelectSort(a4, N); int end3 = clock(); int begin3_1 = clock(); SelectSortPro(a5, N); int end3_1 = clock(); int begin4 = clock(); HeapSort(a6, N); int end4 = clock(); int begin5 = clock(); BubbleSort(a6, N); int end5 = clock(); int begin5_1 = clock(); BubbleSortPro(a7, N); int end5_1 = clock(); int begin6 = clock(); QuickSort(a8, 0, N - 1); int end6 = clock(); int begin6_1 = clock(); QuickSortPro(a9, 0, N - 1); int end6_1 = clock(); int begin6_2 = clock(); QuickSortNonR(a10, 0, N - 1); int end6_2 = clock(); int begin7 = clock(); MergeSort(a11, N); int end7 = clock(); int begin7_1 = clock(); MergeSortNonR(a12, N); int end7_1 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("ShellSortPro:%d\n", end2_1 - begin2_1); printf("SelectSort:%d\n", end3 - begin3); printf("SelectSortPro:%d\n", end3_1 - begin3_1); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end5 - begin5); printf("BubbleSortPro:%d\n", end5_1 - begin5_1); printf("QuickSort:%d\n", end6 - begin6); printf("QuickSortPro:%d\n", end6_1 - begin6_1); printf("QuickSortNonR:%d\n", end6_2 - begin6_2); printf("MergeSort:%d\n", end7 - begin7); printf("MergeSortNonR:%d\n", end7_1 - begin7_1); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); free(a9); free(a10); free(a11); free(a12); }
💨 输出结果 (这里使用 Release 版本 && 10 万个数据)
这里测试 3 次
三、排序算法复杂度及稳定性分析
❗ 稳定性 (比较重要，注意不要死记，要结合思想来看) ❕
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排
序算法是稳定的；否则称为不稳定的。
❓ 稳定性的意义 ❔
假设有一考试，并规定前 6 名发奖状，如果分数相同，则按交卷时间的先后计算名次。此时排序稳定性的意义就有所体现了
四、概念选择题
1、快速排序算法是基于 ( ) 的一个排序算法
A. 分治法
B. 贪心法
C. 递归法
D. 动态规划法
📝 分析：快速排序是一种分治的算法，其次递归不是一种算法
2、对记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表时，为找到插入位置需比较 ( ) 次？（采用从后往前比较）
A. 3
B. 4
C. 5
D. 6
📝 分析：
15 23 38 54 60 72 96 45
所以需要比较 5 次
3、以下排序方式中占用 O(n) 辅助存储空间的是 ( )
A. 简单排序
B. 快速排序
C. 堆排序
D. 归并排序
📝 分析：注意没有简单排序；归并排序的空间复杂度是 O(N)
4、下列排序算法中稳定且时间复杂度为 O(n2) 的是 ( )
A. 快速排序
B. 冒泡排序
C. 直接选择排序
D. 归并排序
📝 分析：
冒泡排序是稳定的算法，且时间复杂度是 O(N2)
直接选择排序是不稳定的，例如：
5 5 1
1 5 5
5、关于排序，下面说法不正确的是 ( )
A. 快排时间复杂度为 O(N*logN)，空间复杂度为 O(logN)
B. 归并排序是一种稳定的排序，堆排序和快排均不稳定
C. 序列基本有序时，快排退化成冒泡排序，直接插入排序最快
D. 归并排序空间复杂度为 O(N)，堆排序空间复杂度的为 O(logN)
📝 分析：堆排序没使用递归，没有辅助空间，所以它的空间复杂度为 O(1)
6、下列排序法中，最坏情况下时间复杂度最小的是 ( )
A. 堆排序
B. 快速排序
C. 希尔排序
D. 冒泡排序
📝 分析：堆排序 (归并) 最坏情况下和最好情况下时间复杂度最小的 —— O(N*lonN)
7、设一组初始记录关键字序列为 (65,56,72,99,86,25,34,66)，则以第一个关键字 65 为基准而得到的第一趟快速排序结果是 ( )
A. 34，56，25，65，86，99，72，66
B. 25，34，56，65，99，86，72，66
C. 34，56，25，65，66，99，86，72
D. 34，56，25，65，99，86，72，66
📝 分析：
我们前面已经了解到快速排序首次单趟的三种方法 —— hoare版本、挖坑版本、前后指针版本，注意在某些情况下需要都考虑到，因为三种版本得到的结果不一定都一样
结合情况此题选择 A 选项
