快速排序法

在看阮一峰老师的快速排序法时，总能看到网上各种各样的吐槽文章，都说阮老师的实现方法有问题。那么，具体问题到底在哪呢？

本着学习的心态，查找了一些相关的文章和实现方法，发现大家都是不约而同的采用阮老师的实现方法。我在阮老师的基础上做了一点改进，如下。

原理

(1)选基准：选择数组里面的任意一个元素作为基准数(我以中间元素为例)。

(2)划分数组：
小于基准数的元素放在’基准’左边；
大于基准数的元素放在’基准’右边；
等于基准数的元素和’基准’放在一起。

(3)递归：对’基准’左边和右边两个子集，不断重复第一步和第二步，直到所有子集只剩一个元素为止。

具体实现

function quickSort(arr) {
    if (arr.length <= 1) {        //递归出口，当数组长度小于等于1时返回
        return arr;
    }

    var temple = Math.floor(arr.length / 2);
    var flag = arr.splice(temple, 1)[0];
    var left = [],
        middle = [flag],
        right = [];

    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < flag) {
            left.push(arr[i]);
        }else if (arr[i] > flag) {
            right.push(arr[i]);
        }else {
            middle.push(arr[i]);
        }
    }

    return quickSort(left).concat(middle, quickSort(right));
}

var arr = [2, 5, 23, 10, 7, 8, 12, 7, 6];
var newArr = quickSort(arr);
console.log(newArr);      //[2, 5, 6, 7, 7, 8, 10, 12, 23]

待排序数组每次调用quickSort方法时，都会被分成左，中，右三个数组。对左边和右边的数组再用相同的方法进行排序，最后返回排序完成的数组。

总结

我和阮一峰老师快排的不同主要在于多了一个middle数组来接收和’基准’一样的元素。

用递归方法来实现时，需要考虑到每次进行操作时共同点在哪（即找规律，找公式）。

还要考虑到当满足一定条件时跳出（即出口），否则程序将会陷入死循环。

快速排序法

原理

具体实现

相关方法：

总结