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` 自减
如果等于 `pivot`,`q` 自增
3. 重复步骤 2,直至 `q`、`j` 相遇。

## 实现
“`
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
}
}
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
}
“`

CC BY-SA 4.0 QuickSort Dijkstra 3-Way Partitioning by 小小泥娃 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.