由浅入深快速排序算法（JS实现）

前言

前段时间，前端圈子因为一篇文章面试官：阮一峰版的快速排序完全是错的
，而浮躁了起来，而本文作者也因为不当的表述而遭受很多人的批评与嘲笑。同时，我们也发现了很多前端同学阅读文章的时候，没有进行完整的思考，就过于相信文章所说的观点过于的肯定与信赖（这种事情我也没有少犯）。今天，我们就一步一步的深入快速排序算法的实现，看看阮一峰老师是否真像文中所说的是完全错误的呢。

快速排序的算法

快速排序使用分治法策略来把一个序列）分为两个子序列
步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序算法的实现

从上面的算法说明我们可以知道，快速排序本质是通过分治策略通过基准值数组拆分成两部分，一部分永远比基准值小，另外一部分永远比基准值大。这时候在继续在拆分的部分中取基准值继续将已经拆分的部分再次拆分成两部分，直到不可在继续拆分下去。这个时候数组的顺序就已经完成了排序操作。

我们根据上面描述，就可以完成下面这样的代码实现（类阮一峰老师代码实现）

var quickSort = function(arr){
    // 如果数组不可在分，则跳出递归
    if(arr.length <= 1){
        return arr;
    }
    // 基准值取数组第一个
    var pivot = arr[0];
    var left = [];
    var right = [];
    for(var i = 1; i < arr.length; i++){
        // 小于等于基准值的放在左边,大于基准值的放在右边
        if(arr[i] <= pivot){
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
   // 对左右数组递归quickSort，最后合并成一个完整的数组
    return quickSort(left).concat(pivot).concat(quickSort(right));
}

在这段代码中，我们可以看到，这段代码实现了通过pivot区分左右部分，然后递归的在左右部分继续取pivot排序，实现了快速排序的文本描述，也就是说该阮老师的算法实现本质是没有问题的。

虽然阮老师的实现方式非常的易于理解。不过该实现也是有可以改进的空间，在这种实现中，我们发现在函数内定义了left/right两个数组存放临时数据。随着递归的次数增多，会定义并存放越来越多的临时数据，需要Ω(n)的额外储存空间。

因此，像很多算法书中，都使用了原地（in-place）分区的版本去实现快速排序，我们先介绍什么是原地分区算法。
原地（in-place）分区法正如其名，即借由移动小于等于pivot的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素，也不会产生临时数组，从而增加空间复杂度。

原地（in-place）分区算法描述

1. 从数列中挑出一个元素，称为"基准"（pivot），数组第一个元素的位置作为索引。
2. 遍历数组，当数组数字小于或者等于基准值，则将索引位置上的数与该数字进行交换，同时索引+1
3. 将基准值与当前索引位置进行交换

通过以上3个步骤，就将以基准值为中心，数组的左右两侧数字分别比基准值小或者大了。这个时候在递归的原地分区，就可以得到已排序后的数组。

原地分区算法实现

// 交换数组元素位置
function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

function partition(array, left, right) {
    var index = left;
    var pivot = array[right]; // 取最后一个数字当做基准值，这样方便遍历
    for (var i = left; i < right; i++) {
        if (array[i] <= pivot) {
            swap(array, index, i);
            index++;
        }
    }
    swap(array, right, index);
    return index;
}

因为我们需要递归的多次原地分区，同时，又不想额外的地址空间所以，在实现分区算法的时候会有3个参数，分别是原数组array，需要遍历的数组起点left以及需要遍历的数组终点right
最后返回一个已经排好序的index值用于下次递归，该索引对应的值一定比索引左侧的数组元素小，比所有右侧的数组元素大。

再次基础上我们还是可以进一步的优化分区算法，我们发现

1. <=pivot可以改为<pivot,这样可以减少一次交换

原地分区版快速排序实现

function quickSort(array) {
    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    function partition(array, left, right) {
        var index = left;
        var pivot = array[right]; // 取最后一个数字当做基准值，这样方便遍历
        for (var i = left; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, index, i);
                index++;
            }
        }
        swap(array, right, index);
        return index;
    }

    function sort(array, left, right) {
        if (left > right) {
            return;
        }
        var storeIndex = partition(array, left, right);
        sort(array, left, storeIndex - 1);
        sort(array, storeIndex + 1, right);
    }

    sort(array, 0, array.length - 1);
    return array;
}

该原地分区算法实际运行动图如下：

quickSort.gif

除此之外，原地分区算法还有各种各样其他的实现，开头提到的文章中则使用了双向扫描的原地分区算法，这里都不在赘述了。

参考文章

维基百科:快速排序