首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >以前有没有人看到过快速排序的这种改进?

问以前有没有人看到过快速排序的这种改进?
EN

Stack Overflow用户
提问于 2010-01-21 07:06:25
回答 5查看 5.4K关注 0票数 25

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

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

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

首先,有荷兰国旗方法,它像[ < 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选择一个pivot,我们将在该子数组中将其引用为pivot2,并将其排序到[ <= pivot2 | > pivot2]中。

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

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

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

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

希望您现在已经明白了这一点。这种技术的改进是,无需检查每个元素是否也等于枢轴,即可处理相等的元素。换句话说,它使用较少的比较。

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

源代码

这里有两个非常简单的qs1和qs2函数。它们使用Sedgewick收敛指针排序方法。显然,它们可以非常优化(例如,它们对轴心的选择非常糟糕),但这只是为了展示想法。我自己的实现更长,更快,更难读,所以让我们从这个开始:

代码语言:javascript
复制
// 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);
}

我知道这是一个相当简单的想法,但当我添加标准的快速排序改进时,它在运行时有了相当大的改进(3个中位数的轴心选择,以及小数组的插入排序)。如果您要使用此代码进行测试,请仅对随机数据进行测试,因为枢轴选择不佳(或改进枢轴选择)。要使用这种排序,您可以调用:

代码语言:javascript
复制
qs1(array,0,indexofendofarray);

一些基准测试

如果你想知道它到底有多快,这里有一些初学者的数据。它使用的是我的优化版本,而不是上面给出的版本。然而,上面给出的一个在时间上仍然比std::sort时间更接近双轴快速排序。

对于具有2,000,000个元素的高度随机数据,我得到以下时间(通过对几个连续的数据集进行排序):

代码语言:javascript
复制
std::sort - 1.609 seconds  
dual-pivot quicksort - 1.25 seconds  
qs1/qs2 - 1.172 seconds

其中std::sort是C++标准库排序,双轴快速排序是弗拉基米尔·雅罗斯拉夫斯基几个月前提出的,qs1/qs2是我的快速排序实现。

更少的随机数据。对于2,000,000个元素,并使用rand() % 1000生成(这意味着每个元素大约有2000个副本),时间是:

代码语言:javascript
复制
std::sort - 0.468 seconds  
dual-pivot quicksort - 0.438 seconds  
qs1/qs2 - 0.407 seconds

有一些情况下,双轴快速排序胜出,我确实意识到双轴快速排序可以优化得更多,但同样可以安全地声明我的快速排序。

以前有没有人见过这个?

我知道这是一个冗长的问题/解释,但是你们中有谁以前看到过这种改进吗?如果是这样,那么为什么它没有被使用?

EN

回答 5

Stack Overflow用户

发布于 2012-05-09 08:13:45

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

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

票数 7
EN

Stack Overflow用户

发布于 2012-05-24 09:06:55

回答你的问题,不,我以前没有见过这种方法。我不打算分析你的代码并做其他艰苦的工作,但也许下面是正式呈现你的算法的下一步/注意事项。在现实世界中,实现排序算法的目的是:

良好的可扩展性/复杂性和低开销

伸缩性和开销是显而易见的,并且很容易衡量。当分析排序时,除了时间测量比较和交换的数量。大文件的性能也将取决于磁盘寻道时间。例如,合并排序在具有磁盘的大文件上工作得很好。(另请参阅Quick Sort Vs Merge Sort )

具有良好性能的宽范围输入

有很多数据需要排序。众所周知,应用程序以模式生成数据,因此重要的是使排序在某些模式下具有弹性,以应对性能较差的情况。您的算法针对重复数字进行了优化。如果所有数字都重复但只有一次(即seq 1000>file;seq 1000>>file;shuf file)怎么办?如果数字已经排序了怎么办?向后排序?那么1,2,3,1,2,3,1,2,3,1,2,3,3?1,2,3,4,5,6,6,6,6,6,5,5,5,4,4,3,2,1,2,3,4,4,5,6,7的模式是什么?在这些常见场景中,糟糕的性能是交易的破坏者!在与已发布的通用算法进行比较之前,最好准备好此分析。

病理表现的低风险

在所有输入的排列中,有一种比其他的表现更差。这比平均水平差多少?有多少排列会提供类似的糟糕性能?

祝你下一步好运!

票数 5
EN

Stack Overflow用户

发布于 2010-01-21 07:13:36

这是一个很大的改进,如果你希望有很多相等的对象,我相信它已经被实现了。有很多这样的墙。

如果我对你写的所有内容都理解正确的话,那么它不是一般的“已知”的原因是它确实提高了基本的O(n2)性能。这意味着,两倍的对象数量,四倍的时间。除非所有对象都是相等的,否则您的改进不会改变这一点。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2105737

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档