排序算法——快速排序

快速排序，可以称得上是21世纪最伟大的算法之一，它的性能也是相当不错的，它的平均时间复杂度是O(nlogn)是一种非常高效的算法，几乎我们每门语言当中的系统排序算法中都有一部分是基于快速排序算法实现的。

快速排序的思想也很简单，就是每一次，都将一个数送到它最终的位置上面，并且它前面的数都比它小，后面的数都比它大，每一轮都这样然后递归执行，最终就会实现整个数组完全有序的状态。

当然快排的优点肯定是平均性能好，但是快排对于已经比较接进完全有序的数组，会暴露出自己的问题，这时它会达到自己的最坏的性能，目前解决这种问题的方法也有很多，当然只能减少这中情况的发生，并不能避免，但在数学期望的角度上，会让它的性能更优，具体做法：

1.我们可以在快速排序一个数组之前，运行一个算法来打乱原数组
2.我们可以每次选定标准的时候，并不选择第一个数，而是随机选定一个待排序范围内的数字

我们现在就可以自己实现一个二路快速排序算法：

/**
 * Created by linSir on 17/2/10.
 */
function paration(list, l, r) {
    var first = list[l];
    var left = l;
    var right = r;
    var temp;
    while (left < right) {
        while (list[right] > first && left < right) {
            right--;
        }
        if (left < right) {
            list[left] = list[right];
            left++;
        }
        while (list[left] <= first && left < right) {
            left++;
        }
        if (left < right) {
            list[right] = list[left];
            right--;
        }
        list[left] = first;
    }
    return left;
}

function quickSort(list, l, r) {
    if (l >= r) {
        return;
    }
    var temp;
    temp = paration(list, l, r);
    console.log(temp);
    quickSort(list, l, temp - 1);
    quickSort(list, temp + 1, r);
    return list;

}


var list = [3, 1, 2, 4, 5, 6, 7];
console.log(quickSort(list, 0, 6));

结果：

运行效果图

现在我们所写的算法就是基本的快速排序算法了。