前言
咱们初学编程的可能最先接触的算法就是排序算法了吧，不知道你是不是被正在被各种排序算法折磨着😭，没关系咱们可以调用排序函数啊🥰，不管是c语言还是c++都提供不同的排序函数，通过调用这些函数，可以让你刷题更快呀！一起来看看吧！
qsort函数（c语言用）
它是C语言中自带函数库中的一个函数，包含在 头文件中
下面是 qsort() 函数的声明☺
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
各参数及其说明
base -- 指向要排序的数组的第一个元素的指针
nitems -- 由 base 指向的数组中元素的个数
size -- 数组中每个元素的大小（以字节为单位）
compar -- 用来比较两个元素的函数，即函数指针（比较算法的回调函数）
参数compar详细说明
compar参数指向一个比较两个元素的函数。比较函数的原型应该像下面这样。注意两个形参必须是const void *型🤔，同时在调用compar 函数（compar实质为函数指针，这里称它所指向的函数也为compar）时，传入的实参也必须转换成const void *型。在compar函数内部会将const void *型转换成实际类型，见下文。
int compar(const void *p1, const void *p2);
如果compar返回值小于0（< 0），那么p1所指向元素会被排在p2所指向元素的前面
如果compar返回值等于0（= 0），那么p1所指向元素与p2所指向元素的顺序不确定
如果compar返回值大于0（> 0），那么p1所指向元素会被排在p2所指向元素的后面
听到这是不是感觉有点懵😬，没关系其实你只要记住下面的cmp函数写法就能解决大部分问题😉
int cmp(const void *p1, const void *p2) { return (*(int *)p1) - (*(int *)p2); //这是升序排序 } int cmp(const void *p1, const void *p2) { return (*(int *)p2) - (*(int *)p1); //这是降序排序 } //注意再c语言中cmp函数返回值必须是int型传入的两个参数的类型必须都是const void* //不要忘了对p1和p2进行强制类型转换，cmp函数的返回值 //是int型，所以要将本身是const void * 型的强制类型转换（int *）后再解引用*
我们知道了函数的原型后，那在刷题的时候我们怎么用这个函数呢？
比如我们想用qsort来排序这样一个数组：
int a[5] = {4, 5, 3, 2, 1};
我们需要这样写：
qsort(a, 5, sizeof(int), cmp);
然后在主函数前面加上我们的cmp函数
int cmp(const void *p1, const void *p2) { return (*(int *)p1) - (*(int *)p2); } //注意再c语言中cmp函数返回值必须是int型传入的两个参数的类型必须都是const void* //不要忘了对p1和p2进行强制类型转换，cmp函数的返回值 //是int型，所以要将本身是const void * 型的强制类型转换（int *）后再解引用*
这样数组 a 就会实现升序排列：
{1, 2, 3, 4, 5};
怎么样是不是写起来比冒泡排序、归并排序快多了🤭
qsort用法实例
/* qsort example */ #include <stdio.h> /* printf */ #include <stdlib.h> /* qsort */ int values[] = { 40, 10, 100, 90, 20, 25 }; int cmp (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); //升序 } int main () { int n; qsort (values, 6, sizeof(int), cmp); for (n=0; n<6; n++) printf ("%d ",values[n]); return 0; }
分析一下cmp函数。如果a小于b，则返回值为负数（< 0），也即a会排在b的前面。同理，若a大于b，则a会排在b的后面。所以，这里的qsort()为从小到大即升序排序。因此，运行结果为：10 20 25 40 90 100
如果想让数组降序排列，只需将cmp函数里的
return ( *(int*)a - *(int*)b );
改为
return ( *(int*)b - *(int*)a );
结合上文提到的compar参数的详细说明，想想为什么吧🤔
注意受函数排序规则的底层实现影响，c语言使用cmp函数必须这样写return ( *(int*)a - *(int*)b );而不能写成return ( *(int*)a < *(int*)b );（这样写编译器会报错的）😓
sort函数（用于c++）
sort函数包含在头文件为#include的c++标准库中，调用标准库里的排序方法可以实现对数据的排序😀
sort模板及其参数说明
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
第一个参数first：是要排序的数组的起始地址
第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）
第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。
sort实例
1、对整型数组的排序
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a[6] = {8,6,4,1,3,9}; //将a[0]~a[3]从小到大排序 sort(a,a+4); //sort第三个参数是选填的，不填默认升序 for(int i = 0;i < 6;i++){ printf("%d",a[i]); } return 0; } 运行结果: 1 4 6 8 3 9
2、对于字符数组的排序，默认为字典序
#include<stdio.h> #include<algorithm> using namespace std; int main(){ char a[] = {'K','H','T','A'}; sort(a,a+4); for(int i = 0;i < 4;i++){ printf("%c",a[i]); } return 0; } 运行结果: AHKT
以上两个例子都没有定义cmp函数，那如果自定义cmp函数会怎么样呢😜？
3、对int型数组从大到小排序：
#include<stdio.h> #include<algorithm> using namespace std; bool cmp(int a,int b){ return a > b;//意：设定排序规则为从大到小排序 } int main(){ int a[6] = {8,6,4,1,3,9}; sort(a,a+6,cmp);//使用cmp函数 for(int i = 0;i < 6;i++){ printf("%d",a[i]); } return 0; } 运行结果: 9 8 6 4 3 1
4、对于char型数组从大到小排序：
#include<stdio.h> #include<algorithm> using namespace std; bool cmp(char a,char b){ return a > b; } int main(){ char a[] = {'K','H','T','A'}; sort(a,a+4,cmp); for(int i = 0;i < 4;i++){ printf("%c",a[i]); } return 0; } 运行结果: TKHA
注意 ：
qsort和sort函数都是基于快速排序实现的，而快排是不稳定排序😓
不稳定性是指，对于指定区域内相等的元素，sort函数可能无法保证数据的元素不发生相对位置不发生改变。 这对于普通的排序问题可能没有影响，比如对于 2 2 3 1 5 排序后 1 2 2 3 1 5 （排序前第一个二可能在这里是第二个2） 但是在这里，这些2么有其他含义，对题解影响不大 ！！！但是要注意 假如上述两个2风别代表月份和日 那这里可能就会产生歧义
也是因为这个特点，直接用sort或qsort函数做oj上的一些特别的题时，可能会出现输出结果正确但一提交就不对这种情况（我就被这所谓的不稳定排序坑了好几次😵）大家要根据题意合理使用啊！🥰
你学会了吗？快去刷几道题试试吧！
