个人主页：Lei宝啊
愿所有美好如期而遇
目录
快排简介：
快速排序，参见： qsort详解及其模拟实现
快排的三种递归实现：
Hoare：
此法乃Hoare大佬所创，我等一个不注意便就掉入陷阱，大坑于代码处自有注释，诸君慢品：
//Hoare版本 right传数组下标 void QuickSort_Binary(int* arr, int left, int right) { if (left >= right) return; //选定一个数keyi，最好是不大也不小，上面加个三数取中 int keyi = left; //快排开始的区间,都是闭区间 int begin = left; int end = right; while (begin < end) { //一坑在=，若无此，循环不止 //二坑在begin < end，若无此，有越界之忧，end或减减不止 //三坑在要从右先行，以此保证begin与end相遇时 // 二者所指处值小于keyi所指值 while (begin < end && arr[end] >= arr[keyi]) { end--; } while (begin < end && arr[begin] <= arr[keyi]) { begin++; } Swap(&arr[end], &arr[begin]); } Swap(&arr[begin], &arr[keyi]); QuickSort_Binary(arr, left, begin - 1); QuickSort_Binary(arr, begin + 1, right); }
挖坑：
此法则无关左右矣
//挖坑法 传数组下标 void QuickSort_Binary(int* arr, int left, int right) { if (left >= right) return; int hole = left; int temp = arr[left]; //定义这两变量主要是为了区分后面递归时的区间 int begin = left; int end = right; while(begin < end) { while(begin < end && arr[end] >= temp) { end--; } //交换爽啊，赋值的话循环结束后，还要把temp的值赋给hole位置 Swap(&arr[hole], &arr[end]); hole = end; while (begin < end && arr[begin] <= temp) { begin++; } Swap(&arr[hole], &arr[begin]); hole = begin; } QuickSort_Binary(arr, left, begin - 1); QuickSort_Binary(arr, begin + 1, right); }
双指针：
//双指针法 传数组下标 void QuickSort_Binary(int* arr, int left, int right) { if (left >= right) return; int temp = arr[left]; int prev = left; int cur = left; while (cur <= right) { while (arr[cur] < temp && ++prev != cur) { Swap(&arr[prev], &arr[cur]); } cur++; } //想法大致都是keyi位置的值不动，从下一个位置开始，最后交换keyi位置和停止位置 //停止位置的值一定比keyi位置的值要小 Swap(&arr[left], &arr[prev]); QuickSort_Binary(arr, left, prev - 1); QuickSort_Binary(arr, prev + 1, right); }
小区间优化：
我们可以发现的是，递归像一座金字塔，越是到下面，递归次数越多，而我们通过计算得知，一颗满二叉树节点数为2^n-1，最后一层节点数为2^(n-1)，也就是说，最后三层节点数占到总数的近87.5%,
也就是说，剩余的节点小于15就不要递归了，可以使用插入排序，这个还是比较好的，插入排序参见：插入排序与希尔排序
以Hoare大佬的排序为例：
//Hoare版本 right传数组下标 void QuickSort_Binary(int* arr, int left, int right) { if (left >= right) return; if(right-left+1 >= 15) { //选定一个数keyi，最好是不大也不小，上面加个三数取中 int keyi = left; //快排开始的区间,都是闭区间 int begin = left; int end = right; while (begin < end) { //一坑在=，若无此，循环不止 //二坑在begin < end，若无此，有越界之忧，end或减减不止 //三坑在要从右先行，以此保证begin与end相遇时 // 二者所指处值小于keyi所指值 while (begin < end && arr[end] >= arr[keyi]) { end--; } while (begin < end && arr[begin] <= arr[keyi]) { begin++; } Swap(&arr[end], &arr[begin]); } Swap(&arr[begin], &arr[keyi]); QuickSort_Binary(arr, left, begin - 1); QuickSort_Binary(arr, begin + 1, right); } else { InsertSort(arr,right-left+1); } }
三数取中优化：
再一个，如果说一个序列已然有序，我们再使用快排就很难受，此时时间复杂度直达O(N^2),所以如果我们加上三数取中，就不会出现最坏情况，但是力扣老贼针对快排，快排的三数取中我们仍要修改，改为随机数取中。
int GetMidNum(int* a, int left, int right) { int mid = left + (rand() % (right - left)); if (a[left] > a[mid]) { if (a[mid] > a[right]) { return mid; } else if (a[left] > a[right]) { return right; } else { return left; } } else { if (a[left] > a[right]) { return left; } else if (a[mid] > a[right]) { return right; } else { return mid; } } }
这样我们返回这个中间值坐标后，这样做：
1. int mid = GetMidNum(arr, left, right); 2. Swap(&arr[left], &arr[mid]);
快排非递归实现：
快排掌握递归并不够，虽然说他的空间复杂度不高，尽管我们有了上述优化，但是仍然难以保证他不会爆栈，所以掌握非递归还是很有必要的。
快速排序的非递归类似于二叉树的前序遍历，我们在这里需要借助于栈，当然队列也可，但是这样的话就类似于二叉树的层序遍历了。
栈和队列参考：栈和队列的实现
二叉树的前序遍历参考：二叉树的几个递归问题
二叉树的层序参考：二叉树的层序遍历及判断完全二叉树
void QuickSortNonR(int* a, int left, int right) { Stack stack; Init(&stack); Push(&stack, right - 1); Push(&stack, left); while (!Empty(&stack)) { int begin = GetTop(&stack); Pop(&stack); int end = GetTop(&stack); Pop(&stack); int mid = SortWay_two(a, begin, end); if (mid + 1 < end) { Push(&stack, end); Push(&stack, mid + 1); } if (begin < mid) { Push(&stack, mid); Push(&stack, begin); } } }
这里注意栈的特性是先进后出。
快排的三路划分实现：
在力扣的针对下，有大佬推出了这个算法，使得快排终于能够通过。
我们的快排是大等于或小等于，而三路划分是小的在左，相等于keyi的在中间，大的在右，使得我们直接递归相等数的左边和右边就可。
//快排三路划分 void QuickSort_ThrDiv(int *arr,int left,int right) { if (left >= right) return; srand((unsigned int)time(NULL)); int mid = GetMidNum(arr, left, right); Swap(&arr[left], &arr[mid]); int begin = left; int end = right; int keyi = arr[left]; int cur = left + 1; while (cur <= right) { if (arr[cur] < keyi) { Swap(&arr[cur], &arr[left]); left++; cur++; } else if (arr[cur] > keyi) { Swap(&arr[cur], &arr[right]); right--; } else { cur++; } } QuickSort_ThrDiv(arr, begin, left - 1); QuickSort_ThrDiv(arr, right + 1, end); }
今晚的风，吹得好浪漫~
