partial_sort接受一个middle迭代器，使序列中的middle-first个最小元素以递增顺序排序，置于[first, middle)内。下面是测试代码： ~~~ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a[] = {10,9,8,7,6,5,4,3,2,1,0}; vector<int> vec(a, a+11); vector<int>::iterator b = vec.begin(); vector<int>::iterator e = vec.end(); partial_sort(b, b+6, e); // 前6个最小元素排序 while (b != e) cout << *(b++) << ' '; return 0; } ~~~ 运行结果：  从结果可以看出，前6个最小元素放在了前6个位置上，而剩下的元素则放于容器后面未排序。 实现partial_sort的思想是：对原始容器内区间为[first, middle)的元素执行make_heap()操作构造一个最大堆，然后拿[middle, last)中的每个元素和first进行比较，first内的元素为堆内的最大值。如果小于该最大值，则互换元素位置，并对[first, middle)内的元素进行调整，使其保持最大堆序。比较完之后在对[first, middle)内的元素做一次对排序sort_heap()操作，使其按增序排列。注意，堆序和增序是不同的。 下面分析STL的源码。partial_sort有两个版本，一个默认以小于作为比较规则，出来的顺序为递增排列。另一个可以传入一个仿函数，即自定义比较规则。这里只分析前者。 ~~~ template <class RandomAccessIterator> inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) { __partial_sort(first, middle, last, value_type(first)); } ~~~ 进入__partial_sort函数： ~~~ template <class RandomAccessIterator, class T> void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, T*) { make_heap(first, middle); // [first, middle)区间构造一个heap for (RandomAccessIterator i = middle; i < last; ++i) if (*i < *first) // 当前元素比堆中最大的元素小 __pop_heap(first, middle, i, T(*i), distance_type(first)); // first值放i中，i的原值融入heap并调整 sort_heap(first, middle); } ~~~ 此函数和上面的文字描述基本相同。有一点小的区别在于当*i < *first时，代码中没有互换i所指元素和first所指元素。到底怎么做的？来看看__pop_heap函数： ~~~ template <class RandomAccessIterator, class T, class Distance> inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance*) { *result = *first; // 弹出元素放vector尾端 __adjust_heap(first, Distance(0), Distance(last - first), value); } ~~~ 此函数把first中的元素放在了result，也就是i位置上，成功地把最大值挤出了[first, middle)区间。但此时first位置形成了一个空洞，即索引值Distance(0)，所以需要调整heap，这由__adjust_heap函数负责。调整大致过程是找出最大元素放入first，然后把value保存的值插入到堆的适当位置，在这里value即为T(*i)，即把i所指元素融入到了[first, middle)区间。由此可见，__adjust_heap的复用性还是很高的。 再回到__partial_sort函数。for循环就是重复上面的“挤出”和“融入”操作直到容器末尾。当跳出for循环时，区间[first, middle)中已经存放有容器的前middle-first个最小元素了。最后执行sort_heap()，由堆序变为增序排列： ~~~ template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { while (last - first > 1) pop_heap(first, last--); } ~~~ 弹出堆的最大值并放入尾部，然后缩小堆的范围，循环执行弹出操作直至堆只剩下最后一个元素。这样就可以达到排序效果了。注意，此函数只能用于堆上。若要对整个普通容器施行堆排序操作，可以借partial_sort接口，只需把middle参数改为last即可： partial_sort(first, last, last); 这种方法用到了STL的快速排序身上，感觉越来越有意思了。 个人觉得这个局部排序还是蛮重要的，至少是它的排序思想很好，要不然STL也不会使用它了。 参考： 《STL源码剖析》 P386.