sort介绍

在C/C++中，要想应用排序算法，可以使用c语言的qsort，也可以使用c++的sort 。

1)qsort 是 C 标准库提供的一个通用排序函数，位于 stdlib.h 头文件中。

qsort 适用于 C 语言中的数组。

2)sort 是 C++ 中STL的泛型算法（即函数）

sort可以排数组，vector(以及其他的容器)

sort可以自定义排序规则。

引入：

#include<algorithm>

排静态数组

c语言中 arr是一个数组名 作为函数参数时会退化成数组中第一个元素的地址

即arr==>&arr[0],即由数组退化为一个指针；指针即可做加减乘除运算

sort函数的参数需要传入两个地址，如下列所示：

int arr[6]={2.4,6,1,3,5};
/*第一个参数填起始地址
第二个参函数填最后一个元素的后一个位置的地址*
即区间是左闭右开/
sort(arr,arr+6);

排动态数组

因为vector想表示位置得使用迭代器。

所以sort函数的参数使用两个迭代器

#include<vector>
​
vector<int> vec={2,3,5,1,4};
sort(vec.begin(),vec.end());

sort函数重载理解

上面的两个例子中，sort的参数使用了指针，也可以使用迭代器；

实际上这运用了c++语法中的函数重载，即不同的函数使用同一个名字；

自定义比较规则

sort的底层是快速排序实现的。

这是一个基于比较的排序；从而必然会存在这样的逻辑：

if(lhs比较rhs){不交换
}else{交换
}

其中lhs比较rhs默认是lhs<rhs；

若想要自定义比较和规则，我们可以自己写个函数，但该函数必须满足：有2个参数，返回值为bool

举例：怎样把升序排序定义成降序的排序呢？

先实现比较函数

bool compare(int lhs,int rhs){return lhs>=rhs;
}

从而便可使用它：

vector<int> vec={2,3,5,1,4};
sort(vec.begin(),vec.end(),compare);

这样，数组就会按照降序排序了。

从而，我们可以知道，我们要想自定义比较规则，只需要设计compare函数的实现就可以了。

compare函数的设计

compare函数设计首先要遵循一些要求：

1.两个参数，类型和容器一致

2.返回值为bool

3.函数名不重要，保持和sort的第三个参数一致

4.当lhs和rhs不会发生交换时，要返回真；

例如：升序排序时，左边小于右边不能交换，故当左边<右边时，就要返回真；