C++STL中元素排序的方法

STL提供了nth_element（）算法。该算法可以对指定区间内的元素进行排序，并使第n个位置上的元素就位，即所有在位置n之前的元素都小于等于它，所有在位置n上的元素都大于等于它，由此可以得到根据位置n上的元素分割开来的两个子序列。第一子序列的元素全部小于第二子序列的元素。如果程序开发人员只需要n个最大或最小元素，但不要求这些元素是已排序的，此时本算法会提供很大帮助。

由上述内容可知，在使用nth_element（）算法之后的序列中，元素是已排序的，并且所有小于第n个元素的元素出现在该元素的前面，而大于第n个元素的元素出现在该元素的后面。其原型为：

在上述两种形式的原型中，迭代器属于随机访问型迭代器。第一种形式属于常规形式，第二种形式包含二元判断式，并使用二元判断式comp（elem1，elem2）作为排序规则。

nth_element（）算法和partial_sort（）算法有相似之处。其区别在于：partial_sort（）算法在实现局部排序时，指定位置作为划分整个区间的界线；而nth_element（）算法在实现排序时，是指定区间中的某个位置（元素）作为划分整个区间的界线。

例4-28

(www.xing528.com)

例4-28的执行效果如图4-28所示。

图4-28 例4-28的执行效果

提示

程序的执行效果可能和读者想象的不一样。请仔细阅读、认真思考。