手撕各种排序（中）：https://developer.aliyun.com/article/1389401
🌙归并排序
这里讲述两种方法，一种是递归型另一种则是非递归
💫归并排序递归型
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
void _MergeSort(int* a, int* tmp, int begin, int end) { //尾小于头时 if (end <= begin) return; //开始分割 int mid = (end + begin) / 2; // [begin, mid][mid+1, end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); //归并到tmp数据组，再拷贝回去 //a->[begin, mid][mid+1, end]->tmp int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin; //开始拷贝 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //当第一段元素没有完全拷贝完就把剩下的拷贝进去 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } //当第二段元素没有完全拷贝完就把剩下的拷贝进去 while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //归并排序（分路并归） void MergeSort(int* a, int n) { //开辟空间 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } //调用 _MergeSort(a, tmp, 0, n - 1); //释放内存 free(tmp); }
💫归并排序非递归型
第一次当 gap 为 1 的时候，我们将距离为 1 的两个数组（其实就是两个元素为 1 的数）进行归并，得到了拥有两个元素的一个有序数组，然后通过循环将后面的元素全部用同样的方式归并。然后就得到了如上图所示蓝色表示的元素排布。同时我们在将这一步骤之后的数组拷贝回到原数组。在进行接下来的操作（这里的意思和上递归的是一样的）。接着每次将 gap 的值增加 2 倍，直到 gap 的值不小于 n 结束归并。这个过程我们将其称为小区间优化。
//归并排序（非递归） void MergeSortNonR(int* a, int n) { //开辟空间 int* tmp = (int*)malloc(sizeof(int) * n); //判断 if (tmp == NULL) { perror("malloc fail"); return; } 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; // [begin1,end1] [begin2,end2] 归并 // 如果第二组不存在，这一组不用归并了 if (begin2 >= n) { break; } // 如果第二组的右边界越界，修正一下 if (end2 >= n) { end2 = n - 1; } //printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2); int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 拷贝回原数组 memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int)); } printf("\n"); gap *= 2; } free(tmp); }
🌙计数排序
计数排序的朴素方法步骤：
1、从无序数组中取出最大值max，新建一个长度为max+1的数组。
2、遍历无序数组，取其中元素作为新建数组的索引，存在一个则新数组该索引所在的值自增。
3、遍历新数组，当存在不为0的元素，取该元素的索引放入最终数组，并且该元素自减，直到为0，返回最终数组。
上代码：
//计数排序测试 void CountSort(int* a, int n) { //找最大值和最小值 int min = a[0], max = a[0]; for (size_t i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } //找出区间 int range = max - min + 1; //开辟（区间） int* count = (int*)malloc(sizeof(int) * range); printf("range:%d\n", range); //判断 if (count == NULL) { perror("malloc fail"); return; } //计入数字的个数 memset(count, 0, sizeof(int) * range); // 统计数据出现次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } }
⭐总结
咱看看每种排序的复杂度和稳定性。
🌠Sort.h代码
#include<stdio.h> //打印数据 void PrintArray(int* a, int n); //冒泡排序测试 void BubbleSort(int* a, int n); //插入排序测试 void InsertSort(int* a, int n); //希尔排序测试 void ShellSort(int* a, int n); //选择排序测试 void SelectSort(int* a, int n); //堆排序测试 void HeapSort(int* a, int n); //快排测试 void QuickSort1(int* a, int begin, int end); void QuickSort2(int* a, int begin, int end); //快排非递归测试 void QuickSortNonR(int* a, int begin, int end); //归并排序测试 void MergeSort(int* a, int n); //归并排序（非递归）测试 void MergeSortNonR(int* a, int n); //计数排序测试 void CountSort(int* a, int n);
🌠Test.c代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<time.h> #include<stdlib.h> #include"Sort.h" #include"Stack.h" //希尔排序测试 void TestShellSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; ShellSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } //冒泡排序测试 void TestBubbleSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; BubbleSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } //堆排序测试 void TestHeapSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; HeapSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } //选择排序测试 void TestSelectSort() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; SelectSort(a, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } //测试代码 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); for (int i = N - 1; i >= 0; --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]; } int begin1 = clock(); //插入排序 InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); //希尔排序测试 ShellSort(a2, N); int end2 = clock(); int begin7 = clock(); //冒泡排序测试 BubbleSort(a7, N); int end7 = 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); //计数排序测试 //CountSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("BubbleSort:%d\n", end7 - begin7); 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("CountSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { TestOP(); //TestBubbleSort(); //TestHeapSort(); //TestSelectSort(); //TestQuickSort(); //TestMergeSort(); //TestCountSort(); //printf("%d\n", Func(100000)); return 0; }
🌠Sort.c代码
#define _CRT_SECURE_NO_WARNINGS 1 #include"Sort.h" #include"Stack.h" //交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //打印数据 void PrintArray(int* a, int n) { //循环 for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } //冒泡排序测试 void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int exchange = 0; for (int j = 1; j < n - i; j++) { if (a[i - 1] > a[i]) { //这里是一个交换函数 Swap(&a[i - 1], &a[i]); exchange = 1; } } //这里进行一趟有序时，直接跳出循环 if (exchange == 0) { break; } } } //插入排序 void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; //一个元素进行插入 while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; } else { break; } --end; } //最后把插入的元素赋值回去 a[end + 1] = tmp; } } //希尔排序测试 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { //间隔gap的元素进行排序 gap = gap / 3 + 1; //本质上是插入排序 for (int i = 0; i < n - gap; ++i) { int end = i; int tmp = a[end + gap]; //一个元素进行插入 while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end = end - gap; } else { break; } } //最后把插入的元素赋值回去 a[end + gap] = tmp; } } } //void ShellSort(int* a, int n) //{ /*int gap = 3; for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } */ //选择排序测试 void SelectSort(int* a, int n) { //初始化第一个元素 和 最后一个元素 int begin = 0; int end = n - 1; while (begin < end) { //选出最大值和最小值 int mini = begin, maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } //最小值和最初的元素交换 Swap(&a[begin], &a[mini]); //如果max被换走就需要重新赋值 if (maxi == begin) { maxi = mini; } //最大值和最末的元素交换 Swap(&a[end], &a[maxi]); ++begin; --end; } } //堆排序测试 //实现向下调整建大堆 void AdjustDown(int* a, int n, int parent) { //孩子和父亲的关系 int child = parent * 2 + 1; while (child < n) { //找出小的那个孩子 if (child + 1 < n && a[child + 1] < a[child]) { ++child; } //实现向下调整元素 if (a[child] < a[parent]) { //元素交换 Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序测试 void HeapSort(int* a, int n) { //向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { //实现向下调整建大堆 AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { //元素交换 Swap(&a[0], &a[end]); //实现向下调整建大堆 AdjustDown(a, end, 0); --end; } } //三数取中 （找出中间值） int GetMidi(int* a, int left, int right) { //中间值 int mid = (left + right) / 2; //三个数比较找出中间值 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } // 右边找小，左边找大，交换，把左边的值跟a[keyi]交换 int PartSort1(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定位最左边（相对） int keyi = left; while (left < right) { //找小 while (left < right && a[right] >= a[keyi]) { --right; } //找大 while (left < right && a[left] <= a[keyi]) { ++left; } //左右交换 Swap(&a[left], &a[right]); } //此时左边走到中间了，开始交换 Swap(&a[keyi], &a[left]); //返回 return left; }; //挖坑法 int PartSort2(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定位最左边（相对） int key = a[left]; //保存key值以后，左边形成第一个坑 int hole = left; while (left < right) { //右边先走，找小，填到左边的坑，右边形成新的坑位 while (left < right && a[right] >= key) { --right; } a[hole] = a[right]; hole = right; //左边再走，找大，填到右边的坑，左边形成新的坑位 while (left < right && a[left] <= key) { ++left; } a[hole] = a[left]; hole = left; } a[hole] = key; return hole; } //前后指针 int PartSort3(int* a, int left, int right) { //找中间值（相对） int midi = GetMidi(a, left, right); //把最左边（相对）跟中间值（相对）换 Swap(&a[left], &a[midi]); //定义指针开头 int prev = left; //定义指针开头后一个 int cur = prev + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } //交换 Swap(&a[prev], &a[keyi]); return prev; } //快排测试一 void QuickSort1(int* a, int begin, int end) { if (begin >= end) return; //小区间优化，小区间不再递归分割排序，降低递归次数 //当元素小于10时，采用插入排序 if ((end - begin + 1) > 10) { //找值 int keyi = PartSort3(a, begin, end); // [begin, keyi-1] keyi [keyi+1, end] QuickSort1(a, begin, keyi - 1); QuickSort1(a, keyi + 1, end); } else { //插入排序 InsertSort(a + begin, end - begin + 1); } } //快排测试二 void QuickSort2(int* a, int begin, int end) { if (begin >= end) return; //调用 int keyi = PartSort3(a, begin, end); //[begin, keyi-1] keyi [keyi+1, end] QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi + 1, end); } //快排非递归（采用栈的形式）（先进后出） void QuickSortNonR(int* a, int begin, int end) { //定义 ST st; //初始化 STInit(&st); //添加元素 STPush(&st, end); STPush(&st, begin); while (!STEmpty(&st)) { //剥离元素 让left取先入但是后出的元素（区间的左边） int left = STTop(&st); STPop(&st); //让right取栈顶元素（是我们后入的区间的右边） int right = STTop(&st); STPop(&st); // 右边找小，左边找大，交换，把左边的值跟a[keyi]交换 int keyi = PartSort1(a, left, right); //分割成段 // [lefy,keyi-1] keyi [keyi+1, right] if (keyi + 1 < right) { //添加元素 STPush(&st, right); STPush(&st, keyi + 1); } if (left < keyi - 1) { //添加元素 STPush(&st, keyi - 1); STPush(&st, left); } } //销毁 STDestroy(&st); } void _MergeSort(int* a, int* tmp, int begin, int end) { //尾小于头时 if (end <= begin) return; //开始分割 int mid = (end + begin) / 2; // [begin, mid][mid+1, end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); //归并到tmp数据组，再拷贝回去 //a->[begin, mid][mid+1, end]->tmp int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin; //开始拷贝 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //当第一段元素没有完全拷贝完就把剩下的拷贝进去 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } //当第二段元素没有完全拷贝完就把剩下的拷贝进去 while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝回原数组 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } //归并排序（分路并归） void MergeSort(int* a, int n) { //开辟空间 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } //调用 _MergeSort(a, tmp, 0, n - 1); //释放内存 free(tmp); } //归并排序（非递归） void MergeSortNonR(int* a, int n) { //开辟空间 int* tmp = (int*)malloc(sizeof(int) * n); //判断 if (tmp == NULL) { perror("malloc fail"); return; } 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; // [begin1,end1] [begin2,end2] 归并 // 如果第二组不存在，这一组不用归并了 if (begin2 >= n) { break; } // 如果第二组的右边界越界，修正一下 if (end2 >= n) { end2 = n - 1; } //printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2); int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 拷贝回原数组 memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int)); } printf("\n"); gap *= 2; } free(tmp); } //计数排序测试 void CountSort(int* a, int n) { //找最大值和最小值 int min = a[0], max = a[0]; for (size_t i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } //找出区间 int range = max - min + 1; //开辟（区间） int* count = (int*)malloc(sizeof(int) * range); printf("range:%d\n", range); //判断 if (count == NULL) { perror("malloc fail"); return; } //计入数字的个数 memset(count, 0, sizeof(int) * range); // 统计数据出现次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } //排序 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } }
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
