快速排序算的上目前使用最广泛的算法了，之所以它这么受欢迎，是因为它是原地排序，而且将长度为 N 的数组排序所需的时间和 NLogN 成正比。快速排序一般都会比归并排序和希尔排序要快，下面来看看快速排序的基本思想。
快速排序是一种分治的排序算法。它将一个数组分成两个子数组，两部分独立排序。快速排序和归并排序是不同的。归并排序的思想是将两个子数组分别排序，然后再归并两个子数组从而确保整个数组是有序的。而快速排序却不是这样，在快速排序中，只要两个子数组有序了，那么整个大数组也就是有序的了，不需要在进行归并。
快速排序的步骤主要如下：
- 选择一个基准元素 a[j]
- 保证 a[low] - a[j-1] 中的所有元素都不大于 a[j]
- 保证 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] 中的元素还未确定。
其处理过程如下：
-
a[i]小于v， 将a[lt]与a[i]交换，将lt和i都加 1 -
a[i]大于v， 将a[gt]和a[i]交换，将gt减 1 -
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 查看源码
