具有3路分区的QuickSort是什么？
画一个数组：
3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0
两个分区Quick Sort将选择一个值，比如说4，并在数组的一侧放置大于4的每个元素，在另一侧放置少于4的每个元素。像这样：
3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5
一个三分区快速排序将选择两个值进行分区并以这种方式拆分数组。让我们选择4和7：
3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9
这只是常规快速排序的一个小变化。
您继续对每个分区进行分区，直到对数组进行排序。运行时在技术上是nlog3（n），它与常规快速排序的nlog2（n）略有不同。
如果你真的使用Akra-Bazzi formula来计算数学，将分区数作为参数，然后对该参数进行优化，你会发现e（= 2.718 ...）分区提供了最快的性能。然而，在实践中，我们的语言结构，cpus等都针对二进制操作进行了优化，因此标准分区为两组将是最快的。
我认为3路分区是由Djstrka完成的。
想想一个带有{ 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }元素的数组。
基本上你设置了3个分区：小于，等于和大于某个分支。等于分区不需要进一步排序，因为它的所有元素已经相等。
例如，如果我们选择第一个3作为枢轴，那么使用Dijkstra的三向分区将排列原始数组并返回两个索引m1和m2，使得索引小于m1的所有元素将低于3，所有索引大于或等于m1且小于或等于m2的元素将等于3，所有索引大于m2的元素将大于3。
在这种特殊情况下，得到的数组可能是{ 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }，值m1和m2将是m1 = 2和m2 = 3。
请注意，结果数组可能会根据用于分区的策略而改变，但数字m1和m2将是相同的。
我认为它与Dijkstra分区的方式有关，其中分区的元素小于，等于和大于枢轴。只有较小和较大的分区必须递归排序。您可以在the walnut上看到交互式可视化并使用它。我在那里使用的颜色是红色/白色/蓝色，因为分区方法通常被称为“荷兰国旗问题”
3路快速排序基本上将数组分为3个部分。第一部分小于枢轴，第二部分等于枢轴，第三部分大于枢轴。它是线性时间分割算法。这个分区类似荷兰国旗问题。
//code to implement Dijkstra 3-way partitioning
package Sorting;
public class QuickSortUsing3WayPartitioning {
private int[]original;
private int length;
private int lt;
private int gt;
public QuickSortUsing3WayPartitioning(int len){
length = len;
//original = new int[length];
original = {0,7,8,1,8,9,3,8,8,8,0,7,8,1,8,9,3,8,8,8};
}
public void swap(int a, int b){ //here indexes are passed
int temp = original[a];
original[a] = original[b];
original[b] = temp;
}
public int random(int start,int end){
return (start + (int)(Math.random()*(end-start+1)));
}
public void partition(int pivot, int start, int end){
swap(pivot,start); // swapping pivot and starting element in that subarray
int pivot_value = original[start];
lt = start;
gt = end;
int i = start;
while(i <= gt) {
if(original[i] < pivot_value) {
swap(lt, i);
lt++;
i++;
}
if(original[i] > pivot_value) {
swap(gt, i);
gt--;
}
if(original[i] == pivot_value)
i++;
}
}
public void Sort(int start, int end){
if(start < end) {
int pivot = random(start,end); // choose the index for pivot randomly
partition(pivot, start, end); // about index the array is partitioned
Sort(start, lt-1);
Sort(gt+1, end);
}
}
public void Sort(){
Sort(0,length-1);
}
public void disp(){
for(int i=0; i<length;++i){
System.out.print(original[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
QuickSortUsing3WayPartitioning qs = new QuickSortUsing3WayPartitioning(20);
qs.disp();
qs.Sort();
qs.disp();
}
}