引入
想必大伙们在掌握了各种排序算法之后，个个都跃(xin)跃(ru)欲(si)试(hui)，迫切希望能够大(mao)显(pao)身(pai)手(xu)。为了能帮助大家提(shao)高(diao)效(tou)率(fa)，将精力集中在学习新知识上，我为你们准备了这篇博客。
本文介绍了sort( )函数的基本用法，并且尽可能言简意赅、条理清晰地讲明白了一些相对高阶的内容，适合c++新手进行学习和提高。
PS：sort( )函数及其变化，原则上可以基本满足各种情况的排序，但是要知道排序算法是最简单，最基础，也是对初学编程者最重要的算法。平时用sort偷个懒可以，但切记一定要掌握好各种排序算法。
C语言中的qsort()
#include<stdlib.h>
void qsort(void* base, size_t NumOfElement, size_t SizeOfElement,
int (*compare)(const void *p1, const void *p2)
核心就是利用了函数指针，使用前必须严格定义一个与适合参数4的比较函数。
int cmp_C(const void* p1, const void* p2)
{
return *(int*)p1 > *(int*)p2;
}
int a[] = { 4,2,5,3,6,8,1,7 };
qsort(a, sizeof(a)/sizeof(a[0]), sizeof(int), cmp_C);
//排序后， a = {1,2,3,4,5,6,7,8}
通过定义不同的cmp( )比较函数，我们便能实现不同类型顺序空间的排序。
初识C++的sort( )
对于C++小白，建议先学会这下面两种最实用，最简单的使用方法。
函数定义先不展开，先来看它的使用例子
方法一
#include <algorithm>
bool cmp1(int a,int b) {
return a > b;
}
int a[] = { 4,2,5,3,6,8,1,7 };
int n = sizeof(a) / sizeof(a[0]);
sort(a, a + n, cmp1);
//排序后：a = {8,7,6,5,4,3,2,1}
说明：
- 参数 1 为排序首地址，参数 2 为排序末地址，参数 3 依旧为函数指针。
- 参数 3 可以不写，默认为升序
进一步：
用过sort( )函数给人的直观感受就是，C++真人性化。
- 首先，函数参数更少。实际上C语言qsort中的参数3就挺多余, 元素的大小完全可以省去，交给比较函数来处理。
- 其次，顺序更合理。刚才两个例子的比较函数都是用的元素a大于元素b，sort排序后大数在前，而qsort排完小数在前，你说C语言反不反人类。
- 最后，比较函数更方便。qsort的比较函数必须严格遵循格式，无论定义还是使用都麻烦地要死，而sort的比较函数就放宽松了许多，参数想怎样就怎样。(不过我们一般使用常引用作为比较函数的参数)
方法二
sort(a, a + n, greater<int>());
//排序后：a = {8,7,6,5,4,3,2,1}
sort(a, a + n, less<int>());
//排序后：a = {1,2,3,4,5,6,7,8}
深入sort( )函数
接下来的内容适合对c++有一定理解。你如果是为了标题而来，想提前学习一些奇(zhuang)技(bi)淫(ji)巧(qiao)，那么下面就是你想要的。你如果是想正经学习，下面的知识将是很好的案例来带你初窥仿函数、函数对象、lambda表达式等相关内容。
首先来看sort( )函数的定义
void sort (RanIt first, RanIt last, Compare comp);
- 参数1 参数2 为随机访问迭代器，指向排序地址的末尾。
- 参数3 规定第三个参数为一个二元谓词
- 进一步说明
- 指针实际上也是一种随机访问迭代器，故之前两个初阶方法中的使用没有问题
- 谓词是一个可调用的表达式，返回结果是一个能用作条件判断的值。二元谓词即谓词有两个参数。一般我们会使用函数指针、仿函数和lambda表达式来充当这个谓词。
- 参数3 默认的情况表面上是排升序，实际上其实是利用了“<”运算符，因此任何定义了"<"的对象，都可以缺省参数3，默认地完成排序。
函数指针
这里sort依旧是使用函数指针，不同的是引入了Vector容器及其迭代器
bool cmp2(const int& a,const int& b)
{
return a < b;
}
vector<int> V = { 4,2,5,3,6,8,1,7 };
sort(V.begin(), V.end(), cmp2);
函数对象
这里涉及到一个概念：可调用类型。其实我们接触过的函数、函数指针就是可调用类型，他们最明显的一个特点是都伴随着"( )"一对括号，这对括号就是调用运算符。
重载一个类的调用运算符，那么这个类创建的对象就能够像函数一样使用调用运算符，成为了可调用的对象，即函数对象(也称仿函数)。
class cmp2 {
public:
bool operator()(int a, int b)
{
return a > b;
}
};
//根据定义。
// cmp2 functor;
// sort(V.begin(), V.end(), functor);
//简洁写法，创建匿名对象
sort(V.begin(), V.end(), cmp2());
其实刚才的方法二中的greater和less就属于这种类型。
这种方法貌似多此一举，但还是有其独特的作用。比如这个函数存在于一个类中，那么就可以在类中声明其他成员，这样我们就可以记录一个比较函数的状态的相关信息。
lambda 表达式
lambda 表达式也称 lambda 函数，它与普通函数已经极其相似了，简单得看它就像一个匿名的内联函数，这个函数具有返回类型和参数列表，同时它也是一个可调用类型。废话不多说，直接来看如何使用。
sort(V.begin(), V.end(), [](int x, int y)->bool {return x > y; });
解读：这参数3 是个lambda表达式，充当sort函数需要的比较函数。
- 这里的 [ ] 可以先忽略其含义，但写法上不能忽略，它标记着一个lambda表达式
- ( ) 中为表达式的参数
- -> 指向表达式的返回类型，为bool类型
- { } 中为函数体
这样看来，lambda表达式确实能够起到函数一样的作用，而且用法也不是很复杂。它最直接的作用就是我们不必为了某些只会使用一次的函数起名字，也不需要在某些地方单独定义出一个函数。
lambda表达式也是较经常出现在LeetCode的官方题解的方法，所以建议大家可以再深入些去了解这个C11标准的新特性。
总结
C++为我们提供了更加好用的排序函数sort( ),其中第三个函数是一个二元谓词，可由以下三个可调用类型充当：函数指针，函数对象、lambda表达式。
以后有机会再来详解一下lambda表达式。
测试代码如下，供大家逐个测试。
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int cmp_C(const void* p1, const void* p2)
{
return *(int*)p1 > *(int*)p2;
}
//函数指针法
bool cmp1(int a,int b) //简写
{
return a > b;
}
//bool cmp1(cons int& a,const int& b) //严谨写法
//{
// return a > b;
//}
//函数对象法
class cmp2 {
public:
bool operator()(int a, int b)
{
return a > b;
}
};
int main()
{
int a[] = { 4,2,5,3,6,8,1,7 };
vector<int> V = { 4,2,5,3,6,8,1,7 };
//C语言 qsort()
// qsort(a, sizeof(a) / sizeof(a[0]), sizeof(int), cmp_C); //大于 排完小在前 ， 小于 排完大在前
//初识sort()
//sort(a, a + sizeof(a) / sizeof(a[0]), cmp1); //大于 排完大在前
//sort(V.begin(), V.end(), cmp1);
//sort(V.begin(), V.end(), greater<int>());
//仿函数法
//cmp2 aaa; //1.用可调用对象，充当谓词
//sort(V.begin(), V.end(), aaa);
//sort(V.begin(), V.end(), cmp2()); //2.匿名对象
//lambda 表达式
//sort(V.begin(), V.end(), [](int x, int y)->bool {return x > y; });
//附赠 尝试理解
//auto f = [](auto x, auto y) ->bool {return x > y; };
//bool (*f)(int, int) = [](int x, int y) ->bool {return x > y; };
//sort(V.begin(), V.end(), f);
//输出
for (auto i : a) cout << i; cout << endl;
for (auto i : V) cout << i; cout << endl;
return 0;
}
