快速排序算的上目前使用最广泛的算法了,之所以它这么受欢迎,是因为它是原地排序,而且将长度为 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 查看源码