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++ 编码并使用向量，但是这个问题应该很笼统。

4

5 回答 5

11 
#include <algorithm>
std::partial_sort(start, middle, end);
于 2012-08-09T16:22:18.003 回答
4

如果您不需要对下半部分进行排序，请使用std::nth_element. 如果您需要对下半部分进行排序并且向量包含少于 100,000 个元素，请使用std::partial_sort，如果您的向量较大，则使用std::nth_element将向量划分为下半部分和上半部分，然后std::qsort在下半部分使用。我已经在运行带有 g++ 4.4.3 的 CentOS 的 Intel Xeon X5570 @ 2.93GHz 上确认了这一点，并在此答案的末尾给出了时间安排。Scott Meyers 和其他人发现令人惊讶的是，std::nth_element随后的速度比大型向量std::qsort要快得多：std::partial_sort

http://www.velocityreviews.com/forums/t745258-nth_element-sort-versus-partial_sort.html

如果您只想要最低一半的值并且不需要对它们进行排序，那么std::nth_element最快（复杂性是线性的）。

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
于 2012-08-09T16:32:11.417 回答
0

您可以使用基数排序对所有内容进行排序，它可能比快速排序更快。我不确定它是否比部分排序更快。如果您需要对有限范围的数字（例如 32 位表示）进行排序，这很有用 这是我前段时间
编辑的一个实现：似乎基数排序的这种实现更快

于 2012-08-09T19:22:33.477 回答
0

我很确定您可以进行部分快速排序，在算法对您的数组至少一半进行排序后停止该算法。请参阅此处以获取视觉表示。

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

于 2012-08-09T16:37:14.203 回答
0

对于这个问题，我认为没有任何算法的时间复杂度小于 O(log N)。但在一般情况下，这可以得到加强。

您可以针对此特定用例微调快速排序算法，如下所示。

您可能已经知道，快速排序包含一个称为分区的内部算法，它将数组分成两个，中间有一个枢轴元素，使得左侧的值小于枢轴，右侧的值大于枢轴.

因此，您的问题简化为对数组进行分区的问题，以便在枢轴的两侧拥有相等数量的元素。

下面的算法应该可以工作，它将数组分成两部分，这样数组的下半部分的元素小于中值，上半部分的元素大于中值。

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) 左边的所有元素都应该小于它，右边的元素应该大于它。

您应该很容易获得分区算法。

于 2012-08-09T16:38:04.820 回答