最近的一次前端实习面试题。。因为没准备充分,导致在快排这一块就直接死了。。太丢人了。回来之后好好总结了下,然后写下这篇js实现快排。
原理
原理其实很简单,我们要先设一个基准数,我们一般设为第一个,然后我们从数组的两端开始找,这边我们开始节点设为low,尾节点设为high,我们从high开始往左找一个比基准数要小的数,(至于为什么要先从high开始往左查找后边我们会讲到),我们在从low开始往右找比基准数大的值,这里一定要满足low是小于high的,然后我们交换找到的两个值,然后当我们找的过程中low=high了则这个值与基准数进行交换,可以看下图的过程演示。
这样后我们第一次就结束了,可以看到基准数为9,最后一次执行完后,9左边的都比9小,右边的都比9大。这样我们第一次就完成了,有一种’二分’的思想,之后我们只要对左边和右边分别进行上述操作即可,可以轻松的用递归来实现了。
问题
为什么要从右边找,这其实很好理解,因为我们最后low=high了,找到的那个值,必须比基准小(仅限从小到大排序,且基准在左边),因为要确保左边的比基准都小。这边可以举个例子:
4 3 6 5 7
如果先从左边找的话:第一个比4大的值为6,那么我们再从右边找一个比4小的值,我们会发现是3,但是如果要找到3那么high要比low要小了,我们在low=high的时候就要交换和基准了,所以最后结果会变成
6 3 4 5 7
这样就并不能保证4左边的一定比4小,右边的比4大。
搞懂原理,代码实现就很简单了。
1 | /* |