快速排序

JavaScript实现

网上大部分都是基于这种写法：

//JavaScript
function quicksort(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));
}

但是这种个写法很明显是需要0(n)的额外空间的，那如果我们基于原地分区该怎样实现呢？

partition的不同版本

记得在学习数据结构的时候，我们是下面这样实现的，通过两个指针low,high从两端往中间逼近。

//C++
int partition(int arr[], int low, int high){
    //直接选取第一个元素为枢轴
    int pivot = arr[low];
    while(low < high) {
        //注意下面的while内部也要进行越界判断！
        while(low < high && arr[high] > pivot) { 
            high--;
        }
        while(low < high && arr[low] <= pivot) {
            low++;
        }
        arr[low] = pivot;
        return low;
    }
}

void quicksort(int arr[], int low, int high) {
    int loc = 0;
    if(low < high) {
        loc = partition(arr, low, high);
        quicksort(arr, low, loc - 1);
        quicksort(arr, loc + 1, high);
    }
}

因为partition函数是快排的核心，所以partition的优化方法有很多，可以分为两大类，单向扫描版本和双向扫描版本，上面就是双向扫描的例子，方法还是很好理解的。《算法导论》那本书上还提出了另一种基于单向扫描的partition方法，如下：

int partition(int arr[], int low, int high){    
    x = arr[high]; //这里直接选取最后一个元素为比较元素，后面还可以根据random来改进
    int i = low - 1; //这个i为慢速移动下标，必须为比最小的下标p小1，否则两个元素的序列（比如2，1）就无法交换
        int j = low;
    for(; j < high; j++) {
        if(arr[j] <= x){
            swap(&arr[++i], &arr[j]);
        }
    }
    swap(&arr[i+1], &a[j]);
    return i + 1;
}

quicksort(int arr[], int low, int high) {
    if(low < high) {
        int index = partition(arr, low, high);
        quicksort(arr, low, index - 1);
        quicksort(arr, index + 1, high);
    }
}

算法示意图如下：

单向扫描优化版本

可以优化的地方：

1. <=x 改为<x，减少交换次数
2. i的初始值直接设为low
3. i = j时的交换是多余的可以优化掉

//cpp优化版本
int partition (int a[], low, high) {
    int x = a[high];
    int i = low;
        int j = low;
    for(; j < high; j++) {
        if(a[j] < x) {
            if(i != j){
                swap(&a[i], &a[j]); 
            }
                        i++;
        }
    }
    swap(&a[i], &a[j]);
    return i;
}

随机化版本

之前的方法都是基于一个前提：所有的排列都是等概率的，但是实际工程中并不会总是成立。有时候我们可以通过在算法中引入随机性，从而使得算法对所有的输入都能获得较好的期望，比如针对一个几乎有序的输入序列进行排序的问题。很多人都选择随机化版本作为大数据输入情况下的快排。
思路如下:

randomPartition(arr, low, high){
    i = random(low, high);
    swap(a[i], a[high]);
    return partition(arr, low, high);
}

randomQuicksort(arr, low, high) {
    if(low < high){
        int index = randomPartition(arr, low, high);
        randomQuicksort(arr, low, index - 1);
        randomQuicksort(arr, index + 1, high)
    }
}

其实就是多了最开始的枢轴随机化一个数这步，然后再与最后的元素交换，后面都一样一样滴。

单向扫描版本的JavaScript实现

//js
function quicksort (arr) {
    function swap (arr, m, n) {
        var tmp = arr[m];
        arr[m] = arr[n];
        arr[n] = tmp;
    }
    function partition (arr, low, high) {
        var x = arr[high];
        var i = low - 1;
        for(var j = low; j < high; j++) {
            if(arr[j] <= x){
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    function sort (arr, low, high) {
        if(low < high) {
            var pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
        return arr;
    }

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

同理，其中的partition也可以优化

    function partition (arr, low, high) {
        var x = arr[high];
        var i = low;
        for(var j = low; j < high; j++){
            if(arr[j] < x){
                if(x != j){
                    swap(arr, i, j);
                    i++;
                }
            }
        }
        swap(arr, i, high);
        return i;
    }