logo标签列表

将数组排序直到我们得到排好序的数组的最低一半。

c++algorithmsorting
4

我目前正在尝试获取数据数组中最低一半的数值。这个数组一开始是未排序的。

基于此，

{4,6,9,3,8,5}

转换为：

{3,4,5,6,9,8} or {3,4,5}

一个简单的解决方案是对数组进行排序（使用快速排序），然后仅使用存储在已排序数组的前一半中的值。然而，由于快速排序和大多数高效的排序算法会将整个数组排序，而我只需要前50％的值，这似乎是一种资源浪费。请注意，在此项目中性能很重要。
了解到完全排序的复杂度是O(n log n)，而停止在找到最小元素后的排序的复杂度是O(n)，那么我可以轻松构建一个简单的算法，其复杂度为n/2*n，以查找最低的50％。但是，这真的比完整的快速排序更好吗？
明确一下，如果我们只想要数组中最低的一半值，那么最好使用哪种排序方法？如果50％更小（例如1％），则依次搜索最低元素当然是最快的解决方案，但在什么情况下它比快速排序慢？
我在使用C++编码并使用向量，但这个问题应该是相当普遍的。
5个回答
11
#include <algorithm>
std::partial_sort(start, middle, end);
我的印象是partial_sort只对数组的一部分进行排序，但仔细阅读文档后似乎正是我需要的东西。"执行大约(end-start)*log(middle-start)次比较"，这比快速排序要好些...你知道它使用的算法是什么吗？ - Alex Millette
@AlexMillette：看起来GCC使用了堆排序的变体。也可以通过对快速排序进行小修改来完成——第一阶段将选择您想要的范围的末尾作为枢轴，然后仅对较低的子范围进行排序。 - Mike Seymour
可能是一种快速排序的形式，它会丢弃任何从 n/2 开始的分区。 - ltjax
1
@BenjaminLindley：不，它执行基于堆的分区，然后在较低的分区上执行堆排序（至少在4.6中是这样，在其他版本中我没有看过）。 - Mike Seymour
@rhalbersma：不，你是错误的。如果它按照你所描述的方式工作，就不需要std::partial_sort（我假设这就是你的意思），因为它将等同于std::sort(start, middle);。 - Fred Larson
显示剩余2条评论
4
如果您不需要下半部分排序，可以使用std::nth_element。如果您需要对下半部分进行排序，且向量包含的元素少于100,000个，则使用std::partial_sort；如果您的向量更大，则使用std::nth_element将向量划分为下半部分和上半部分，然后在下半部分上使用std::qsort。我已在运行CentOS和g++ 4.4.3的Intel Xeon X5570 @ 2.93GHz上进行了确认，并在本答案末尾给出了时间。Scott Meyers和其他人发现，对于大型向量，std::nth_element后跟std::qsort比std::partial_sort快得多，这令人惊讶。
如果您只想获取值的最低一半，并且不需要对它们进行排序，则std::nth_element是最快的（复杂度为线性）。
参考链接：http://www.velocityreviews.com/forums/t745258-nth_element-sort-versus-partial_sort.html 和 http://www.cplusplus.com/reference/algorithm/nth_element/。
// nth_element example (modified to partition into lower/upper halves)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    vector<int> myvector;
    vector<int>::iterator it;

    // set some values:
    for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

    random_shuffle (myvector.begin(), myvector.end());

    // using default comparison (operator <):
    nth_element (myvector.begin(), myvector.begin()+myvector.size()/2, myvector.end());

    // print out content:
    cout << "myvector contains:";
    for (it=myvector.begin(); it!=myvector.end(); ++it)
        cout << " " << *it;

    cout << endl;

    return 0;
}

在运行CentOS并使用g++ 4.4.3的Intel Xeon X5570 @ 2.93GHz上，我测量了以下时间。从数据中可以清楚地看到，std::nth_element是线性的，并且对于所有大小都比std::partial_sort更快，在N为10亿个元素时快94倍。

N =       1000 nth_element   0.0000082 sec
N =       1000 nth + qsort   0.0001114 sec
N =       1000 partial_sort  0.0000438 sec

N =      10000 nth_element   0.0000592 sec
N =      10000 nth + qsort   0.0005639 sec
N =      10000 partial_sort  0.0005271 sec

N =     100000 nth_element   0.00095 sec
N =     100000 nth + qsort   0.00683 sec
N =     100000 partial_sort  0.00697 sec

N =    1000000 nth_element   0.0086 sec
N =    1000000 nth + qsort   0.0831 sec
N =    1000000 partial_sort  0.1227 sec

N =   10000000 nth_element   0.0700 sec
N =   10000000 nth + qsort   0.9307 sec
N =   10000000 partial_sort  2.7006 sec

N =  100000000 nth_element   0.8147 sec
N =  100000000 nth + qsort  10.7602 sec
N =  100000000 partial_sort 56.7105 sec

N = 1000000000 nth_element   10.055 sec
N = 1000000000 nth + qsort  123.703 sec
N = 1000000000 partial_sort 947.949 sec
虽然复杂度确实是线性的，但常数因子相当大，只有在元素数量很大时才会开始显示出好处。 - Happy Green Kid Naps
这不是我的经验，你用的是哪个编译器/库/机器来得出这个观察结果的？ - amdn
有趣。我假设你是在50%的限制下进行测试的。我想知道如果我们改变这个限制会得到什么结果。也就是说，当接近100%时，partial_sort是否会占据上风？那快速排序呢？虽然这更多是出于好奇而不是我的项目，所以我不会对此进行太多测试。不过，这个答案还是相当不错的。 - Alex Millette
Alex，是的，测试是在50%的限制下进行的。我可能会进行一项95%的测试并报告结果。 - amdn
0

我认为在这个问题中，没有比O(log N)时间复杂度更低的算法。但在平均情况下，可以通过优化来提高效率。

你可以修改快速排序算法，以适应这个特定的用例，方法如下。

也许你已经知道，快速排序包括一个名为partition的内部算法，它将数组分为两个部分，并在中间设置一个基准元素，使得左侧的值小于基准值，右侧的值大于基准值。

因此，你的问题可以简化为将一个数组划分为两部分，使得基准元素两侧的元素数量相等。

以下算法可以解决这个问题，它将数组分成两半，以便较低的一半具有小于中位数的元素，较高的一半具有大于中位数的元素。

void split_the_array(int[] array, int a, int b, int m)
{
    p = partition(array, a, b)
    if (p == m) return;
    if (p < m) split_the_array(p+1, b, m)
    else       split_the_array(a, p-1, m)
}

调用此函数的方式为

split_the_array(arr, 0, len(arr), len(arr) / 2)

函数执行后，左侧所有元素（len(arr) / 2）应小于它，右侧所有元素应大于它。

你应该很容易得到分区算法。

0

我相信你可以进行部分快速排序，在它至少排序了一半的数组后停止算法。在这里查看可视化表示。

在最坏的情况下，整个数组将被排序，而在最好的情况下，一半将被排序。

0

你可以使用基数排序对所有内容进行排序，它可能比快速排序更快。我不确定它是否比部分排序更快。如果您需要对一定范围的数字进行排序（例如32位表示），则它非常有用。 这里是我之前制作的一个实现
编辑：看起来这个基数排序的实现甚至更快

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接