3分区快速排除

Question

什么是3分区快速排序？

Answer 1

图片数组：

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0 

一个两个分隔快速排序将挑选一个值，即4，并把每一个元素大于4的阵列的一侧而另一边的每个元素小于4。像这样：

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5 

一个3分区快速排序就挑两个值进行分区并分裂阵列了这种方式。让我们选择4和7：

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9 

这只是普通快速排序上的轻微变化。

您继续对每个分区进行分区，直到对数组进行排序。 运行时在技术上是nlog （n），它与常规快速排序的记录（n）之间的变化非常小。

Answer 2

http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

参见：

http://www.sorting-algorithms.com/quick-sort-3-way

我认为面试问题的版本也非常有趣。它要求，are there four partition versions of quicksort ...

Answer 3

如果您真的使用Akra-Bazzi formula将分区数作为参数进行数学运算，然后对该参数进行优化，您会发现e（= 2.718 ...）分区提供了最快的性能。然而，在实践中，我们的语言结构，cpus等都针对二进制操作进行了优化，因此标准分区到两个集合将是最快的。

Answer 4

我在3路分区是由Djstrka。

想一想与元素的数组{3,9，4，1，2，3，15，17，25，17}

基本上设置了3个分区，小于，等于，和更大的比。分区枢轴，所有小于枢轴的元素，加上大于枢轴的所有元素。您移动所有等于主键的元素。

Answer 5

//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(); 

} 

} 

Answer 6

我认为这与Dijkstra分区方式有关，其中分区的元素小于，等于和大于主元。只有较小和较大的分区才能递归排序。您可以在the walnut上看到交互式可视化效果。我使用的颜色有红色/白色/蓝色，因为分区的方法通常称为“荷兰国旗问题”