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[] = { 3,3,3,3,3,3,3,3 };2.三路划分算法
这里使用三路划分可以提升当数组中，有大量相同的值时，排序的时间效率，三路划分的核⼼思想有点类似hoare的左右指针和lomuto的前后指针的结合（这里的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结束
排序成这样以后，再递归left之前的数组，和right之后的数组就可以了。
注意：这种排序方法，主要是当数组中有大量相同的数据时，时间效率较高，但如果数组中没有大量相同的数据，这种算法的时间效率甚至还不如，lomuto和hoare版的快速排序。
三路划分针对有⼤量重复数据时，效率很好，其他场景就⼀般，但是三路划分思路还是很有价 值的，有些快排思想变形体，要⽤划分去选数，他能保证跟key相等的数都排到中间去，三路划分的价值就体现出来了。
void _QuicksortPro(int* arr, int left, int right)//三路划分：有大量相同数据
{if (left >= right)return;int begin = left;int end = right;int randi = left + (rand()%(right - left + 1));Swap(&arr[left], &arr[randi]);int key = arr[left];int cur = left + 1;while (cur <= right){if (arr[cur] < key){Swap(&arr[left++], &arr[cur++]);}else if (arr[cur > key]){Swap(&arr[cur], &arr[right--]);}else{cur++;}}_QuicksortPro(arr, begin, left - 1);_QuicksortPro(arr, right + 1, end);
}void Quicksort(int* arr, int left, int right)
{srand(time(0));_QuicksortPro(arr, left, right);
}3.introsort的快排排序（内省排序）
introsort是由DavidMusser在1997年设计的排序算法，C++sgi STL sort中就是⽤的introspective sort(内省排序)思想实现的。内省排序可以认为不受数据分布的影响，⽆论什么原因划分不均匀， 导致递归深度太深，他就是转换堆排了，堆排不受数据分布影响。
首先确定递归深度达到多少时,深度一般为logn的两倍（数据个数取二的对数：2*logn），就停止这种排序转换成堆排序（堆排序，在小编之前“堆的应用”文章中已有详细讲解）；
其次当数组长度小于十六时，就直接使用插入排序，简单递归次数；
代码如下：
//直接插入排序
void InsertSort(int* arr, int size)
{for (int i = 0; i < size-1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];}else {break;}end--;}arr[end + 1] = tmp;}
}//堆排序
void AdjustDwon(int* a, int n, int root)
{int parent = root;int child = 2 * parent + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int* a, int n)
{int parent = (n - 1 - 1) / 2;while (parent >= 0){AdjustDwon(a, n, parent);parent--;}int size = n - 1;while (size > 0){Swap(&a[0], &a[size]);AdjustDwon(a, size, 0);size--;}
}void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{if (left >= right){return;}if (right - left + 1 < 16){InsertSort(arr + left, right - left + 1);return;}if (depth > defaultDepth){HeapSort(arr+ left, right - left + 1);return;}depth++;int begin = left;int end = right;int randi = left + (rand() % (right - left + 1));Swap(&arr[randi], &arr[left]);int keyi = left;int prev = left, cur = left + 1;while (cur <=right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);keyi=prev;IntroSort(arr, begin, keyi - 1, depth, defaultDepth);IntroSort(arr, keyi+1, end, depth, defaultDepth);
}void QuickSort（int *arr,int left,int right）
{int depth = 0;int logn = 0;int size=right-left+1; for (int i = 1; i < size; i*=2){logn++;}IntroSort(arr, left, right, depth,logn*2);
}