41

什么是具有 3 路分区的 QuickSort？

4

7 回答 7

55

画一个数组：

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

三分区快速排序将选择两个值进行分区并以这种方式拆分数组。让我们选择 4 和 7：

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

这只是常规快速排序的一个微小变化。

您继续对每个分区进行分区，直到对数组进行排序。运行时在技术上是 nlog 3 (n)，与常规快速排序的 nlog 2 (n) 略有不同。

于 2009-06-02T19:36:15.343 回答
18

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

也可以看看：

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

我认为面试问题版本也很有趣。它问，是否有四个分区版本的快速排序...

于 2009-06-02T19:30:27.193 回答
15

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

于 2009-06-02T21:16:18.930 回答
15

我认为 3 路分区是由 Djstrka 设计的。

考虑一个带有元素的数组{ 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }。

基本上，您设置了 3 个分区：小于、等于和大于某个枢轴。等于分区不需要进一步排序，因为它的所有元素都已经相等。

例如，如果我们选择第一个3作为枢轴，那么使用 Dijkstra 的 3 路分区将排列原始数组并返回两个索引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将是相同的。

于 2013-10-10T15:23:49.093 回答
1

我认为这与 Dijkstra 分区方式有关，其中分区的元素小于、等于和大于枢轴。只有较小和较大的分区必须递归排序。您可以在walnut看到一个交互式可视化并与它一起玩。我在那里使用的颜色是红色/白色/蓝色，因为分区方法通常被称为“荷兰国旗问题”

于 2015-07-28T22:02:50.143 回答
0

3 路快速排序基本上将数组划分为 3 个部分。第一部分小于枢轴，第二部分等于枢轴，第三部分大于枢轴。它是线性时间分区算法。这种划分类似于荷兰国旗问题。

于 2019-08-18T15:22:54.393 回答
-2 
  //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();

}

}
于 2014-05-03T11:34:40.733 回答