STL的sort()算法，数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。STL sort算法(以上三种算法的综合) -- Introspective Sorting(内省式排序)。
I）Sort函数包含在头文件为#include<algorithm>的c++标准库中！ II）Sort函数有三个参数： （1）第一个是要排序的数组的起始地址。 （2）第二个是结束的地址（最后一位要排序的地址） （3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。
STL里面有个sort函数，可以直接对数组排序，复杂度为n*log2(n)。
使用第一个版本是对[first,last)进行升序排序，默认操作符为"<"，第二个版本使用comp函数进行排序控制，comp包含两个在[first,last)中对应的值，如果使用"<"则为升序排序，如果使用">"则为降序排序，分别对int、float、char以及结构体排序:
sort_main函数
#include "stdafx.h" #include #include #include #include using namespace std; bool compare(const string &a, const string &b){ return a > b; } bool cmp(const int &a, const int &b){ return a > b; } int _tmain(int argc, _TCHAR* argv[]) { vector res = { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"}; vector B = { 1, 2, 3, 4, 5 }; for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; sort(B.begin(), B.end(), cmp); sort(res.begin(), res.end(), compare); for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; system("pause"); return 0; }输出：
ABC ACB BAC BCA CAB CBA 1 2 3 4 5 CBA CAB BCA BAC ACB ABC 5 4 3 2 1
sort_class函数
class Test{ public: static bool compare(const string &a, const string &b){ return a > b; } static bool cmp(const int &a, const int &b){ return a > b; } void test(){ vector res = { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" }; vector B = { 1, 2, 3, 4, 5 }; for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; sort(B.begin(), B.end(), cmp); sort(res.begin(), res.end(), compare); for (int i = 0; i < res.size(); i++){ cout << res[i] << " "; } cout << endl; for (int i = 0; i < B.size(); i++){ cout << B[i] << " "; } cout << endl; } }; int _tmain(int argc, _TCHAR* argv[]) { Test t; t.test(); system("pause"); return 0; } 输出： ABC ACB BAC BCA CAB CBA 1 2 3 4 5 CBA CAB BCA BAC ACB ABC 5 4 3 2 1这里sort_main函数与sort_class函数，有一点区别的是
sort_main函数要申明为
bool compare(const string &a, const string &b){ return a > b; }
sort_class函数要申明为
static bool compare(const string &a, const string &b){ return a > b; }
sort_class函数没有申明static,会出错（没有深入研究，先记录下来）
错误 4error C2780: “void std::sort(_RanIt,_RanIt)”: 应输入 2 个参数，却提供了 3 个
错误 3error C3867: “Test::compare”: 函数调用缺少参数列表；请使用“&Test::compare”创建指向成员的指针
gcc下编译，sort_class函数没有申明static,也会出错
In file included from a.cc:2: ./solution.h:10:32: error: reference to non-static member function must be called sort(res.begin(), res.end(), compare); 1 error generated.
gcc下编译，sort_class函数申明static，但是参数没有申明为const 也会出错
static bool compare(string &a, string &b)){ return a > b; }
In file included from a.cc:1: In file included from /home/web/newjudge/include/nc_tools.h:5: In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/algorithm:62: /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:2287:28: error: binding of reference to type 'basic_string<[3 * ...]>' to a value of type 'const basic_string<[3 * ...]>' drops qualifiers while (__comp(*__first, __pivot))~~~~~~ /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:2319:19: note: in instantiation of function template specialization 'std::__unguarded_partition<__gnu_cxx::__normal_iterator<std::basic_string *, std::vector<std::basic_string, std::allocator<std::basic_string > > >, std::basic_string, bool (*)(std::basic_string &, std::basic_string &)>' requested here return std::__unguarded_partition(__first + 1, __last, *__first, __comp); /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:2360:11: note: in instantiation of function template specialization 'std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<std::basic_string *, std::vector<std::basic_string, std::allocator<std::basic_string > > >, bool (*)(std::basic_string &, std::basic_string &)>' requested here std::__unguarded_partition_pivot(__first, __last, __comp); /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:5512:9: note: in instantiation of function template specialization 'std::__introsort_loop<__gnu_cxx::__normal_iterator<std::basic_string *, std::vector<std::basic_string, std::allocator<std::basic_string > > >, long, bool (*)(std::basic_string &, std::basic_string &)>' requested here std::__introsort_loop(__first, __last, ./solution.h:10:3: note: in instantiation of function template specialization 'std::sort<__gnu_cxx::__normal_iterator<std::basic_string *, std::vector<std::basic_string, std::allocator<std::basic_string > > >, bool (*)(std::basic_string &, std::basic_string &)>' requested here sort(res.begin(), res.end(), compare); In file included from a.cc:1: In file included from /home/web/newjudge/include/nc_tools.h:5: In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/algorithm:62: /usr/bin/../lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_algo.h:2290:18: error: binding of reference to type 'basic_string<[3 * ...]>' to a value of type 'const basic_string<[3 * ...]>' drops qualifiers while (__comp(__pivot, *__last)) 2 errors generated.
