1.快排介绍快排的核心思想就是分而治之。这里我们讲的是三路划分的快排三路划分可以避免当数组中有大量重复元素时出现无谓的递归速度更快随机选择一个基准元素把比它小的放在左边比它大的放在右边等于的放中间然后再去递归处理左边和右边中间的等于区间就不用再处理了。举个例子假设排序 [5, 2, 8, 5, 1, 5, 3]选基准为 5。三路划分后的结果类似[2, 1, 3] [5, 5, 5] [8]然后只需要左边 [2,1,3] 和右边 [8] 递归中间的三个 5 相当于已经排好了。2.快排具体过程还是拿[5, 2, 8, 5, 1, 5, 3]这个数组来分析快排的具体过程。由快排的介绍我们知道要想把数组划分成三块就要先找一个基准元素我们这里通过获取随机值的方法来得到基准元素这种获得基准元素的方法最好。1随机找基准元素要想找到区间的基准元素得知道整个数组还有区间的左右端点下标。//参数完整数组 数组的左端点 数组的右端点 int getRandom(int* arr,int left,int right) { int index leftrand() % (right - left 1); return arr[index]; }别忘了加上left我就老是忘哈哈哈哈哈哈2根据基准元素把数组分三块数组分三块肯定要遍历这个数组所以我们用一个cur指针来遍历这个区间记住curleftcur不等于0因为我们写得数组分三块这个思想是要去递归的每个区间得起始下标都是left。再用一个L指向小于基准元素的区间的最右侧R来指向大于基准元素的区间的最左侧一定要搞懂L和R变量的含义很重要刚开始这两个区间都不存在所以Lleft-1Rright1。要用到的变量都解释清楚后我们就来模拟数组分三块的这个过程吧假设基准元素随机选到了5。第一开始arr[cur]等于5cur直接此时cur指向2小于基准元素就要把2加入到红色区间就是left先然后再和cur指向的2交换cur在遍历下一个元素-swap(arr[left],arr[cur])。cur指向8大于基准元素则需要把8加入到绿色区间right先--然后再和cur指向的8交换cur不要因为交换过来的元素还没有遍历呢直接就会漏掉遍历这个元素cur现在指向right左边的3-swap(arr[--right],arr[cur])。现在遍历到小于基准元素的值等于大于三种情况该如何处理都已经知道了下面就是要考虑循环遍历什么时候终止了。很容易能想到当curR的时候循环终止也就是curR循环一直进行。最后数组会被划分成这三个区间。【leftL】(小于基准元素的区间)【L1R-1】(等于基准元素的区间)【R,right】。【L1,R-1】区间相当于已经排好了接下来只需要递归处理【leftL】和【Rright】区间即可重复数组分三块的过程直到leftright说明区间只有一个元素或者区间不合法此时递归终止。3.快排完整代码#includeiostream using namespace std; void qSort(int* arr, int left, int right) { //递归出口 区间内只有一个元素了说明这个区间已经有序了 if (left right) return; int key getRandom(arr, left, right);//随机获得基准元素 int L left - 1, R right 1,curleft; while (cur R) { if (arr[cur] key) cur; else if (arr[cur] key) swap(arr[L], arr[cur]); else swap(arr[--R], arr[cur]); } //【leftL】【L 1R - 1】【R, right】 qSort(arr, left, L); qSort(arr, R, right); } int getRandom(int* arr, int left, int right) { int index leftrand() % (right - left 1); return arr[index]; } int main() { srand(time(NULL)); int arr[] {5, 2, 8, 5, 1, 5, 3}; int n sizeof(arr) / arr[0]; qSort(arr,0,n-1); return 0; }4.快排的时间复杂度和稳定性时间复杂度O(n*logn)稳定性不稳定