处理先前快速排序中的重复元素

我找到了一种在快速排序中更有效地处理重复元素的方法，并且想知道是否有人以前见过这样做过。

这种方法大大减少了检查重复元素所涉及的开销，从而提高了有和没有重复元素的性能。通常，重复元素以几种不同的方式处理，我将首先列举这些方式。

首先，有荷兰国旗方法对数组进行排序，如 [ < pivot | == pivot | unsorted | > pivot] .

其次，排序时将相等的元素放在最左边，然后将它们移动到中心的方法是[ == pivot | < pivot | unsorted | > pivot]然后在排序后 ==元素移动到中心。

第三，Bentley-McIlroy 分区把==两边的元素，所以排序是 [ == pivot | < pivot | unsorted | > pivot | == pivot]然后是 ==元素移动到中间。

最后两种方法是为了减少开销。

我的方法

现在，让我解释一下我的方法如何通过减少比较次数来改进快速排序。
我一起使用两个快速排序函数，而不是一个。

我将调用的第一个函数 q1并将数组排序为 [ < pivot | unsorted | >= pivot] .

我将调用的第二个函数 q2并将数组排序为 [ <= pivot | unsorted | > pivot] .

现在让我们看看这些串联的用法，以改进对重复元素的处理。

首先，我们调用q1对整个数组进行排序。它选择一个枢轴，我们将进一步将其称为 pivot1然后围绕 pivot1 进行排序.因此，我们的数组在这一点上被排序为 [ < pivot1 | >= pivot1 ] .

然后，对于 [ < pivot1]分区，我们将其发送至 q1再一次，那部分是相当正常的，所以让我们先对另一个分区进行排序。

对于 [ >= pivot1]分区，我们将其发送至 q2 . q2选择一个枢轴，我们将其称为 pivot2从此子数组中将其排序为 [ <= pivot2 | > pivot2] .

如果我们现在查看整个数组，我们的排序看起来像 [ < pivot1 | >= pivot1 and <= pivot2 | > pivot2] .这看起来非常像双枢轴快速排序。

现在，让我们回到 q2 内部的子数组( [ <= pivot2 | > pivot2] )。

对于 [ > pivot2]分区，我们只需将其发送回 q1这不是很有趣。

对于 [ <= pivot2]分区，我们首先检查是否pivot1 == pivot2 .如果它们相等，那么这个分区已经排序了，因为它们都是相等的元素!如果枢轴不相等，那么我们只需将此分区发送到 q2再次选择一个枢轴(进一步 pivot3 )，排序，如果 pivot3 == pivot1 ，则不必对 [ <= pivot 3] 进行排序等等。

希望你现在明白了。这种技术的改进是处理相等的元素，而不必检查每个元素是否也等于枢轴。换句话说，它使用较少的比较。

我还没有尝试过的另一种可能的改进是 checkin qs2如果[ <= pivot2]的大小与其总子数组的大小相比，分区相当大(或 [> pivot2] 分区非常小)，然后在这种情况下对重复元素进行更标准的检查(上面列出的方法之一)。

源代码

这里有两个非常简化的 qs1和 qs2职能。他们使用 Sedgewick 收敛指针排序方法。他们显然可以非常优化(例如，他们选择的支点非常糟糕)，但这只是为了展示这个想法。我自己的实现更长、更快、更难阅读，所以让我们从这个开始:

// qs sorts into [ < p | >= p ]
void qs1(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[right], temp;
    long i = left - 1, j = right;
    // do the sort
    for(;;){
        while(a[++i] < pivot);
        while(a[--j] >= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[i];
    a[i] = a[right];
    a[right] = temp;

    // send the [ < p ] partition to qs1
    if(left < i - 1)
        qs1(a, left, i - 1);
    // send the [ >= p] partition to qs2
    if( right > i + 1)
        qs2(a, i + 1, right);
}

void qs2(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[left], temp;
    long i = left, j = right + 1;
    // do the sort
    for(;;){
        while(a[--j] > pivot);
        while(a[++i] <= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[j];
    a[j] = a[left];
    a[left] = temp;

    // Send the [ > p ] partition to qs1
    if( right > j + 1)
        qs1(a, j + 1, right);
    // Here is where we check the pivots.
    // a[left-1] is the other pivot we need to compare with.
    // This handles the repeated elements.
    if(pivot != a[left-1])
            // since the pivots don't match, we pass [ <= p ] on to qs2
        if(left < j - 1)
            qs2(a, left, j - 1);
}

qs1(array,0,indexofendofarray);

std::sort - 1.609 seconds  
dual-pivot quicksort - 1.25 seconds  
qs1/qs2 - 1.172 seconds

std::sort - 0.468 seconds  
dual-pivot quicksort - 0.438 seconds  
qs1/qs2 - 0.407 seconds

最佳答案

弗拉基米尔·雅罗斯拉夫斯基 | 9 月 11 日 12:35
用新的双枢轴快速排序替换 java.util.Arrays 中的快速排序

访问 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

关于c++ - 有没有人见过这种对快速排序的改进？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2105737/