STL中的排序算法sort详解【Van0512】

要使用sort排序，首先得包含algorithm的头文件，即在文件开头写下这么一行：

#include <algorithm>

同时，为了书写方便，同时也写下

using namespace std;

sort排序有两种参数模式，返回值都是void
一种是sort(first, last)
一种是sort(first, last, comp)
first和last表示的是一个迭代器对象，可以理解成指针，comp是一种自定义的比较器，可以自己定义比较规则。比较的范围是一个开区间[first, last)。
写个demo：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
缺省比较器的默认比较规则是升序排序，这里用两种方法构造两个和默认比较规则一致的比较器。
若要实现降序排序，把 '<' 改成 '>' 就可以了。
*/
bool comp(int i, int j) {
    return i < j;
}

struct {
    bool operator()(int i, int j) {
        return i < j;
    }
} comp2;

int main(void) {
    vector<int> vec = {3, 2, 4, 1, 7, 6, 5, 8 };
    //1. 实现前四个元素的升序排序
    sort(vec.begin(), vec.begin() + 4);
    //2. 实现后四个元素的升序排序
    sort(vec.begin() + 4, vec.end(), comp);
    //3. 实现所有元素的升序排序
    sort(vec.begin(), vec.end(), comp2);
    //可将下面的代码插入到各个排序语句之后，分析输出结果。
    for(auto iter = vec.begin(); iter != vec.end(); iter++)
        cout << *iter << " ";
    cout << endl;    

    return 0;
}

好吧，上面的代码是我在MarkDown编辑器直接写的，没有进行测试，不过，我觉得应该没问题，笑~O(∩_∩)O~
上面介绍完了sort的基本使用方法，接下来，做点更有趣的。
我们如果写下了这样一行代码，猜猜看会发生什么？

    sort(vec.rbegin(), vec.rend());

没错，你猜对了！
实现的是降序排序！
rbegin()返回的是一个指向vec最后一个元素的迭代器，而rbegin() + 1返回的是指向倒数第二个元素的迭代器。
于是，我们发现，如果要进行降序排序，我们可以不用定制自己的比较器（假设元素本身的可比较的）！

    sort(vec.rbegin(), vec.rend());

的作用，就相当于下面两条语句，当然它的效率更高。

    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());

最后要说的一点是，sort排序并不保证相同的两个元素排序之后的相对位置，也即是不稳定排序。这个意思是，假如第5个位置的元素是10， 第8个位置的元素也是10，排序之后，不保证第5个位置的元素依然在第8个位置的元素之前。
如果要使用稳定排序，则把sort改成stable_sort即可，这个方法实现的是稳定排序。
它们的平均时间复杂度是 N*log2(N)。