快速排序

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

以一个数组作为示例，取区间第一个数为基准数。
|0|1|2|3|4|
| —- | —- |—-| —- | —- |
|6|3|7|4|1|
初始时，i = 0; j = 5; X = a[i] = 6

由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。

1、从j开始向前找一个比X小或等于X的数。
2、当j=4，符合条件，将a[4]挖出再填到上一个坑a[0]中。a[0]=a[4]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[4]，这怎么办了？简单，再找数字来填a[4]这个坑。
3、这次从i开始向后找一个大于X的数，当i=2，符合条件，将a[2]挖出再填到上一个坑中a[4]=a[2]; j–;
数组变为
|0|1|2|3|4|
| —- | —- |—-| —- | —- |
|1|3|7|4|7|
i = 2; j = 4; X=6
4、再重复上面的步骤，先从后向前找，再从前向后找。
5、从j开始向前找，当j=3，符合条件，将a[3]挖出填到上一个坑中，a[2] = a[3]; i++;

从i开始向后找，当i=3时，由于i==j退出。

此时，i = j = 3，而a[3]刚好又是上次挖的坑，因此将X填入a[3]。

数组变为：
|0|1|2|3|4|
| —- | —- |—-| —- | —- |
|1|3|4|6|7|

再重复上面的步骤，先从后向前找，再从前向后找。

代码实现

/**
 * 快速排序
 * @param {Array<Number>} arry 要排序的数组
 */
function quickSort(arry, left, right) {
    if (arry.length == 0) {//判断数组不为空
        return [];
    }
    let [l, r] = [left, right];
    if (l < r) {
        let temp = arry[l];//即arry[l]就是第一个坑
        while (l < r) {
            // 从右向左找小于temp的数来填arry[l]
            while (l < r && arry[r] > temp) {
                r--;
            }
            if (l < r) {
                arry[l] = arry[r]; //将arry[r]填到arry[l]中，arry[r]就形成了一个新的坑
                l++;
            }
            // 从左向右找大于temp的数来填arry[r]
            while (l < r && arry[l] < temp) {
                l++;
            }
            if (l < r) {
                arry[r] = arry[l]; //将arry[l]填到arry[r]中，arry[l]就形成了一个新的坑
                r--;
            }
        }
        arry[l] = temp;//将temp填入arry[l]的坑
        console.log(arry, l);
        // 递归调用 
        quickSort(arry, left, l - 1);
        quickSort(arry, l + 1, right);
    }
}

运行结果：

quickSort([72, 6, 57, 88, 60, 42, 83, 73, 48, 85], 0, 9);
[ 48, 6, 57, 42, 60, 72, 83, 73, 88, 85 ] 5
//第一次排序72为观察数，分界为5；左边都是小于，右边都是大于
[ 42, 6, 48, 57, 60, 72, 83, 73, 88, 85 ] 2
//数组左边0-5继续续排序，48为观察数，分界为2
[ 6, 42, 48, 57, 60, 72, 83, 73, 88, 85 ] 1
//数组左边0-2继续排序，42为观察数，分界结果为1，
//这时再递归发现1<1-1;结束递归，开始右边排序
[ 6, 42, 48, 57, 60, 72, 83, 73, 88, 85 ] 3
//右边排序其实是开始于[ 42, 6, 48 , 57, 60, 72, 83, 73, 88, 85 ] 这个数组，57为观察数，排序区间为3-5，发现已经是正序，继续递归上次的右边排序
[ 6, 42, 48, 57, 60, 72, 73, 83, 88, 85 ] 7
//右边排序其实是开始于[ 48, 6, 57, 42, 60, 72, 83, 73, 88, 85 ]这个数组基于分界点5的右边数组，83为观察数，排序区间为6-9，排序分界结果为7
[ 6, 42, 48, 57, 60, 72, 73, 83, 85, 88 ] 9
//再次递归，右边已正序

复杂度

时间复杂度：O(nlogn)
空间复杂度：快速排序使用递归，递归使用栈，因此它的空间复杂度为O(logn)
稳定性：快速排序无法保证相等的元素的相对位置不变，因此它是不稳定的排序算法