七、归并排序
归并排序是建立在归并操作上的一种有效的排序算法，采用分治法
1、归并排序
1）递归归并
- 基本思想：
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序
- 核心步骤：
动图展示：
- 实现代码：
//归并排序 void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right)//只有一个元素或没有元素为有序，则返回 return; int mid = (right + left) / 2; _MergeSort(a, left, mid, tmp); _MergeSort(a, mid+1, right, tmp); //左区间和右区间有序后开始归并 int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int p = left;//记录下标 while (begin1<=end1&&begin2<=end2)//归并排序 { if (a[begin1] < a[begin2])//升序 { tmp[p++] = a[begin1++]; } else { tmp[p++] = a[begin2++]; } } while (begin1 <= end1)//剩下部分 { tmp[p++] = a[begin1++]; } while (begin2 <= end2) { tmp[p++] = a[begin2++]; } //拷贝回数组a for (int i = left; i <= right; i++) { a[i] = tmp[i]; } void MergeSort(int* a, int n) { //创建暂存数据数组（保存归并好的数据） int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("nalloc fail\n"); exit(-1); } //归并排序 _MergeSort(a, 0, n - 1, tmp); //释放 free(tmp); tmp = NULL; }
- 归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
2）非递归归并
- 基本思路：
对于归并的非递归来说可以用栈也可以用循环，这里主要讲解循环（比较简单，直接从合并步骤开始）
- 实现代码：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1;//数组归并距离 //（初始gap为1即每个数组只有一个元素，此时每个数组都为有序数组） while (gap < n)//归并趟次 { for (int i = 0; i < n; i += gap * 2)//分组归并 { //划分区间 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //判断越界的情况 //这种情况不用考虑归并（已经有序） if (end1 >= n|| begin2 >= n) { break; } //这种情况需要归并 if (end2 >= n) { end2 = n - 1; } //归并 int p = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[p++] = a[begin1++]; } else { tmp[p++] = a[begin2++]; } } while (begin1 <= end1) { tmp[p++] = a[begin1++]; } while (begin2 <= end2) { tmp[p++] = a[begin2++]; } //拷贝排序后数据到原数组 for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp);//释放 tmp = NULL; }
八、计数排序
计数排序是一种非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用
1、计数排序
- 基本思想：
在排序数组中找到最大最小的数据，算出对应范围并创建对应长度个数组用来计数，遍历排序数组，根据每个出现的数据值与计数数组下标构建的相对映射关系进行统计数据出现次数，最后将统计的出的数据按次序赋值给原数组
- 动图展示
- 实现代码：
void CountSort(int* a, int n) { //遍历找出数组最大最小值（算出范围） int max = a[0], min = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; //开辟对应长度个计数数组 int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); exit(-1); } //初始化数组计数为0 memset(count, 0, sizeof(int)*range); //遍历计数据出现次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; //a[i] - min：数据与下标构成的相对映射关系 } //排入原数组 int p = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[p++] = i + min; } } free(count);//释放 count = NULL; }
- 计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限（只能对整数排序）
- 时间复杂度：O(MAX(N,range))
- 空间复杂度：O(range)
- 稳定性：稳定
九、性能分析
- 排序算法复杂度及稳定性总结：
- 性能测试代码：
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); //给开辟数组赋值 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]; } //数组排序并计算时间花费 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(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = 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("MergeSort:%d\n", end6 - begin6); printf("BubbleSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); //释放数组 free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } int main() { TestOP(); return 0; }
注：在Release版本下测试比Debug好一点，Release会对测试具有优化，更好的体现排序算法性能
- 测试结果：
- 总结：
总体来说插入排序，选择排序，冒泡排序是低一级水平的排序算法，希尔排序，堆排序，归并排序和快速排序是高一级别的排序，而计数排序效率非常高，但有一定局限
