python/GESP/排序算法.md

## 排序算法专题

### 一、基本知识
有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储 空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

![](https://img-blog.csdnimg.cn/20210714113743879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg3OTM4,size_16,color_FFFFFF,t_70)

#### 口诀: 快选希堆

### 二、快速排序
```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;
}
```