了解各种与排序有关的选择

在C++的STL中，除了sort之外还有许多排序算法，根据不同情况选择不同的排序算法，能够获得更高的效率，在此记录一下。

1、sort

大多数程序员需要对一组对象进行排序的时候，首先想到的一个算法是：sort。sort是一个非常不错的算法，但它也并非在任何场合下都是完美无缺的。

    sort(v.begin(), v.end());                       //缺省是递增排序
    sort(v.begin(), v.end(), greater<double>());    //用函数对象（仿函数）实现递减排序

2、partial_sort

部分排序原理是堆排序。首先界定出区间[first， middle)，并利用make_heap建堆，将它组织成一个大根堆（max_heap），然后把[middle， last)中的每一个元素拿来与堆顶元素（最大值）比较，如果小于该最大值，就互换位置并重新保持大根堆状态，当我们走遍整个[middle， last)时，较大的元素都已经被抽离出[first， middle)了，这时候再以sort_heap将[first， middle)做一次排序即可。

    //将最大的10个元素按递增顺序放到v的前10个位置上
    partial_sort(v.begin(), v.begin() + 10, v.end(), Comapre);

算法图解如下：

3、nth_element

当nth_element返回时，所有按全排列规则排在位置n之前的元素也都被排在位置n之前，而所有按全排列规则排在位置n之后的元素都被排在位置n之后。nth_element的做法是不断地以三数取中将整个序列分割成更小的左、右子序列。如果nth迭代器落于左子序列，就再对左子序列进行分割，否则就再对右子序列进行分割。直到分割后的子序列长度不大于3，便对最后这个待分割的子序列做插入排序。

    //将最小的10个元素放到v的前10个位置上，这10个元素本身不按顺序排列
    nth_element(v.begin(), v.begin() + 9, v.end());
    //根据stl中区间的定义，partial_sort第二个参数是目标区间外的第一个元素
    //而nth_element则使用第二个参数标识出容器中的某个特定位置。

算法图解：

4、partition

把满足某个特定条件的元素放在区间的前部，然后返回一个迭代器，指向第一个不满足条件的元素。

    partition(v.begin(), v.end(), condition);

5、稳定排序

以上列举的算法都是不稳定排序，它们也有稳定版本：stable_sort，stable_partition。

总结

总的来说，算法所做的工作越多，它需要的时间也越多，稳定的排序算法要比那些忽略稳定性的算法更为耗时。按照效率将这些算法排序如下：

1. partition
2. stable_partition
3. nth_element
4. partial_sort
5. sort
6. stable_sort

参考文献

《Effective STL》 && 《STL源码剖析》