C++中 Sort函数详细解析

C++中 Sort函数详细解析

本文详细介绍了C++中sort函数的使用方法，包括其调用方式、使用场景、排序原理以及具体的应用案例。对于C++开发者来说，这篇文章具有很高的参考价值。

前言

sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变，如果某些场景需要保持相同元素间的相对顺序，可使用
stable_sort
函数，这里不过多介绍。

一、sort函数调用的两种方式

默认:两个参数
first
,
last
，将
[first, last)
区间内元素升序排列。【注意区间为左闭右开】

自定义排序:需用户指定排序规则
Compare comp
,将
[first, last)
区间内的元素按照用户指定的顺序排列。

二、sort函数使用场景

由于在排序过程中涉及到元素交换等操作，所以sort函数仅支持可随机访问的容器，如数组， string、vector、deque等。

三、sort函数排序原理

sort()
并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

所以无论元素初始时为何种状态，
sort()
的平均排序复杂度为均为O(N*log2(N)) ，具有不错的的性能，在刷算法题时，可以直接使用sort()来对数据进行排序，而不需手动编写排序函数。

四、sort函数使用案例

1.升序排列

sort函数如果不传入第三个参数，则默认是升序排列。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
 // 方式一、使用数组
 int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(a, a + 10); // 10为元素个数
 for (int i = 0; i < 10; i++) cout << a[i] << ' '; // 输出排序后数组
 cout << endl;
 // 方式二、使用 vector
 vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(arr.begin(), arr.end()); // 10为元素个数
 for (int i = 0; i < 10; i++) cout << arr[i] << ' '; // 输出排序后数组
 return 0;
}

2.降序排列

实现方式1

实现降序排列，需传入第三个参数–比较函数，
greater()
，这里的元素为
int
类型，即函数为
greater()
; 如果是其他基本数据类型如
float
、
double
、
long
等也是同理。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
 // 方式一、使用数组
 int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(a, a + 10, greater<int>()); // 10为元素个数
 for (int i = 0; i < 10; i++) cout << a[i] << ' '; // 输出排序后数组
 cout << endl; // 输出 9 8 7 6 5 4 3 2 1 0 
 // 方式二、使用 vector
 vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(arr.begin(), arr.end(), greater<int>());
 for (int i = 0; i < 10; i++) cout << arr[i] << ' '; // 输出排序后数组
 return 0;
}

实现方式2

我们也可以使用自定义的比较函数，函数的返回值为
bool
类型，例如：

bool cmp(int num1, int num2) {
 return num1 > num2; // 可以简单理解为 > 降序排列; < 升序排列
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int num1, int num2) {
 return num1 > num2; // 可以简单理解为 >： 降序排列; < ： 升序排列
}
int main() {
 // 一、使用数组
 int a[10] = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(a, a + 10, cmp); // 使用自定义排序函数
 for (int i = 0; i < 10; i++) cout << a[i] << ' '; // 输出排序后数组
 cout << endl; // 输出 9 8 7 6 5 4 3 2 1 0 
 // 二、使用 vector
 vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
 sort(arr.begin(), arr.end(), cmp); // 使用自定义排序函数
 for (int i = 0; i < 10; i++) cout << arr[i] << ' '; // 输出排序后数组
 return 0;
}

3.结构体排序(自定义比较函数)

要对元素进行排序，前提是元素之间可以进行比较，即谁大谁小。 基本数据类型可直接进行大小比较， 但结构体元素之间的大小关系需要我们自己指定，如果不指定，则结构体之间大小关系就不确定，则不能够排序。

结构体排序案例1: 对学生信息进行排序
学生有
姓名
，
分数
两个属性,

struct Student { // 学生结构体
 string name; // 学生姓名
 int grade; // 学生分数
 Student(); // 无参数构造函数
 Student(string name, int grade) : name(name), grade(grade) {}; // 有参数构造函数
};

需求：对一个班级内的学生成绩进行排序，首先按成绩进行排序降序排列，若成绩相同，则按照姓名字典顺序升序排列。

自定义排序函数;

bool cmp(Student s1, Student s2) { // 自定义排序
 if (s1.grade != s2.grade) { // 如果学生成绩不相同
 return s1.grade > s2.grade; // 则按照成绩降序排列
 }
 return s1.name < s2.name; // 否则按照姓名升序排列
}

排序代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Student { // 学生结构体
 string name; // 学生姓名
 int grade; // 学生分数
 Student(); // 无参数构造函数
 Student(string name, int grade) : name(name), grade(grade) {}; // 有参数构造函数
};
bool cmp(Student s1, Student s2) { // 自定义排序
 if (s1.grade != s2.grade) { // 如果学生成绩不同
 return s1.grade > s2.grade; // 则按照成绩降序排列
 }
 return s1.name < s2.name; // 否则按照姓名升序排列
}
int main() {
 vector<Student> studs;
 studs.emplace_back("Bob", 80);
 studs.emplace_back("Ali", 90);
 studs.emplace_back("Ann", 85);
 studs.emplace_back("Liming", 90);
 studs.emplace_back("Trump", 79);
 studs.emplace_back("Fury", 58);
 studs.emplace_back("Jam", 62);
 studs.emplace_back("Lucy", 89);
 sort(studs.begin(), studs.end(), cmp); // 排序
 for (int i = 0; i < studs.size(); i++) { // 输出结果
 cout << studs[i].name << "\t" << studs[i].grade << endl;
 }
 return 0;
}

五、自定义comp函数返回true或false作用

bool cmp(int num1, int num2) { // 实现降序排列
 return num1 > num2; // num1大于num2时返回true，否则返回false
}

自定义函数返回值为
bool
类型

• 若返回
  true
  ，则表示
  num1
  与
  num2
  应该交换顺序；
• 若返回
  false
  , 则
  num1
  与
  num2
  保持原有顺序；

下面举例说明自定义比较函数的执行过程:

对 2, 5, 1, 3, 4 降序排列
调用cmp函数时，将5赋值给num1, 2赋值给num2 (注意顺序)
5 > 2, 返回true，num1 与 num2需进行交换；即5应该在2的前面
数组变为 5, 2, 1, 3, 4
第二次 将3赋值给num1, 1赋值给num2，
3 > 1, 返回true，num1 与 num2需进行交换；即3应该在1的前面
数组变为 5, 2, 3, 1, 4
之后经过数次的比较与交换最终排序完成。

最终得到 5 4 3 2 1