1. 快排性能的关键点分析
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本二分居中，那么快排的递归树就是颗均匀的满⼆叉树，性能最佳。但是实践中虽然不可能每次都是二分居中，但是性能也还是可控的。但是如果出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组序列有序时就会出现这样的问题，我们前面已经用三数取中或者随机选key解决了这个问题，也就是说我们解决了绝大多数的问题，但是现在还是有⼀些场景没解决(数组中有大量重复数据时)，类似以下代码。
// 数组中有多个跟key相等的值
int a[] = { 6,1,7,6,6,6,4,9 };
int a[] = { 3,2,3,3,3,3,2,3 };
// 数组中全是相同的值
int a[] = { 2,2,2,2,2,2,2,2 };1.1 三路划分算法思想讲解
当面对有大量跟key相同的值时，三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段【比key小的值】【跟key相等的值】【比key大的值】，所以叫做三路划分算法。结合下图，理解一下实现思想：
1. key默认取left位置的值；
2. left指向区间最左边，right指向区间最后边，cur指向left+1位置；
3. cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++；
4. cur遇到比key大的值后跟right位置交换，换到右边，right--；
5. cur遇到跟key相等的值后，cur++；
6. 直到cur > right结束。
#include <stdio.h>
#include <stdlib.h>/* 思路：
1. key默认取left位置的值。
2. left指向区间最左边，right指向区间最后边，cur指向left+1位置。
3. cur遇到⽐key⼩的值后跟left位置交换，换到左边，left++，cur++。
4. cur遇到⽐key⼤的值后跟right位置交换，换到右边，right--。
5. cur遇到跟key相等的值后，cur++。
6. 直到cur>right结束
*/void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort(int* arr, int left, int right)
{if (left >= right)return;int begin = left;int end = right;// 随机选基准值keyint randi = left + (rand() % (right - left + 1));Swap(&arr[left], &arr[randi]);// 三路划分// left和right指向就是跟key相等的区间// [begin, left-1] [left, right] [right+1, end]int key = arr[left];int cur = left + 1;while (cur <= right){// 1.cur遇到比key小，小的换到左边，同时把key换到中间位置// 2.cur遇到比key大，大的换到右边if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);--right;}else{// cur位置的值与key相等，cur++，避免重复交换++cur;}} // [begin, left-1] [left, right] [right+1, end]QuickSort(arr, begin, left - 1);QuickSort(arr, right + 1, end);
}void Print(int* a, int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}int main()
{int a[] = { 6, 1, 7, 6, 6, 6, 4, 9 };int n = sizeof(a) / sizeof(a[0]);printf("排序前：\n");Print(a, n);QuickSort(a, 0, n - 1);printf("排序后：\n");Print(a, n);return 0;
}
1.2 introsort快排（自省快排）
introsort是introspective sort采用了缩写，他的名字其实表达了他的实现思路，它的思路就是进行自我侦测和反省，快排递归深度太深（sgi stl中使用的是深度为2倍排序元素数量的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。
#include <stdio.h>
#include <stdlib.h>// 这是C++官方库的一种方法
// 适用于任何环境下的一种高效排序算法void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 直接插入排序--时间复杂度略小于O(n^2)
// 希尔排序 gap == 1 就是直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; ++i){int end = i;int tmp = arr[end + 1];while (end >= 0){// 排升序--大的往后放if (arr[end] > tmp){arr[end + 1] = arr[end];--end;}else{break;}}arr[end + 1] = tmp;}
}// 向下调整
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){// 先找最大的孩子--排升序--建大堆if (child + 1 < n && arr[child + 1] > arr[child]){++child;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 堆排序--O(nlogn)
void HeapSort(int* arr, int n)
{// 向下调整for (int i = (n - 1 - 1) / 2; i >= 0; --i) // O(n){AdjustDown(arr, i, n); // O(logn)}// 排升序--建大堆int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);--end;}
}// 快排--自省
// depth：深度 // defaultDepth：限制深度void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;// 小区间优化// 数组长度小于16的小数组，换为插入排序，简单递归次数if (right - left + 1 < 16){InsertSort(a + left, right - left + 1);return;}// 当深度depth超过2*logn改用堆排序if (depth > defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;// 随机选基准值keyint randi = left + (rand() % (right - left + 1));Swap(&a[left], &a[randi]);// 前后指针int prev = left;int cur = prev + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[key]);key = prev;// [begin, key-1] key [key+1, end]IntroSort(a, begin, key - 1, depth, defaultDepth);IntroSort(a, key + 1, end, depth, defaultDepth);
}void QuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int n = right - left + 1;for (int i = 1; i < n; i *= 2){logn++;}// 自省排序// 这里的控制深度logn * 2可以自己控制，可以是logn、logn * 3、logn * 4...IntroSort(a, left, right, depth, logn * 2);
}void Print(int* a, int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}int main()
{int a[] = { 6, 1, 7, 6, 6, 6, 4, 9 };int n = sizeof(a) / sizeof(a[0]);printf("排序前：\n");Print(a, n);QuickSort(a, 0, n - 1);printf("排序后：\n");Print(a, n);return 0;
}
完