本文为senlie原创，转载请保留此地址：

partial_sort / partial_sort_copy

-----------------------------------------------------------------------------------------------------------------------------------------

描写叙述：本算法接受一个 middle 迭代器(位于序列[first, last) 之列)。然后又一次安排[first, last),

使序列中的 middle - first 个最小元素以递增顺序排序。置于[first, last)内。

其余 last - middle 个元素安置于[middle, last)中，不保证有不论什么特定顺序。

思路：

算法内部採用 heap sort

1.用 make_heap() 将 [first, middle) 组织成一个 max-heap

2.将[middle,last) 中的每个元素与 max-heap 的堆顶元素比較，假设小于该值，就互换位置并又一次保持 max-heap 状态。

3.如今[first, middle)里保存的是较小的 middle - first 个元素，再使用 sort_heap() 对[first, middle] 排序就能够了

复杂度：(last - first) * log(middle - first) 次比較 

源代码：

template 
     
      inline void partial_sort(RandomAccessIterator first,                         RandomAccessIterator middle,                         RandomAccessIterator last) {  __partial_sort(first, middle, last, value_type(first));}template 
      
       void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,                    RandomAccessIterator last, T*) {  make_heap(first, middle);  for (RandomAccessIterator i = middle; i < last; ++i)    if (*i < *first)       __pop_heap(first, middle, i, T(*i), distance_type(first));  sort_heap(first, middle);}
      
     

演示样例：

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
     
      (cout, " "));// The printed result is "1 2 3 4 5 11 12 10 9 8 7 6".