QuickSort Dijkstra 3-Way Partitioning

思想

原始的 2-Way 快排在遇到大量重复数据时会退化为 O(n^2),为了解决这个问题,3-Way 快排被提出了。通过将区间分割为“小于”、“等于”和“大于”(基准数)三个部分,获得了趋近 O(nlogn) 的复杂度。不同于 2-Way 快排的是,我们在此选取一个基准数的值,而非一个基准元素。

(小声逼逼:当然为了方便也可以直接改进 2-Way 快排,在每一次基准数归位后遍历全区间元素,将等于基准数的元素交换到基准数旁边,也能获得等价的三个区间。当然,效率相对于 3-Way 快排有所下降,代码实现的复杂度也上升了。)

使用 i 下标表示“小于”区间的上界;使用 q 下标表示“等于”区间的上界;使用 j 下标表示“大于”区间的下界。

  1. 选取一个元素的值作为基准数值
  2. 判断 arr[q]pivot 的关系: 如果小于 pivot,交换 arr[i]arr[q]q 自增,i 自增 如果大于 pivot,交换 arr[j]arr[q]q ** 不变 **,j 自减 如果等于 pivotq 自增
  3. 重复步骤 2,直至 qj 相遇。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static void swap(int arr[], int a, int b)
{
/**
* Due to Java doesn't have reference, we can use XOR to swap the values
*/
if (a != b)
{
arr[a] ^= arr[b];//a = a^b
arr[b] ^= arr[a];//b = b^a^b = a
arr[a] ^= arr[b];//a = a^b^a = b
}
}
public static void quickSort(int f[], int lo, int hi)
{
if (lo >= hi)
return;

int pivot = f[(int)Math.random() % (hi - lo + 1) + lo];//randomize pivot

/**
* i "less" upper bound
* j "more" lower bound
* q "equal" upper bound
*
* ##less## ->i ##equal## ->q ##unknown## j<- ##more##
*/

int i = lo, j = hi, q = lo;

//partition
while (q <= j)
{
if (f[q] < pivot)
swap(f, q, i++);
else if (f[q] > pivot)
swap(f, q--, j--);//the exchanged value need to be check, so we q--
++q;
}
//recursion
quickSort(f, lo, i);//left
quickSort(f, j+1, hi);//right
}