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上看到交互式可視化效果。我使用的顏色有紅色/白色/藍色，因爲分區的方法通常稱爲「荷蘭國旗問題」