STL 排序（转载）

这篇文章关于STL中的排序写的虽不深入，但是还是挺好的。

1、sort

sort有两种形式，第一种形式有两个迭代器参数，构成一个前开后闭的区间，按照元素的 less 关系排序；第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数，它使用快速排序算法，并且在递归过程中，当元素数目小于一个阈值（一般是16，我的试验是24）时，转成直接插入排序。伟大的数学家Knuth已经证明，在平均意义上，快速排序是最快的了；当然，最坏复杂性比较差。sort要求随机迭代器，因此对于很多编译器来说，对于前向迭代器（如list）使用sort是一个编译错误。

sort的基本使用方式如下：

#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
 
using namespace std;
 
void func1()
{
    vector<int> ar;
    //向数组里面插入一些随机数
    generate_n(back_inserter(ar), 100, rand);
    //按从小到大排序
    sort(ar.begin(), ar.end());
}

逆序排列的方法

void func2()
{
    vector<int> ar;
    //向数组里面插入一些随机数
    generate_n(back_inserter(ar), 100, rand);
 
    //方法1：使用函数作为谓词
    sort(ar.begin(), ar.end(), GreateThan);
    //方法2：使用仿函数作为谓词
    //注意下面两种方法都需要有个括号，实际上是要产生一个临时对象
    sort(ar.begin(), ar.end(), CompareInt());
    //方法3：使用预定义的Adapter, 定义在 <functional> 中
    sort(ar.begin(), ar.end(), greater<int>());
    //方法4：正常排序，然后翻转过来
    sort(ar.begin(), ar.end());
    reverse(ar.begin(), ar.end());
    //方法5：使用逆迭代器
    sort(ar.rbegin(), ar.rend());
}

 2、stable_sort

 sort优点一大堆，一个缺点就是它不是一种稳定的排序。什么是排序的稳定性？就是如果出现两个元素相等时，要求排序之后他们之间保持原来的次序（比如我们先按学号排序，然后按成绩排序，这时就希望成绩相同的还是按照学号的次序排）。很可惜，快速排序算法就不是稳定的，要追求这个，只好用stable_sort了。

在各种排序算法中，合并排序是稳定的，但一般的合并排序需要额外的O(N)的存储空间，而这个条件不是一定能够满足的（可能是比较奢侈的）。所以在stable_sort内部，首先判断是否有足够的额外空间（如vecotr中的cap()-size()部分），有的话就使用普通合并函数，总的时间复杂性和快速排序一个数量级，都是O(N*logN)。如果没有额外空间，使用了一个merge_without_buffer的关键函数进行就地合并（如何实现是比较有技巧的，完全可以专门谈一谈），这个合并过程不需要额外的存储空间（递归的堆栈除外），但时间复杂度变成O(N*logN)，这种情况下，总的stable_sort时间复杂度是O(N*logN*logN)。

总之，stable_sort稍微慢一点儿，但能够保证稳定，使用方法和sort一样。但很多时候可以不用这种方式和这个函数，比如上面的例子，完全可以在排序比较准则中写入成绩和学号两个条件就OK了。

class CStudent
{
public:
    CStudent();
    //注意这个比较函数中的const
    bool operator<(const CStudent& rhs) const
    {
        if (m_score != rhs.m_score)
            return (m_score <rhs.m_score);
        return m_name <rhs.m_name;
    }
protected:
    std::string m_name;
    int m_score;
};
 
void func4()
{
    vector<CStudent> arStu;
    sort(arStu.begin(), arStu.end());
}

3、heap_sort

堆排序也是一种快速的排序算法，复杂度也是O(N*logN)。STL中有一些和堆相关的函数，能够构造堆，如果在构造好的堆上每次取出来根节点放在尾部，所有元素循环一遍，最后的结果也就有序了。这就是sort_heap了。它的使用要求区间已经被构造成堆，如：

void func5()
{
    vector<int> ar;
    //生成数据
    generate_n(back_inserter(ar), 100, rand);
    //构造堆
    make_heap(ar.begin(), ar.end());
    //堆排序
    sort_heap(ar.begin(), ar.end());
}

4、list.sort

对于list容器，是不能直接使用sort的（包括stable_sort），从技术的角度来说，sort要求随机迭代器；从算法的角度来说，list这种链表结构本身就不适合用快速排序。因此，list容器内部实现了专门的sort算法，这个算法采用的是合并排序，应该是稳定的（不确定）。如：

list<int> li;
    li.sort();