排序

基础

排序是必须掌握的基本算法,也是学习其他算法的基础。
最好能做到手写各种排序算法。

基础排序算法

冒泡排序

1
2
3
4
5
6
7
8
9
for (int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}

使用库函数排序

一般可以直接调用系统排序函数进行排序,不需要自己手写。

在C++中调用sort函数

1
2
#include<algorithm>
sort(buf,buf+n);

sort函数的两个参数表示,待排序内存的起始地址和结束地址


sort函数的排序方式可以自定义

1
2
3
4
bool cmp(int x , int y){
return x>y;
}
sort(buf,buf+n,cmp); //降序排列

对于cmp函数,传递的两个参数x,y,可以理解为,这两个数的当前顺序也就是,x在y的前面。
当返回值就是对这种初始顺序的肯定与否定。
一般来说,升序就是< , 降序就是>.

比较字符串

在c语言里面

1
2
3
4
5
6
7
8
#include<string.h>
char a[]="abc";
char b[]="bdf";
int ptr;
ptr = strcmp(a,b);
// ptr>0 a>b
// ptr<0 a<b
// ptr=0 a=b

在C++里面:

1
2
3
4
string a="abc";
string b="dfg";
可以直接比较
if(a<b)....

重载运算符

对于结构体,可以通过重载运算符的方式来自定义排序方式

1
2
3
4
5
6
7
8
9
10
struct student{
string name;
int age;
int score;
bool operator < (const student b) const {
if(score!=b.score) return score<b.score;
if(name!=b.name) return name<b.name;
else return age<b.age;
}
};