一天一算法 - 快速排序

快速排序算的上目前使用最广泛的算法了，之所以它这么受欢迎，是因为它是原地排序，而且将长度为 N 的数组排序所需的时间和 NLogN 成正比。快速排序一般都会比归并排序和希尔排序要快，下面来看看快速排序的基本思想。

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，两部分独立排序。快速排序和归并排序是不同的。归并排序的思想是将两个子数组分别排序，然后再归并两个子数组从而确保整个数组是有序的。而快速排序却不是这样，在快速排序中，只要两个子数组有序了，那么整个大数组也就是有序的了，不需要在进行归并。

快速排序的步骤主要如下：

1. 选择一个基准元素 a[j]
2. 保证 a[low] - a[j-1] 中的所有元素都不大于 a[j]
3. 保证 a[j+1] - a[high] 中的所有元素都不小于 a[j]

通过上述步骤可以看出，快速排序的每一次切分都会将一个元素放置在其最终位置上，所以只要递归不断的切分数组，直到每个子数组中都只包含一个元素，那么整个大数组自然而然也就变成有序的了。

首先，来看看切分函数

var partition = function(arr, low, high) {
    var i = low,
        j = high+1,
        value = arr[low];

    while(true) {
        while(arr[++i] < value) {
            if (i === high) {
                break;
            }
        }

        while(arr[--j] > value) {
            if (j === low) {
                break;
            }
        }

        if (i >= j) {
            break;
        }
        swap(arr, i, j);
    }

    swap(arr, low, j);
    return j;
};

在切分函数中，首先选择 a[low] 为基准元素，设置游标 i 让其从 low 开始递增，用于查找比 a[low] 大的元素，一旦查找到就跳出循环。

设置游标 j， 让其从 high 开始递减，用于查找比 a[low] 小的元素，一旦查找到就跳出循环。

当 i < j 时，将 i 和 j 位置的元素交换。当 i >= j 的时候，说明在 j 这个位置，说明当 index <= j 的时候，元素都小于或者等于基准元素，当 index > j 都大于基准元素，所以我们需要在跳出大循环的时候将基准元素与 j 位置的元素进行交换，这也就意味着基准元素在此次循环过程中找到了自己的基准位置。

其实快速排序的核心也就是上面的切分函数，由于在切分过程中返回了一个位置 j，所以接下来的过程也就简单了，只需要在切分 [low, j-1]和 [j+1, high] 区间的元素即可。

var quickSortRes = function(arr, low, high) {
    if (high <= low) {
        return;
    }

    var j = partition(arr, low, high);
    quickSortRes(arr, low, j-1);
    quickSortRes(arr,j+1, high);
};

利用快速排序，排序 100 0000 个元素的数组，在我电脑上仅需要 120ms 左右，可见它比归并排序要快。不过，值得注意的是，使用快速排序有一个致命的缺点，那就是如果你使用快速排序去排序一个已经有序的数组时，它的运行时间会与 N ^ 2 成正比，反正在我电脑上运行的时候抛出了栈溢出异常。所以使用快速排序最好的一个办法就是在使用前先把数组打乱。

虽然快速排序性能已经很高了，但是我们仍然有提高快速排序性能的方法。比如之前提到过的插入排序，在小数组排序的时候我们可以将快速排序替换为插入排序，这样会进一步提升快速排序的性能，改进后的代码像下面这样。

var quickSortRes = function(arr, low, high) {
    if (high <= low) {
        return;
    }

    if((high - low +1) < 10) {
        insertionSort(arr,low, high);
        return;
    }

    var j = partition(arr, low, high);
    quickSortRes(arr, low, j-1);
    quickSortRes(arr,j+1, high);
};

具体多大的小数组换成插入排序呢？一般对于[5,15] 之间规模的小数组都是比较不错的。上述改进在我电脑上将快速排序的时间提升了 0 - 20ms 不等。咋一看好像并没有改进多少，但是我认为就算能够提升 1ms ，那么我们所做的努力都是值得的！

对于拥有大量重复元素的数组来说，我们仍有改进快速排序的方法，这个算法就是 Dijkstra 提出的 "三向切分快速排序"。 它从左到右遍历数组一次，维护一个指针 lt 使得 a[low ... lt-1] 都小于 v，一个指针 gt 使得 a[gt+1 ... high] 都大于 v，一个指针 i 使得 a[lt ... i-1] 中的元素都等于 v， a[i ... gt] 中的元素还未确定。

其处理过程如下：

1. a[i] 小于 v， 将 a[lt] 与 a[i] 交换，将 lt 和 i 都加 1
2. a[i] 大于 v， 将 a[gt] 和 a[i] 交换，将 gt 减 1
3. a[i] 等于 v， 将 i 加 1

var quick3Way = function(array, low, high) {
    if (high <= low) {
        return;
    }
    var lt = low,
        i = low + 1,
        gt = high,
        v = array[low];

    while (i <= gt) {
        var cmp = array[i] - v;
        if (cmp < 0) {
            swap(array, lt++, i++);
        } else if (cmp > 0) {
            swap(array, i, gt--);
        } else {
            i++;
        }
    }
    
    quick3Way(array, low, lt - 1);
    quick3Way(array, gt + 1, high);
};

经过我的测试，发现当数组中有大量重复元素的时候，三向快速排序的性能提升十分显著，比如说我向一个数组中插入 100万 个 1 的时候，三向排序耗时 5ms 左右，而普通的快速排序则需要 35ms 左右。所以当我们在为人的年龄或者等级之类的属性排序时，最好使用三向快速排序！

---

你可以在 我的 Github 查看源码