挖坑法
人们所熟知的快排就是这个思想，比霍尔法更容易清晰理解。先将第一个数放在临时变量key中，此时形成一个坑位，然后右边先走找小，遇到小的停下来，将该值赋给坑位，并形成一个新的坑位。并且左边找大，赋值，形成新的坑位，直至两边相遇，将key值赋给左边。
//快速排序(挖坑法) void QuickSort_dig(int* a, int begin, int end) { //左边作key,右边先走找小，找到了停下 //左边再走找大，找到停下，交换 //重复 if (begin >= end) { return; } //一次排序 int left = begin; int right = end; int keyi = GetMidIndex(a,left,right); int key = a[keyi]; while (left < right) { //找小 while (left < right && a[keyi] <= a[right]) { --right; } a[keyi] = a[right]; keyi = right; //right变为坑 //找大 while (left < right && a[left] <= a[keyi]) { ++left; } a[keyi] = a[left]; keyi = left; } a[keyi] = key; //递归 QuickSort_old_hoare(a, begin, keyi - 1); QuickSort_old_hoare(a, keyi + 1, end); }
函数分开版本：
void QuickSort(int* a, int begin,int end) { if (begin >= end) { return; } if (end-begin>10) { int keyi = Partition2(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi+1, end); } else { InsertSort(a + begin, end - begin + 1); } } //挖坑版本 int Partition2(int* a, int begin, int end) { int left = begin; int right = end; //int keyi = begin;//坑在起始位置 int keyi = GetMidIndex(a,begin,end);//坑在起始位置 int key = a[keyi]; while (left < right) { //找小 while (left < right &&a[right] >= key) { --right; } a[keyi] = a[right];//填坑 keyi = right;//换坑 //找大 while (left < right && a[left] <= key) { ++left; } a[keyi] = a[left];//填坑 keyi = left;//换坑 } a[keyi] = key; return keyi; }
双指针版本
这个版本利用双‘指针’，优化了代码结构，使代码变得更加简洁，但是代码的可读性变差。快指针的作用是找小，慢指针的作用是保留边界，两个指针中间是大数，以翻跟头的形式往前走。
//双指针版本 int Partition3(int* a, int begin, int end) { //prev在起始位置，cur在下一个位置 //判断cur，若cur小于prev，则prev+1交换 //大于prev，cur++ int prev = begin; int cur = prev + 1; int key = a[begin]; while (cur <= end) { 当prev+1 == cur时，如果再交换的话就浪费了 //if (a[cur] < key ) //{ // ++prev; // Swap(&a[cur], &a[prev]); //} //++cur; //当prev+1 == cur时，如果再交换的话就浪费了 if (a[cur] < key&&++prev!=cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[begin], &a[prev]); return prev; } void QuickSort(int* a, int begin,int end) { if (begin >= end) { return; } if (end-begin>10) { int keyi = Partition2(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi+1, end); } else { InsertSort(a + begin, end - begin + 1); } }
快排优化
为了防止最坏情况下爆栈，我们需要使用三数取中法来优化选择keyi的位置。这样递归的深度接近logN。
//为了防止最坏情况爆栈，我们可以用三数取中法来优化，keyi // 三数取中法 int GetMidIndex(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] > a[mid]) { if (a[mid] > a[end]) { return mid; } else { if (a[end] > a[begin]) { return begin; } else { return end; } } } else { if (a[end] < a[begin]) { return begin; } else { if (a[end] > a[mid]) { return mid; } else { return end; } } } }
快速排序非递归
因为快排的思想接近于二叉树的先序遍历，因此我们可以考虑使用栈来模拟递归的过程。核心思想就是：利用栈来保存每次快排的区间。有点类似于层序遍历的方法。
//快排非递归(需要使用栈) // 要求掌握，递归改非递归 // 递归大问题，极端场景下面，如果深度太深，会出现栈溢出 // 1、直接改循环 -- 比如斐波那契数列、归并排序 // 2、用数据结构栈模拟递归过程 void QuickSort_nonrecursive(int* a, int begin, int end) { //先将左右入栈 //出栈，调用快排函数 //调用完了再入栈 Stack q; StackInit(&q); StackPush(&q, end); StackPush(&q, begin); //栈不空 while (!StackEmpty(&q)) { int left = StackTop(&q); StackPop(&q); int right = StackTop(&q); StackPop(&q); 如果左小于右说明可以划分，就继续入栈 //if (left < right) //{ // int keyi = Partition2(a, left, right); // StackPush(&q, keyi - 1); // StackPush(&q, left); // StackPush(&q, right); // StackPush(&q, keyi + 1); //} int keyi = Partition2(a, left, right); //小区间能继续划分，就入栈 if (left < keyi - 1) { StackPush(&q, keyi - 1); StackPush(&q, left); } if (keyi + 1 < right) { StackPush(&q, right); StackPush(&q, keyi + 1); } } StackDestroy(&q); }
特性总结：
1.快排，顾名思义综合性能最好，适应场景最多
2.时间复杂度：O（NlogN）
3.空间复杂度：O（logN）
4.稳定性：不稳定
5. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法采用分治法（Divide and Conquer）。将已有序的子序列合并，得到完全有序的序列；即先保证子序列有序，然后将两个子序列合并成一个有序序列，称为二路归并。核心步骤：先分解、后合并。
归并递归版本
// 归并排序递归 void MergeSort(int* a, int n) { int* tem = (int*)malloc(sizeof(int) * n); if (tem == NULL) { printf("malloc failed"); exit(0); } _MergeSort(a, 0, n - 1, tem); free(tem); } void _MergeSort(int* a, int begin, int end, int* tem) { //begin和end左闭右闭区间 if (begin >= end) //只有一个元素就不需要归并了 { return; } //1.分解 int mid = (begin + end) / 2; _MergeSort(a, begin, mid, tem); _MergeSort(a, mid+1, end, tem); //2.合并(都是闭区间) int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int j = begin; //开始合并 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tem[j++] = a[begin1++]; } else { tem[j++] = a[begin2++]; } } while (begin1 <= end1) { tem[j++] = a[begin1++]; } while (begin2 <= end2) { tem[j++] = a[begin2++]; } //合并好一部分就拷贝回去,左闭右闭加1 memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1)); }
归并非递归版本
因为归并的递归类似于后续遍历，因此不适合用栈来模拟实现，会导致丢失区间问题。因此我们考虑使用循环来修改。利用gap来遍历数组，模拟二路归并的过程，注意区间的控制问题（很棘手）
归并一次后同意合并：
// 归并排序非递归 //后序遍历用栈不好改非递归 //考虑用循环 //第一轮，一个一个排，第二轮两个两个排， void MergeSortNonR(int* a, int n) { int begin = 0; int end = n - 1; int* tem = (int*)malloc(sizeof(int) * n); assert(tem); memset(tem, 0, sizeof(int) * n); //排序 int gap = 1; while (gap < n) { //printf("gap = %d: ", gap); for (int i = 0; i < n; i = i + 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = begin2 + gap - 1; //防止越界，修正边界 //end1越界 if (end1 >= n) { //把end1修成最后一个数 end1 = n - 1; begin2 = n; end2 = n - 1; } else if(begin2 >= n)// begin2越界 { begin2 = n; end2 = n - 1; } else if (end2 >= n) // end2越界 { end2 = n - 1; } //printf("[%d,%d] [%d,%d]->", begin1, end1, begin2, end2); //往tem，排序 int j = i;//比较位置开始，即从begin1 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tem[j++] = a[begin1++]; } else { tem[j++] = a[begin2++]; } } while (begin1 <= end1) { tem[j++] = a[begin1++]; } while (begin2 <= end2) { tem[j++] = a[begin2++]; } } //排完全部的再拷贝 //合并 //printf("\n"); memcpy(a, tem, sizeof(int) * (end - begin + 1)); gap = gap * 2; } }
归并一个区间就合并：
// 归并排序非递归 //后序遍历用栈不好改非递归 //考虑用循环 //第一轮，一个一个排，第二轮两个两个排， void MergeSortNonR(int* a, int n) { int begin = 0; int end = n - 1; int* tem = (int*)malloc(sizeof(int) * n); assert(tem); memset(tem, 0, sizeof(int) * n); //排序 int gap = 1; while (gap < n) { //printf("gap = %d: ", gap); for (int i = 0; i < n; i = i + 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = begin2 + gap - 1; //防止越界，修正边界 //end1越界 if (end1 >= n) { //把end1修成最后一个数 end1 = n - 1; begin2 = n; end2 = n - 1; } else if (begin2 >= n)// begin2越界 { begin2 = n; end2 = n - 1; } else if (end2 >= n) // end2越界 { end2 = n - 1; } //记录每次归并几个，就拷贝几个 int count = end2 - begin1 + 1; //printf("[%d,%d] [%d,%d]->", begin1, end1, begin2, end2); //往tem，排序 int j = i;//比较位置开始，即从begin1 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tem[j++] = a[begin1++]; } else { tem[j++] = a[begin2++]; } } while (begin1 <= end1) { tem[j++] = a[begin1++]; } while (begin2 <= end2) { tem[j++] = a[begin2++]; } //排完一部分就拷贝 memcpy(a + i, tem + i, sizeof(int) * count); } gap = gap * 2; } }
特性总结
1.缺点空间复杂度为O（N），该算法主要用于外部排序的思想。
2.时间复杂度：O（NlogN）
3.空间复杂度：O（N）
4.稳定性：稳定
6.计数排序
计数排序又称鸽巢原理，类似于哈希定址法：第一次统计数值出现的次数，根据统计的结果将序列回收到原来的序列中。
//计数排序 void CountSort(int* a, int n) { //找出数据的范围，找出最大值与最小值然后做差，就是数组的范围 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]; } } //创建计数数组 int count = max - min + 1; int* tem = (int*)malloc(sizeof(int) * count); assert(tem); memset(tem, 0, sizeof(int) * count); //遍历数组记录数据出现次数 for (int i = 0; i < n; i++) { tem[a[i] - min]++; } int j = 0; //排序,tem中出现几次就往a写几个 for (int i = 0; i < count; i++) { //只要tem[i]不为0，就会进入循环 while (tem[i]--) { a[j++] = i + min; } } }
特性总结
1.计数排序在数据范围集中时，效率很高，但不适合浮点数，数据范围相差太大的数据。
2.时间复杂度：O（max（N,range））
3.空间复杂度：O（range）
4.稳定性：稳定
以上就是本文对排序知识的总结，如有问题，欢迎在评论区讨论。
