排序，直到我们得到排序数组的下半部分

Question

我目前正在尝试获取位于数据数组的下半部分的值。这个数组首先是未排序的。

从这个开始：

{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++编写代码并使用向量，但这个问题应该是相当通用的。

Answer 1

#include <algorithm>
std::partial_sort(start, middle, end);

Answer 2

如果不需要对下半部分进行排序，请使用std::nth_element。如果需要对下半部分进行排序，并且向量包含的元素少于100,000，则使用std::partial_sort；如果向量较大，则使用std::nth_element将向量划分为下半部分和上半部分，然后对下半部分使用std::qsort。我已经在运行CentOS和g++ 4.4.3的英特尔至强X5570 @2.93 g++上确认了这一点，并在回答结束时给出了时间安排。Scott Meyer和其他人发现，对于大型向量，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的英特尔至强X5570 @2.93 the上，我测量了以下时间。从数据中可以清楚地看出，对于所有大小，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

Answer 3

我很确定你可以做部分快速排序，在算法对你的数组进行了至少一半的排序后停止。有关可视化表示，请参见here。

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