partial_sort

类别: 算法	组件类型: 函数

原型

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, 
                  RandomAccessIterator middle,
                  RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
                  RandomAccessIterator middle,
                  RandomAccessIterator last, 
                  StrictWeakOrdering comp);

描述

两个版本partial_sort在如何定义一个元素是否小于另一个元素方面有所不同。第一个版本使用operator<，第二个版本使用 函数对象comp.

第一个版本的后置条件partial_sort如下。如果i和j是范围内任何两个有效的迭代器[first, middle)使得i在之前j，并且如果k是范围内的有效迭代器[middle, last)，那么*j < *i和*k < *i都将是false。第二个版本的对应后置条件partial_sort是comp(*j, *i)和comp(*k, *i)都是假的。非正式地说，这个后置条件意味着第一个middle - first元素按升序排列，并且中的任何元素都不小于中的任何元素[middle, last)小于中的任何元素[first, middle).

定义

对类型的要求

• RandomAccessIterator是 随机访问迭代器 的模型。
• RandomAccessIterator是可变的。
• RandomAccessIterator的值类型是 可比较小于。
• 对的排序关系RandomAccessIterator的值类型是严格弱排序，如 可比较小于 要求中所定义。

• RandomAccessIterator是 随机访问迭代器 的模型。
• RandomAccessIterator是可变的。
• StrictWeakOrdering是 严格弱排序 的模型。
• RandomAccessIterator的值类型可转换为StrictWeakOrdering的参数类型。

先决条件

• [first, middle)是一个有效的范围。
• [middle, last)是一个有效的范围。

复杂度

示例

int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);

partial_sort(A, A + 5, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".

注释

[1] 请注意，范围内的元素[first, middle)将与使用以下方法对整个范围进行排序的情况相同（暂时忽略等效元素）sort(first, last)。使用的原因partial_sort而不是sort仅仅是为了效率：一般来说，部分排序需要更少的时间。

[2] partial_sort(first, last, last)具有对整个范围进行排序的效果[first, last)，就像sort(first, last)一样。但是它们使用不同的算法sort使用introsort 算法（快速排序的变体），而partial_sort使用堆排序。参见 Knuth（D. E. Knuth，计算机程序设计艺术。第 3 卷：排序与查找。Addison-Wesley，1975。）第 5.2.3 节，以及 J. W. J. Williams（CACM 7，347，1964）。堆排序和 introsort 的复杂度都是 O(N log(N))N log(N)，但 introsort 通常快 2 到 5 倍。

另请参见