快速排序

原文: https://zhuanlan.zhihu.com/p/...欢送关注我知乎号: https://www.zhihu.com/people/... 疾速排序QuickSort采纳了分治法Divide-and-ConquerMethod，通过将数组链表或其余元素集分为待排序汇合和已排序汇合，并在一次次迭代中将待排序汇合的元素转化到已排序汇合当中直到全副元素都为已排序则实现排序。 疾速排序利用这一策略，节约了解决已排序元素的老本。算法只关注残余待排序的元素，其中地位间断的未排序元素子串又分为：S1(左侧），pivot(替换枢纽元)，S2（右侧） 以疾速排序来实现升序排序为例： 先从数组当选取出一个数组作为枢轴元pivot。（选取枢纽元的策略很要害）将待排序汇合所有小于枢轴元pivot的元素移至s1(左侧），所有大于枢轴元pivot的元素移至s2（右侧）：（双指针中的相向指针法）先将枢轴元pivot(准有序局部)放到最左或者最右辨别出待排序局部。将i, j别离指向待排序局部索引的最左和最右。如果i索引指向的元素小于枢纽元，则i++；否则，i进行。j索引指向的元素大于枢纽元，j--；否则，j进行。如果i<j，则替换两个元素，持续循环3，4步骤；否则跳出循环，将i对应的元素与枢纽元pivot替换（这时候实现了宰割）这个时候定义枢轴元pivot为已排序局部，对残余未排序局部S1(左侧）S2(右侧)持续循环步骤1，2，3直到所有元素都已排序。最原始的疾速排序最原始的疾速排序采纳最简略粗犷的枢纽元选取策略，即选取第一个或最初一个元素为pivot。 该计划的均匀工夫复杂度为O(nlogn)，当遇到数组刚好有序的状况下会呈现最坏工夫复杂度O(n^2)，因为当输出序列自身有序时，会导致S1或S2汇合为空，除枢纽元外所有元素都在S1或S2，此时遍历替换的工夫效率大幅降落，因为节约了另一个区间的作用。 Python代码 nums = [23,2,4,6,2,5,1,6,13,54,8]def quicksort(nums, left, right): # left为最左索引，righ为最右索引 if left >= right: return pivot = left //取第一个元素为pivot i, j = left, right while i < j: while nums[pivot] <= nums[j] and i < j: j -= 1 while nums[pivot] >= nums[i] and i < j: i += 1 if i < j: nums[i], nums[j] = nums[j], nums[i] nums[pivot], nums[i] = nums[i], nums[pivot] quicksort(nums, left, i-1) quicksort(nums, i+1, right)def quicksort2(nums, left, right): # 用栈代替递归 if left >= right: return stack = [] while stack or left < right: if left < right: pivot = left i, j = left, right while i < j: while nums[pivot] <= nums[j] and i < j: j -= 1 while nums[pivot] >= nums[i] and i < j: i += 1 if i < j: nums[i], nums[j] = nums[j], nums[i] nums[pivot], nums[i] = nums[i], nums[pivot] stack.append((left, i, right)) right = i - 1 else: left, mid, right = stack.pop() left = mid + 1quicksort2(nums, 0, len(nums)-1)print(nums) 因为堆栈存储(递归等价于栈代替），疾速排序空间复杂度O(logn) ...

介绍快排的思维是，选取数组中一个数，作为基准(pivot)，而后将数组分成左右两局部。右边局部全副小于基准，左边局部全副大于基准。随后再去递归地对右边局部和左边局部做雷同操作，直至数组被宰割成繁多一个元素，排序实现。网络上大部分快排的实现都是递归实现，这里给出模板。 // 快排模板func QuickSort(nums []int, leftEnd, rightEnd int) { if leftEnd < rightEnd { mid := Partition(nums, leftEnd, rightEnd) QuickSort(nums, leftEnd, mid-1) QuickSort(nums, mid+1, rightEnd) }}快排函数接管数组(nums)、左边界(leftEnd)、右边界(rightEnd)。左边界必须小于右边界。数组传入后，先通过Partition()函数分区。数组和左右边界被传入Partition()后，数组会被辨别左右两局部，右边的元素都小于左边的元素，Partition()会返回一个数值mid代表分区左右的基准值的下标。随后通过递归，再对基准数左右两边作出同样操作。 快排的要害算法，在于Partition()的设计。优化的要害，大部分在于基准数的选取。 实现东尼霍尔的实现疾速排序是东尼霍尔(Tony Hoare)设计的，他设计的算法思路，是选取要排序局部的第一个元素的作为基准。而后有左右两个指针从左右往两头凑近。右指针遇到比基准小的元素，会停下。左指针遇到比基准大的元素，会停下。两个指针进行后，会替换左右指针的元素，随后持续往两头后退，直至两个指针重合。而后再把最右边的基准值插入指针所在位置。 // 霍尔分区，采纳最右边的元素作为基准func HoarePartition(nums []int, leftEnd, rightEnd int) int { pivot := nums[leftEnd] l := leftEnd r := rightEnd for l < r { for l < r && nums[r] >= pivot { r-- } for l < r && nums[l] <= pivot { l++ } nums[l], nums[r] = nums[r], nums[l] } nums[leftEnd], nums[l] = nums[l], nums[leftEnd] return l}这个实际上也是大部分人写的版本。 ...

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此在很多笔试面试中出现的几率很高。 直接默写出快速排序还是有一定难度的，所以一定要弄清楚原理再去记忆而不是去硬背。 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conque)。 最常见的实现方法是"填坑法"，它的实现步骤如下： 选定数列头元素为基准元素pivot，并记住这个位置index，这个位置相当于一个"坑"。设置两个指针left和right，分别指向数列的最左和最右两个元素。接下来从right指针开始，把指针所指向的元素和基准元素做比较，如果比pivot大，则right指针向左移动；如果比pivot小，则把所指向的元素放入index对应的位置。将被放入坑中的元素(right指针移动之前指向的元素)之前的位置赋值给index让这个位置变成一个新的"坑"，同时left指针向右移动一位。接下来切换到left指针进行比较，如果left当前指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把元素放入坑中，left指向的位置赋值给index，使其变成一个新的"坑"，同时right指针向左移动一位。重复步骤3，4，5直到left等于right时，将pivot放入left和right重合的位置，此时数列中比pivot小的元素都在pivot左边，比pivot大的都在pivot元素位置的右边。获取pivot的位置pivotIndex，分而制之，将pivotIndex左侧和右侧的子数列分别重复上述步骤1～6，直到不能拆分子数列为止，整个数列就是一个从头开始递增的数列。具体的代码实现如下： <?phpclass QuickSortClass{ public function partition(array &$arr, $startIndex, $endIndex) { // 取第一个元素为基准值 $pivot = $arr[$startIndex]; $left = $startIndex; $right = $endIndex; // 坑的位置，出事等于基准值pivot的位置 $dataIndex = $startIndex; while ($right >= $left) { // right 指针从右向左进行移动，如果当前值小于基准值则将当前元素放到坑中，当前元素的位置变成新坑，left向右移动一个位置，切换到left进行比较，否则right往左移动一个位置继续用新元素的值与基准值进行比较 while ($right >= $left) { if ($arr[$right] < $pivot) { $arr[$dataIndex] = $arr[$right]; $dataIndex = $right; $left++; break; } $right--; } // left 指针从左往右移动，如果当前值大于基准值则将当前元素放到坑中，当前元素变为新坑，right向左移动一个位置，切换到right进行比较，否则left往右移动一个位置继续与基准值进行比较 while($right >= $left) { if ($arr[$left] > $pivot) { $arr[$dataIndex] = $arr[$left]; $dataIndex = $left; $right --; break; } $left ++; } } $arr[$dataIndex] = $pivot; return $dataIndex; } public function quickSort(&$arr, $startIndex, $endIndex) { // startIndex大于等于endIndex的时候递归结束 if ($startIndex >= $endIndex) { return ; } $pivotIndex = $this->partition($arr, $startIndex, $endIndex); $this->quickSort($arr, $startIndex, $pivotIndex - 1); $this->quickSort($arr, $pivotIndex + 1, $endIndex); }}$quickSortClass = new quickSortClass();$arr = [72, 6, 57, 88, 60, 42, 83, 73, 48, 85];$quickSortClass->quickSort($arr, 0, count($arr) - 1);var_dump($arr);填坑法的口诀如下 ...

最近在学算法，学到快速排序心得就和大家分享一下。以下代码为c做演示，看不懂代码不要紧，做参考就好了，主要为了明白快速排序思路。希望能帮助到大家。快速排序分为4个步骤找一个基准数（参照数）从右往左找比基准数小的数与左坐标交换从左往右找比基准数大的数与右坐标交换左、右坐标相遇时，基准数与相遇坐标交换文字描述已讲述完，接下来草稿演示，也可以直接向下翻看代码，可能代码更有说服力国足有6名队员从左到右身高排序球号为： 5号 9号 12号 3号 7号 8号教练规定左边第一个最高的为队长（基准数）：5号教练要拆分两个队：右边的球号要小于队长球号并且左边球号不能大于右边 找到后和左边交换位置找到了3号比5号小，与左队当前坐标交换位置 新顺序为：3号 9号 12号 5号 7号 8号 坐标定在第4个人左边的球号要大于队长球号并且左边球号不能大于右边找到了9号比5号大，与右队当前坐标交换位置 新顺序为：3号 5号 12号 9号 7号 8号 坐标定在第2个人然后右边继续走找比5小的，最后走到了左队坐标位置，两个相遇相等的坐标让队长（基准数）放到相遇的位置。排队完成。最终得到的顺序为：3号 5号 12号 9号 7号 8号左队都是比队长（5号）球号小的，右边都是比队长大的接下来就要从队长开始继续拆分左、右边和上面教练说的一样直到不能拆分为止整个思路基本就这样，接下来代码实现：#include <stdio.h>#include <stdlib.h>int a[101],n;/*** 快速排序：* 1.以左边第一位作为基准数，* 2.先右边找一个比基准数小的数与左指针所在的位置进行交换 * 3.从左边找一个比基准数大的数与右指针所在的位置进行交换* 4.相遇后则把基准数和左、右指针重合的位置进行交换* 5.重复1/2/3/4操作* 注意：* 如果左坐标大于右坐标位置则无法计算，必须左坐标小于右坐标。*/void quicksort(int left, int right){ int i,j,base; i = left; j = right; if (left>right) return ; // 1.第一步，定义基准数 base = a[left]; // 4.左坐标不等于右坐标时继续迭代，等于则相遇 while(left != right){ // 2.如果右边大于基准数则继续递减迭代至小于基准数停止 while(left<right && a[right]>=base) right–; // 2.1 与左指针所在位置进行交换 a[left] = a[right]; // 3.如果左边小于基准数则继续递增迭代至大于基准数停止 while(left<right && a[left]<=base) left++; // 3.1 与右指针所在位置进行交换 a[right] = a[left]; } // 4.1 左右坐标相遇替换基准数 a[left] = base; // 5.重复1.2.3.4 递归 quicksort(i, left-1); // 重复基准数左边 quicksort(left+1, j); return;}int main(){ int i,j; printf("=============快速排序==============\r\n"); printf(“请输入数量：”); scanf("%d", &n); for (i=1; i<=n; i++){ scanf("%d", &a[i]); } quicksort(1, n); printf(“快速排序结果：\r\n”); for (i=1; i<=n; i++) printf("%d “, a[i]); getchar(); getchar(); system(“pause”); return 0;}本文做为技术参考，也欢迎大神们指导和批评，希望对大家有帮助。 ...

算法原理下列动图来自@五分钟学算法，演示了快速排序算法的原理和步骤。步骤:从数组中选个基准值将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置递归的对分列两边的数组再排序代码实现function quickSort($arr){ $len = count($arr); if ($len <= 1) { return $arr; } $v = $arr[0]; $low = $up = array(); for ($i = 1; $i < $len; ++$i) { if ($arr[$i] > $v) { $up[] = $arr[$i]; } else { $low[] = $arr[$i]; } } $low = quickSort($low); $up = quickSort($up); return array_merge($low, array($v), $up);}测试代码:$startTime = microtime(1);$arr = range(1, 10);shuffle($arr);echo “before sort: “, implode(’, ‘, $arr), “\n”;$sortArr = quickSort($arr);echo “after sort: “, implode(’, ‘, $sortArr), “\n”;echo “use time: “, microtime(1) - $startTime, “s\n”;测试结果:before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10use time: 0.0009009838104248s时间复杂度快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。1) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。2) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。参考资料快速排序十大经典排序算法动画与解析感谢您的阅读，觉得内容不错，点个赞吧 ????原文地址: https://shockerli.net/post/qu… ...

文章包含多个可交互案例，可通过博客原文实时查看案例在学习了常用的排序算法之后，打算用动画Demo来生动形象的展现它们。这里包含6种排序算法，其中一半是简单算法，另一半是高级算法:冒泡排序选择排序插入排序~归并排序希尔排序快速排序冒泡排序这可能是最简单的一种，但是速度非常慢。 假设我们按照棒球运动员的身高来排列队列。从最左边开始。比较两个球员如果左边的高一些，就换掉。否则,不做任何操作。向右移动一个位置点击运行案例选择排序也从最左边开始。寻找从当前位置到右边的最矮球员将最矮球员与当前位置的球员交换向右移动一个位置点击运行案例插入排序在大多数情况下，这是基础排序方法中的最佳方法。它的速度是泡泡排序的两倍。 而具体步骤比上面的排序稍微复杂一些。从左边的开始。部分排序左球员选择第一个未排序的球员作为标记球员将比标记球员矮的球员移到右边将标记的球员插入到第一个移动过位置的球员的前一个位置。点击运行案例合并排序合并排序算法的核心是两个已经排序的数组的合并和递归。 如图所示，主要步骤如下:将数字分成两部分合并两部分点击运行案例希尔排序“Shell排序”的名称是以发现它的Donald Shell命名的。它基于插入排序，但是增加了一个新特性，从而极大地提高了插入排序的性能。 主要步骤将数组按区间(例如3)划分为若干组，并对它们进行一直排序，直到所有元素都被划分和排序为止。缩小区间，继续进行分割和排序，直到区间变为1。点击运行案例快速排序在大多数情况下，这是最快的排序。选择一个参考元素(最右边的元素)将数组划分为左子数组(比参考元素小的所有元素)和右子数组(比参考元素大的所有元素)对左子数组和右子数组重复步骤2点击运行案例感谢你花时间阅读这篇文章。如果你喜欢这篇文章,欢迎点赞、收藏和分享，让更多的人看到这篇文章，这也是对我最大的鼓励和支持！ 同时欢迎阅读我的更多原创前端技术博客: 苏溪云的博客。

支持原文：https://tryenough.com/arithme…举个例子排序这个序列：6 1 2 7 9 3 4 5 10 8步骤1：选择一个基准数作为对比的开始值，这里选择第一个数6：步骤2、先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数。步骤3、然后交换他们变成这样子：继续执行步骤2和3，直到两个哨兵相遇，：左右两个哨兵都走到3：步骤4:将开始选择基准数字6换到中间，测试6左边的数都小于6，右边的数都大于6。完成第一次循环:第一次完成之后，再按照此方法分别对6左右两边的数列进行递归排序即可。是不是很简单。看下代码就更清晰了：void quicksort(int a[], int left,int right) { int i,j,t,temp; if(left>right) return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要，要先从右边开始找 while(a[j]>=temp && i<j) j–; //再找右边的 while(a[i]<=temp && i<j) i++; //交换两个数在数组中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //最终将基准数归位 a[left]=a[i]; a[i]=temp; quicksort(a, left,i-1);//继续处理左边的，这里是一个递归的过程 quicksort(a, i+1,right);//继续处理右边的 ，这里是一个递归的过程 }也可以这么写：/** * 快排 * @param arr * @param low * @param high * @return */ public static int[] quit(int arr[], int low, int high) { int l = low; int h = high; int key = arr[l]; //先找出一个数作为基准数（这里取数组最中间的一位） while (l < h) { while (l < h && arr[h] >= key) h –; //从后向前：寻找比基准数小的数据，如果找到，停下来 if (l < h) { //“探测”到了符合要求的数据，则交换数据，继续顺着方向寻找 arr[l] = arr[h]; l ++; } while (l < h && arr[l] <= key) l ++; //从前向后：寻找比基准数大的数据，如果找到，停下来 if (l < h) { ////“探测”到了符合要求的数据，则交换数据，继续顺着方向寻找 arr[h] = arr[l]; h –; } } arr[l] = key; if (l > low) quit(arr, low, l - 1); if (h < high) quit(arr, h + 1, high); return arr; }支持原文：https://tryenough.com/arithme… ...

导语这篇了解下快速排序。快速排序快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n2) 次比较，但这种状况并不常见。事实上，快速排序 O(n log n) 通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。步骤为：从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。维基百科中的介绍。核心的思想是使用递归，下面的动图很形象。动图演示实例<?php$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];function quickSort($arr){ $count = count($arr); if ($count < 2) { return $arr; } $leftArray = $rightArray = array(); $middle = $arr[0];// 基准值 for ($i = 1; $i < $count; $i++) { // 小于基准值，存入左边；大于基准值，存入右边 if ($arr[$i] < $middle) { $leftArray[] = $arr[$i]; } else { $rightArray[] = $arr[$i]; } } $leftArray = quickSort($leftArray); $rightArray = quickSort($rightArray); return array_merge($leftArray, array($middle), $rightArray); // 倒序 // return array_merge($rightArray, array($middle), $leftArray);}print_r(quickSort($arr));// Array ( [0] => 2 [1] => 3 [2] => 8 [3] => 16 [4] => 21 [5] => 23 [6] => 24 [7] => 32 [8] => 33 )参考资料：快速排序、PHP 快速排序算法、GIF演示排序算法。 ...

只要是个工程师，就或多或少的知道快排，其中很多人都能轻松的写出一个快排的实现。但是大家了解阮一峰快排事件吗，是否知道快排的最佳实践？本文从一个争执讲起，通过生动详实的例子让你真正了解快排。嗯，这确实是一篇炒冷饭的文章，但我希望能把冷饭炒成好吃的蛋炒饭。闲话少叙，马上开始~1. 阮一峰快排事件整个事件用一句话来概括，就是有人diss阮一峰的快排写的不对，如下图。其实从图上也看到了，这个微博并没有发酵起来，直到一篇发表在掘金上的文章《阮一峰版快速排序完全是错的》（文章已经不能访问），然后又被人提问到知乎上，整个事情才变得热闹了起来。Diss的主要点在于两个：一个是拿哨兵用的splice而不是数组下标一个是算法使用的是额外空间而不是原地分割哨兵：快排中的被选中做为比较对象的基准元素这件事情上，绝大多数同学都支持阮老师。其实，我觉得这种粗糙的批评是有问题的。有三个原因：1.1 splice已经被提及，并且时间复杂度没有量级上的区别首先，在阮一峰的快排博客的评论里，他已经提到，splice确实是有问题的，见下图。而且，即使使用了splice，时间复杂度也是O(n)+O(n)=O(n)，在量级上并没有影响。1.2 算法没有规定空间复杂度，并且极端情况下的算法问题是通病另外，快排在维基（中文|英文）的定义上只规定了时间复杂度，对于空间复杂度的定义是，中文：根据实现的方式不同而不同英文：O(n) auxiliary (naive) O(log n) auxiliary所以用空间复杂度来攻击算法是没有依据的。另外，winter在上面知乎的问题中也提及，原地快排的空间复杂度因为不是尾递归必须用栈，空间复杂度是O(log(n))，而即使快排每次都用新的空间，也无非是O(2n)=O(n)而已。当然，若是极端情况下（哨兵每次都把数组分成n-1和1个）阮老师的算法中空间复杂度会退化成O(n的平方)，不过这种情况是非原地快排的通病，而不是阮式算法的特例，所以也不能怪到阮老师头上。1.3 基于通俗易懂的定位更值得肯定阮老师的博客其实一直是通俗易懂的，我也把通俗易懂作为我自己一直的追求。这个算法可能不是没有瑕疵，但是却绝对称不上错。而我们做的也不是抨击瑕疵，而是考虑还有哪些改进的方向。阮老师的这个快排实现确实好记，包括我自己，就是通过阮老师的这个算法才算真正记住了快排。在这个基础上，我觉得这个微博发的没啥意义。2. 快速排序的复杂度分析前面我们BB了半天阮一峰快排事件，中间我们多次提到了快排的时间复杂度和空间复杂度，在本部分，我们将分析为什么它们是这样的。2.1 时间复杂度如果足够理想，那我们期望每次都把数组都分成平均的两个部分，如果按照这样的理想情况分下去，我们最终能得到一个完全二叉树。如果排序n个数字，那么这个树的深度就是log2n+1，如果我们将比较n个数的耗时设置为T(n)，那我们可以得到如下的公式[1]：T(n) ≤ 2T(n/2) + n，T(1) = 0 T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n ……T(n) ≤ nT(1) + (log2n)×n = O(nlogn) 而在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边。这时候我们的比较次数就变为=O(n的平方)2.2 空间复杂度2.2.1 原地排序原地快排的空间占用是递归造成的栈空间的使用，最好情况下是递归log2n次，所以空间复杂度为O(log2n)，最坏情况下是递归n-1次，所以空间复杂度是O(n)。2.2.2 非原地排序对于非原地排序，每次递归都要声明一个总数为n的额外空间，所以空间复杂度变为原地排序的n倍，即最好情况下O(nlog2n)，最差情况下O(n的平方)对于复杂度这块还想了解更详细内容的同学可以参考 《快速排序复杂度分析》3. 快排的最佳实践呢经过上面的部分，想必你对快排在前端的是是非非已经有了一个初步的了解。那么，什么是快排的最佳实践呢？3.1 最简单好记这是阮一峰老师的算法实现的变体，因为用了es6的写法，从而使得代码量变得更加精简，主体更加突出。function quickSortRecursion (arr) { if (!arr || arr.length < 2) return arr; const pivot = arr.pop(); let left = arr.filter(item => item < pivot); let right = arr.filter(item => item >= pivot); return quickSortRecursion(left).concat([pivot], quickSortRecursion(right));}3.2 更高的效率这里贴一个winter的实现，想看更多的实现，可以移步大佬们在github上的互喷地址function wintercn_qsort(arr, start, end){ var midValue = arr[start]; var p1 = start, p2 = end; while(p1 < p2) { swap(arr, p1, p1 + 1); while(compare(arr[p1], midValue) >= 0 && p1 < p2) { swap(arr, p1, p2–); } p1 ++; } if(start < p1 - 1) wintercn_qsort(arr, start, p1 - 1); if(p1 < end) wintercn_qsort(arr, p1, end);}3.3 实际情况下的优化方法刚才也说到，快排其实是存在最差情况的。实际上，在日常工作中，如果真的有这样大数据量级的优化需要，我们往往会根据实际情况对快排进行各种各样的优化。主要的思路有以下几点[3]：合理选择哨兵，尽量避免出现斜树对于重复的元素，一次性的从排来使用选择排序来处理小数组（V8中设定为10）使用堆排序来处理最坏情况的分区用从两边向中间遍历来代替从左向右遍历使用尾递归在不同的线程中并发处理问题因为本文实在有点长，这块就不再做详细的阐述，有需要的同学可以自行参阅《快速排序算法的优化思路总结》。3.总结本文从阮一峰快排事件入手，分析了快排在不同情况下的空间复杂度和时间复杂度，并给出了快排的最佳实践和优化方法。希望能对大家了解快排有所帮助。参考文档：《快速排序复杂度分析》《如何看待文章《面试官：阮一峰版的快速排序完全是错的》？》《快速排序算法的优化思路总结》 ...