C++中的sort函数

sort()函数使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)。要使用algorithm头文件下的sort()函数,需要加上#include头文件和”using namespace std;”

1、在介绍sort()函数之前,先来了解algorithm头文件下一些其他的函数

(1)max(x,y)和min(x,y)分别返回x和y中的最大值和最小值(x和y可以是浮点数)。
(2)abs(x)返回x的绝对值,这里的x必须是整数,浮点数需要使用math头文件下的fabs。
(3)swap()用来交换x和y的值,注意:这里的swap()函数和Java中的swap()函数有着本质的不同。
(4)reverse(x,y)将数组指针在[x,y)之间的元素或容器的迭代器在[x,y)范围内的元素进行反转。
(5)next_permutation(x,y)给出一个序列在全排列的下一个序列。
(6)fill(x,y,a)可以把数组或容器中的array[x]~array[y-1]区间赋值为a。和memset不同,这里的赋值可以是数组类型对应范围中的任意值。
(7)lower_bound(first,last,val)和upper_bound(first,last,val)分别用来寻找在数组或容器[first,last)范围内第一个值大于等于val和第一个值大于val的元素的位置,如果是数组,则返回该位置的指针;如果是容器,则返回该位置的迭代器。如果数组或者容器中没有需要寻找的元素,则两个函数均返回可以插入该元素的位置的指针或者迭代器,它们的时间复杂度均为O(log(last-first))。

2、sort()函数

(1)使用方式:sort(首元素地址(必填),尾元素地址的下一个地址(必填),比较函数(非必填));
如果不填比较函数,则默认对前面给出的区间[first,last)进行递增排序。

(2)比较函数cmp
a、基本数据类型数组的排序

bool cmp(int a,int b){//int型数据递减排序
    return a>b;//当a>b是把a放在b前面
}

bool cmp(double a,double b){//double型数据递减排序
    return a>b;
}

bool cmp(char a,char b){//char型数据递减排序
    return a>b;
}

其实这里也可不必如此:sort(a,a+10,greater<typename>());也可以实现以上三个比较函数的功能。 

b、结构体数组的排序

struct node{
    int x,y;
}st[10];

bool cmp(node a,node b){//递减排序
    return a.x>b.x;
}

bool cmp(node a,node b){//先按x从大到小排序,但当x相等时,按照y从小到大来排序
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}

sort(st,st+3,cmp);//对下标为0,1,2的结构体类型排序

c、容器的排序

在STL标准容器中,只有vector、string、deque是可以使用sort的。这是因为set、map这种容器是用红黑树实现的,元素本身有序,故不允许使用sort排序。以vector为例:

bool cmp(int a,int b){
    return a>b;
}

vector<int> v;
v.push_back(3);
v.push_back(1);
v.push_back(2);
sort(v.begin(),v.end(),cmp);//对整个vector排序