对整个范围进行排序时，std::p artial_sort() 与 std::sort() 的性能?

Question

以下两种方法之间有显著区别吗？方式 1 使用sort或partial_sort，具体取决于向量的大小，而方式 2 总是使用partial_sort。我发现方式 2 更具吸引力，因为我的谓词比示例中复杂一些，所以我不想重复它。但我想知道partial_sort的表现是否比sort差，因为它并不意味着用于对整个范围进行排序，这就是为什么我倾向于使用方式 1。

int main()
{
std::vector<double> vec;
vec.push_back(1.0);
vec.push_back(3.0);
vec.push_back(2.0);
vec.push_back(5.0);
vec.push_back(4.0);
vec.push_back(9.0);
const size_t numBest = 3;
const size_t numTotal= vec.size();
#if WAY1
if (numTotal < numBest)
{
std::sort(vec.begin(), vec.end(), std::not2(std::less<double>()));
}
else
{
std::partial_sort(vec.begin(), vec.begin() + numBest, vec.end(), std::not2(std::less<double>()));
vec.resize(numBest);
}
#elif WAY2
{
const size_t numMiddle = numTotal < numBest ? numTotal : numBest;
std::partial_sort(vec.begin(), vec.begin() + numMiddle, vec.end(), std::not2(std::less<double>()));
vec.resize(numMiddle);
}
#endif
// now vec contains the largest numBest results.
return 0;
}

一些测试结果表明，如果必须对整个范围进行排序，则partial_sort比排序要差得多(在我的用例中为 4 倍(。这表明首选方式 1。似乎partial_sort仅用于对整个范围的一小部分进行排序。我在Visual Studio 2010中进行了测试。

Answer 1

根据 sgi doc，partial_sort使用heapsort，sort使用introsort：

partial_sort(第一个，最后一个，最后一个(具有对整个范围[第一个，最后一个]进行排序的效果，就像排序(第一个，最后一个(一样。但是，它们使用不同的算法：sort 使用内向算法(quicksort 的变体(，partial_sort 使用堆排序。参见高德纳第5.2.3节(D. E. Knuth，计算机编程的艺术。第 3 卷：排序和搜索。Addison-Wesley， 1975.(和J. W. J. Williams (CACM 7， 347， 1964(。堆排序和内联排序都具有 N 个 log(N( 阶的复杂性，但内引入排序通常快 2 到 5 倍。

所以，这是正常的partial_sort比sort慢4倍。

---

我检查了我的VS2017库，发现了partial_sort和sort的实现。这与SGI类似。

partial_sort

template<class _RanIt,
class _Pr> inline
void _Partial_sort_unchecked(_RanIt _First, _RanIt _Mid, _RanIt _Last,
_Pr& _Pred)
{       // order [_First, _Last) up to _Mid, using _Pred
if (_First == _Mid)
return; // nothing to do, avoid violating _Pop_heap_hole_unchecked preconditions
_Make_heap_unchecked(_First, _Mid, _Pred);
for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
{       // replace top with new largest
_Iter_value_t<_RanIt> _Val = _STD move(*_Next);
_Pop_heap_hole_unchecked(_First, _Mid, _Next, _STD move(_Val), _Pred);
}
_Sort_heap_unchecked(_First, _Mid, _Pred);
}

排序

template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort_unchecked1(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr& _Pred)
{       // order [_First, _Last), using _Pred
_Diff _Count;
while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)
{   // divide and conquer by quicksort
pair<_RanIt, _RanIt> _Mid =
_Partition_by_median_guess_unchecked(_First, _Last, _Pred);
_Ideal /= 2, _Ideal += _Ideal / 2;      // allow 1.5 log2(N) divisions
if (_Mid.first - _First < _Last - _Mid.second)
{       // loop on second half
_Sort_unchecked1(_First, _Mid.first, _Ideal, _Pred);
_First = _Mid.second;
}
else
{       // loop on first half
_Sort_unchecked1(_Mid.second, _Last, _Ideal, _Pred);
_Last = _Mid.first;
}
}
if (_ISORT_MAX < _Count)
{   // heap sort if too many divisions
_Make_heap_unchecked(_First, _Last, _Pred);
_Sort_heap_unchecked(_First, _Last, _Pred);
}
else if (2 <= _Count)
_Insertion_sort_unchecked(_First, _Last, _Pred);        // small
}

Answer 2

除了保证复杂性之外，没有什么需要以某种方式实现partial_sort

25.4.1.3 partial_sort [部分排序]

模板无效partial_sort(首先是随机访问迭代器， RandomAccessIterator middle， RandomAccessIterator last(; 模板 void partial_sort(随机访问迭代器在前，随机访问迭代器中间， RandomAccessIterator last， Compare comp(;

1 效果：将范围 [第一个，最后一个] 中的第一个中间 - 第一个排序的元素放入范围 [第一个，中间(。范围 [中间，最后( 中的其余元素按未指定的顺序放置。

2 要求： RandomAccessIterator 应满足 ValueSwappable 的要求 (17.6.3.2(. *优先的类型应满足以下要求： MoveConstructible(表 20(和 MoveAssignable(表 22(。

3 复杂度：大约(最后一个 - 第一个(* log(中间 - 第一个(比较

另一种实现可能是

std::nth_element - average linear time
followed by
std::sort - on the reduced range begin()-nth (n log n)