JavaScript快速排序递归版与非递归版实现

快速排序概述

快速排序(Quiksort)是一种通过基准划分区块并不断交换左右项的排序方式，其采用了分治法，减少了交换的次数。平均算法复杂度：O(NlogN)。

步骤是：

1. 先找到一个基准点(pivot)，为了便于理解一般是位于数组中间的那一项。
2. 逐个循环数组将小于基准的项放左侧，将大于基准的数放右侧。一般通过交换的方式来实现。
3. 将基点左侧全部项和基点右侧全部项分别通过递归(或遍历)形式重复第1项，直到所有数组都交换完成。

快速排序执行过程分析

图1 快速排序执行过程

从上图可以看出：

1. 先找到基准项。比如是中间项(根据left与right之和除以2), 得到基准值arr[2] = 3。
2. 再将基准项左侧大于3的项挪到右侧，将右侧小于3的项挪至左侧。得到 [2,1,3,5,4]
3. 开始新的分区。基准项左侧2,1为新的分区，右侧5,4为新的分区。将它们分别按照1、2步骤进行处理。
4. 2,1位于数组的第0,1项,得到中间项0，基准值为2，交换后得到1,2
5. 5,4位于数组的第3,4项,中间项(3+4)/2取整得到3，基准值为5，交换后得到4,5
6. 全部分区都按照1，2步骤完成后，得到最后的排序结果

快速排序实现

1、递归新建数组版。无需交换，每个分区都是新数组。

图2 快速排序递归新建数组版

这个版本最容易理解，先找准基准项(用中间项表示)，把小于基准项的全添加到左侧新数组，大于等于基准项的放在右侧新数组，然后分别递归调用左、右新数组，再重复第一步找基准项，再据此一分为二。直到把数组项拆分为一个个length为1的数组。最后自左往右将最小值与中间项和最大值连接起来。这里利用到JS语法中的concat，可以有效地连接数组。

这个版本好处是代码简单，非常容易理解，除了要注意基准项不要放入到left和right，而是concat到结果即可。但是带来的问题是要新建很多数组，所以这个方式并不是很优的方式。

2、标准递归版本。需要交换，无需新建数组。

图3 标准递归版本

图4 标准递归版本执行结果

这个版本好处是无需新建数组，而整个排序过程都是基于原数组的位置交换。其机制和排序过程与上一个方案基本类似(不同在于新方案的基准项可交换会，因此递归有时需要带上基准项)，直到把所有分区都比较过后就表示已经排序完成。

其排序过程为：

1. 先找到基准项，这里以中间项表示，pivot=3。left表示最左侧位置，i一开始取值left，right表示最右侧位置,j取值为j, 因此i = 0, j = 4。
2. 自左往右逐个查找大于基准项的数，同时自右往左逐个查找小于基准项的数，类似两边收拢朝中间查找，到基准项停止。当左侧遇到大的数，右侧遇到小的数字，将左右两项交换，同时i增1位，j减1位，缩小范围继续查找，直到将全部小的数移到左侧，大的数字移到右侧。
3. 上一趟交换完成之后，左侧全部小于基准项，右侧全部大于基准项。这时，将基准左侧第1位到基准项-1项放入递归按照步骤1、2进行交换排序，再将基准右侧第1项到最后项放入递归按照步骤1、2进行交换排序。在递归时，有时左侧或者右侧没有可交换的项，这时就与基准项进行了交换，那需要将基准项位置一并传入递归。
4. 分区递归完成后排序完成。

3、非递归版本。需要交换，无需新建数组，利用stack或queue遍历。

图5 快速排序非递归版本

非递归版本基于标准递归版本，交换逻辑与排序规则完全一样。所不同的是，将递归改为栈或队列的循环。不同点是：

1. 首先在交换排序的外循环加入一个stack，将初始的left,right添加进去
2. 如果stack不为空，则将left与right取出，分别赋值给i和j。数组方法pop()表示从后开始取,shift()从前开始取。
3. 在之前递归调用处，分别用push成员来替换。也就是当需要递归时说明要继续交换循环，则给stack添加成员，让循环继续即可。中止条件是stack为空，也就是无需递归时结束。

总结

快速排序是一种相对巧妙的排序方式，相对选择、插入、冒泡来讲效率要高，也要稍微复杂一些。其交换过程也有点类似冒泡，但是不像冒泡两两逐个交换，而是根据基准值比较大小按需要来交换，然后递归分区排序，这样以来交换就减少了。但快排并不稳定，如果遇到已排过序或全一样的数字这种最坏情况那跟冒泡等一样了。

PS：请对比之前关于选择、插入、冒泡三种冒泡排序的文章。