1. sort 函数的使用
sort 函数的定义：
sort (first, end, compare);
- sort 对 [first, end) 范围内的元素进行排序。
- 默认为升序排序(此时不需要传入compare)。
- 当需要降序排序时，需要传入比较器 compare。
1.1 普通数组
升序
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int array[10];
for(int i = 0; i < 10; i++) array[i] = 9 - i;
printf("=====排序前=====\n");
for(int i = 0; i < 10; i++) printf("%d ", array[i]);
puts("");
sort(array,array + 10);
printf("=====排序后=====\n");
for(int i = 0; i < 10; i++) printf("%d ", array[i]);
puts("");
return 0;
}
输出结果：
降序
代码：
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int array[10];
for(int i = 0; i < 10; i++) array[i] = i;
printf("=====排序前=====\n");
for(int i = 0; i < 10; i++) printf("%d ", array[i]);
puts("");
sort(array,array + 10, cmp);
printf("=====排序后=====\n");
for(int i = 0; i < 10; i++) printf("%d ", array[i]);
puts("");
return 0;
}
输出结果：
此时为降序排序，需传入比较器 compare。
compare: 一个返回值为 bool 类型的函数。
如代码中 cmp 所写：
- 假定排序完成后的降序是从 左 到 右。
- 需要比较的两个数 a , b 在数组的相对位置为 a 在左， b 在右。
- return true 则代表二者相对位置正确，不需要改变。
- return false 则代表二者相对位置错位，需要改变。
1.2 结构体数组
升序
代码：
#include <iostream>
#include <algorithm>
using namespace std;
struct Student
{
int age;
int score;
bool operator<(const Student& student) const
{
return age < student.age;
}
};
int main()
{
Student students[10];
for(int i = 0; i < 10; i++)
{
students[i].age = 9 - i;
students[i].score = 0;
}
printf("=====排序前=====\n");
for(int i = 0; i < 10; i++) printf("%d ", students[i].age);
puts("");
sort(students,students + 10);
printf("=====排序后=====\n");
for(int i = 0; i < 10; i++) printf("%d ", students[i].age);
return 0;
}
输出结果：
sort 默认为升序排序，当我们期望升序排序时，可以不传入 compare 比较器，只需要重载 < 运算符。
重载 < 运算符的函数返回值为 bool 类型。
- 假定排序完成后的升序是 从 左 到 右。
- *this(当前Student) 和 要比较的Student 的相对位置为 *this 在左， student 在右。
- return true: 二者相对位置正确，不需要改变。
- return fasle: 二者相对位置错误，需要改变。
降序
代码：
#include <iostream>
#include <algorithm>
using namespace std;
struct Student
{
int age;
int score;
};
bool cmp(const Student& a, const Student& b)
{
return a.age > b.age;
}
int main()
{
Student students[10];
for(int i = 0; i < 10; i++)
{
students[i].age = i;
students[i].score = 0;
}
printf("=====排序前=====\n");
for(int i = 0; i < 10; i++) printf("%d ", students[i].age);
puts("");
sort(students,students + 10, cmp);
printf("=====排序后=====\n");
for(int i = 0; i < 10; i++) printf("%d ", students[i].age);
puts("");
return 0;
}
输出结果：
sort 默认为升序排序，当我们期望降序排序时，需要传入 compare 比较器。
如 cmp, 比较器为一个返回值为 bool 类型的函数。
- 假定排序完成后的降序是 从 左 到 右。
- Student a 和 Student b 的相对位置为 a 在左， b 在右。
- return true: 二者相对位置正确，不需要改变。
- return fasle: 二者相对位置错误，需要改变。
混合排序：
仅以一种情况作为说明。
先比较成绩，成绩高的排在前面(成绩降序)，若成绩相同，则比较年龄，年龄小的排在前面(年龄升序)。
bool cmp(const Student& a, const Student& b)
{
if(a.score == b.score)
return a.age < b.age;
else
return a.score > b.score;
}
sort(students,students + 10, cmp);
sort 默认为升序排序，当我们期望混合排序时，需要传入 compare 比较器。
如 cmp, 比较器为一个返回值为 bool 类型的函数。
- 假定排序完成后的降序是 从 左 到 右。
- Student a 和 Student b 的相对位置为 a 在左， b 在右。
- return true: 二者相对位置正确，不需要改变。
- return fasle: 二者相对位置错误，需要改变。
1.3 标准库容器
以 vector 为例：
// 内置类型：int, double , string ... 等重载过 < 的类型
vector<int> vec1;
//升序：
sort(vec1.begin(),vec.end());
//降序：
bool cmp(int a, int b)
{
return a > b;
}
sort(vec1.begin(),vec1.end(),cmp);
// 自定义类型
vector<Student> vec2;
// 升序：
struct Student
{
int age;
int score;
bool operator<(const Student& student) const
{
return age < student.age;
}
};
sort(vec2.begin(),vec2.end());
// 降序：
bool cmp(const Student& a, const Student& b)
{
return a.age > b.age;
}
sort(vec2.begin(),vec2.end(),cmp);