快速排序

快速排序是最效率极高的一种排序方法，正因为它效率高，所以也受到了面试官的青睐，同样成了程序员必会的内容。O(∩_∩)O哈哈~

它的思想是选一个基准，然后把小于基准的值放在左边，大于基准的值放在右边（假设从小到大排序）。然后分别递归左边和右边的部分，当所有的递归完毕后就是已经排好序的结果了。

市面上流传最广的快速排序是阮一峰老师博客中写的，我们这笔直接拿过来记录一下，原文在这里。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

阮一峰老师的快速排序选择的是最中间的元素作为基准，左边和右边的都定义了一个新的数组来接收，最后把数组连接起来。这个快速排序的优点是思路很明确，缺点是因为定义了新的数组所以空间复杂度比较高。那如何降低空间复杂度呢？其实只要操作元数组就可以了，这里给出另一种快速排序的实现：

function sort(arr,low,high){
    // 用i和j记录下初始的最低位和最高位 temp记录下基准 这里假设是起始位置
    var i = low,j = high,temp = arr[i];
    while (i < j) {// 如果低位的小于高位的时候那么对立面的值进行交换
        while (i < j && temp <= arr[j]) {// 扫描右边 如果右边的的有比temp小的需要交换
            j--;
        }
        // 判断i < j为了避免不需要交换的情况 下同
        if (i < j) {// 如果右边的有交换的情况则放在左边的位置
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < temp) {// 扫描左边 如果左边的的有比temp大的需要交换
            i++;
        }
        if (i < j) {// 如果左边的有交换的情况则放在有边的位置
            arr[j] = arr[i];
            j--;
        }
    }
    // 上面循环结束的时候i位置左边的都比temp小 右边的都比temp大 这只temp给当前位置
    arr[i] = temp;
    if (low < i) {
        sort(arr,low,i - 1);// 递归遍历左侧
    }
    if (j < high) {
        sort(arr,j + 1,high);// 递归遍历右侧
    }
    return arr;
}

function quickSort(arr){// 为了给sort传初始值 而封装的一层
    return sort(arr,0,arr.length - 1);
}

var arr = [8,3,10,7,5,6,4,2,1,9];
quickSort(arr);
console.log(arr);// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

这个快速的时间复杂度要比阮一峰老师的稍微低一点，不过比阮一峰老师的快速排序稍微难理解一点。其实我们在《JavaScript数据结构与算法》读书笔记一文中也有快速排序的记录，那个快速排序与这个有一点点的不同，那个排序的基准选择的中间值，然后每次循环直接交换左侧的和右侧的元素，整体思路相差无几，感兴趣的可以在那篇文章中搜一下快速排序。