|
|
## 排序算法专题
|
|
|
|
|
|
### 一、基本知识
|
|
|
有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：
|
|
|
|
|
|
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序
|
|
|
|
|
|
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
|
|
|
|
|
|
3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储 空间进行比较和交换的数据排序。
|
|
|
|
|
|
4、非原地排序：需要利用额外的数组来辅助排序。
|
|
|
|
|
|
5、时间复杂度：一个算法执行所消耗的时间。
|
|
|
|
|
|
6、空间复杂度：运行完一个算法所需的内存大小
|
|
|
|
|
|
|
|
|
|
|
|
#### 口诀: 快选希堆
|
|
|
|
|
|
### 二、快速排序
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 100010;
|
|
|
int q[N];
|
|
|
int n;
|
|
|
|
|
|
/**
|
|
|
* 功能：利用快速排序对数组进行排序
|
|
|
* @param q 要排序的数组
|
|
|
* @param l 左端下标位置
|
|
|
* @param r 右端下标位置
|
|
|
*/
|
|
|
void quick_sort(int q[], int l, int r) {
|
|
|
if (l >= r) return;
|
|
|
int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
|
|
|
while (i < j) {
|
|
|
do i++;
|
|
|
while (q[i] < x);
|
|
|
do j--;
|
|
|
while (q[j] > x);
|
|
|
if (i < j) swap(q[i], q[j]);
|
|
|
}
|
|
|
quick_sort(q, l, j), quick_sort(q, j + 1, r);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
scanf("%d", &n);
|
|
|
for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
|
|
|
quick_sort(q, 1, n);
|
|
|
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 三、归并排序
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 1e5 + 10;
|
|
|
int q[N], t[N];
|
|
|
|
|
|
void merge_sort(int q[], int l, int r) {
|
|
|
if (l >= r) return;
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
|
|
|
|
|
|
int i = l, j = mid + 1, k = 0;
|
|
|
while (i <= mid && j <= r)
|
|
|
if (q[i] <= q[j])
|
|
|
t[k++] = q[i++];
|
|
|
else
|
|
|
t[k++] = q[j++];
|
|
|
|
|
|
while (i <= mid) t[k++] = q[i++];
|
|
|
while (j <= r) t[k++] = q[j++];
|
|
|
for (i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int n;
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) cin >> q[i];
|
|
|
|
|
|
merge_sort(q, 1, n);
|
|
|
for (int i = 1; i <= n; i++) printf("%d ", q[i]);
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 四、结构体自定义排序
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
// 学生的结构体
|
|
|
struct Node {
|
|
|
string name;
|
|
|
int math;
|
|
|
int english;
|
|
|
};
|
|
|
|
|
|
// 函数实现
|
|
|
bool cmp(Node &a, Node &b) {
|
|
|
if (a.math == b.math)
|
|
|
return a.english > b.english; // math相等，按endlish从大到小排序23
|
|
|
return a.math > b.math; // 按math从大到小排序
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 先按math从大到小排序，math相等，按english从大到小排序
|
|
|
Node a[4] = {{"XiaoMing", 67, 89}, {"LiLei", 90, 56}, {"ZhaoSi", 90, 99}};
|
|
|
sort(a, a + 3, cmp);
|
|
|
|
|
|
for (int i = 0; i < 3; i++)
|
|
|
cout << a[i].name << " " << a[i].math << " " << a[i].english << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
