快速排序算法原来这么简单
条评论原理简述
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。
步骤为(From Wikipedia):
- 从数列中挑出一个元素,称为”基准”(pivot)
- 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
- 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
简单实现
先上一个看起来巨简单的实现:
1 | const quickSort = (arr) => { |
解释起来就很方便,从数组里取出第0个元素作为基准数
,然后过滤数组里的元素,比基准数小的,放到left,剩下的放right。当然,要排除第0个元素本身。最后将它们连接起来,两边各自递归下去。
作为算法呢,用了两次filter其实不太划算,但比这更重要的是,这个实现占用了额外的内存空间。
原地排序(in-place)
其实原理也不太难,每次递归,都是将我们的基准数放到它最终应该在的位置。
比如对于arr = [8, 10, 6, 34, 21, 66, 32]
这样的数组,我们还是每次取第0个元素作为基准数。
初始状态:
NO. | Pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
0 | void | 8 | 10 | 6 | 34 | 21 | 66 | 32 |
将第0个元素8
作为基准数,并且把0号的位置挖出来,等待其他元素填入:
NO. | Pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
0 | void | 8 | 10 | 6 | 34 | 21 | 66 | 32 |
1 | 8 | void | 10 | 6 | 34 | 21 | 66 | 32 |
从右边开始遍历,直到找到一个小于基准数8的6
,将其放入0号坑位:
NO. | Pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
0 | void | 8 | 10 | 6 | 34 | 21 | 66 | 32 |
1 | 8 | void | 10 | 6 | 34 | 21 | 66 | 32 |
2 | 8 | 6 | 10 | void | 34 | 21 | 66 | 32 |
这时再从左边开始遍历,直到找到一个大于基准数8的10
,将其放入2号坑位:
NO. | Pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
0 | void | 8 | 10 | 6 | 34 | 21 | 66 | 32 |
1 | 8 | void | 10 | 6 | 34 | 21 | 66 | 32 |
2 | 8 | 6 | 10 | void | 34 | 21 | 66 | 32 |
3 | 8 | 6 | void | 10 | 34 | 21 | 66 | 32 |
这时再从右边开始遍历,直到找到一个大于基准数8的……没了,那就说明1号坑位就是基准数8的窝了,将它填入:
NO. | Pivot | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
0 | void | 8 | 10 | 6 | 34 | 21 | 66 | 32 |
1 | 8 | void | 10 | 6 | 34 | 21 | 66 | 32 |
2 | 8 | 6 | 10 | void | 34 | 21 | 66 | 32 |
3 | 8 | 6 | void | 10 | 34 | 21 | 66 | 32 |
4 | void | 6 | 8 | 10 | 34 | 21 | 66 | 32 |
这时候要进入到递归了,我们已经将本次的基准数归位到1号位置了,那么接下来就是要排序arr[0]和arr[2..-1],左边的就一个元素,刚好符合递归终止条件,直接return
掉就可以了。右边还有五个元素,按照上述步骤继续递归下去就OK啦~
JavaScript(ES6) 代码实现:
1 | const quickSort = (arr, left = 0, right = arr.length - 1) => { |
其中blankIndex
和pivotVal
是为了可读性添加的,为了节省点代码,也是可以省略掉的。比如两次判断,可以简化成下面这样,最后i和j相等,所以取哪个都可以。
1 | while (i < j) { |
如有疏漏,欢迎评论指出,或者前往Github提出issue~谢谢