Skip to content

排序

一、插入排序🧀

（1）简单插入排序🧀

  • 复杂度：最好 \(O(n)\) ，最坏 \(O(n^2)\) ，平均 \(O(n^2)\)
  • 稳定排序✅
  • 直接插入排序✅：依次将每个元素插入到前面有序部分，依次扩大有序区域
  • 折半插入排序：在“将每个元素插入到前面有序部分”过程中使用二分查找

（2）希尔排序🧀

  • 复杂度：最好 \(O(n)\) ，最坏 \(O(n^2)\) ，平均 \(O(n^{1.3})\)
  • 不稳定排序❌
  • 增量 \(d\) ，每隔 \(d\) 个数取数然后在组内进行插入排序（增量是几就有几个组）
  • 第一次增量是所有数据的一半，第二次是上一次的一半（向下取整），到最后一次就是全部插入排序也就是增量是 \(1\)

二、交换排序🧀

（1）冒泡排序🧀

  • 复杂度：最好 \(O(n)\) ，最坏 \(O(n^2)\) ，平均 \(O(n^2)\)
  • 每次从前往后比较相邻两个，逆序就交换，这算冒泡一轮，归位一个元素
  • 每轮排好一个元素，总共 \(n-1\) 轮
  • 每轮少比较一对
  • 稳定排序✅

Success

改进：用一个flag标记某一轮是否发生交换，如果没有交换那么就直接停止

（2）快速排序🧀

  • 复杂度：最好 \(O(n\log n)\) ，最坏 \(O(n^2)\) ，平均 \(O(n\log n)\)
  • 任意取一个元素为枢轴，左边<=枢轴，右边>=枢轴；然后递归处理知道空或者只剩一个
  • 开一个临时变量 \(pivot\) ，然后双指针，挖坑填坑
  • 不稳定排序❌
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Partition(int A[], int left, int right) {
    int pivot = A[left]; // 选最左边为枢轴
    int i = left, j = right;

    while (i < j) {
        while (i < j && A[j] >= pivot)
            j--;
        A[i] = A[j]; // 小的放左边

        while (i < j && A[i] <= pivot)
            i++;
        A[j] = A[i]; // 大的放右边
    }

    A[i] = pivot; // 枢轴归位
    return i;     // 返回枢轴最终位置
}

// 快速排序主函数（递归）
void QuickSort(int A[], int left, int right) {
    if (left < right) {
        int pivotPos = Partition(A, left, right);
        QuickSort(A, left, pivotPos - 1);
        QuickSort(A, pivotPos + 1, right);
    }
}

三、选择排序🧀

（1）简单选择排序🧀

  • 复杂度：永远 \(O(n^2)\)
  • 简单选择排序：✅每轮都在剩下的里面选择最小的换到最前面

（2）堆排序🧀

  • 复杂度：建堆 \(O(n)\) ，排序 \(O(n\log n)\) ，最好最坏都是 \(O(n\log n)\)
  • 必须是完全二叉树，而且必须从左到右连续
  • 大根堆：所有父亲大于孩子
  • 小根堆：所有父亲小于孩子

Tip

\(i\) 号节点，左孩子：\(2i\) ，右孩子：\(2i+1\)

大根堆

① 建堆：从最后一个非叶子节点开始调整，每次堆顶跟下面大的换

② 排序：堆顶换到最后，向下调整新的堆顶

三、归并排序🧀

  • 复杂度：最好 \(O(n\log n)\) ，最坏 \(O(n^2)\) ，平均 \(O(n^2)\)
  • 归并：每次选两个数组中最小的（比较各自剩下元素中的第一个）
  • 归并排序：每轮都对相邻子序列两两归并
  • 稳定排序✅
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) {
  size_t i = 0, j = 0, k = 0;
  while (i < aLen && j < bLen) {
    if (b[j] < a[i]) {  // <!> 先判断 b[j] < a[i]，保证稳定性
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void merge_sort(int *a, int l, int r) {
  if (r - l <= 1) return;
  // 分解
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // 合并
  int tmp[1024] = {};  // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
                       // vector；先将合并的结果放在 tmp 里，再返回到数组 a
  merge(a + l, a + mid, a + mid, a + r, tmp + l);  // pointer-style merge
  for (int i = l; i < r; ++i) a[i] = tmp[i];
}

四、基数排序🧀

  • 复杂度：\(O(d(n+r))\)
  • 低位优先（LSD）：按照个位……放到每个桶里，然后收集，先进先出（链式队列）
  • \(r\) ：基数（桶的个数）
  • \(n\) ：要排的数
  • \(d\) ：最大的位数
  • 稳定排序✅

五、总结复杂度，稳定性🧀

排序类别 排序算法 最好时间复杂度 最坏时间复杂度 平均时间复杂度 辅助空间复杂度 稳定性
插入排序 直接插入排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定
插入排序 折半插入排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定
插入排序 希尔排序 \(O(n)\) \(O(n^2)\) \(O(n^{1.3})\) \(O(1)\) 不稳定
交换排序 冒泡排序 \(O(n)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定
交换排序 快速排序 \(O(n\log_2 n)\) \(O(n^2)\) \(O(n\log_2 n)\) \(O(\log_2 n)\) 不稳定
选择排序 简单选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定
选择排序 堆排序 \(O(n\log_2 n)\) \(O(n\log_2 n)\) \(O(n\log_2 n)\) \(O(1)\) 不稳定
归并排序 归并排序 \(O(n\log_2 n)\) \(O(n\log_2 n)\) \(O(n\log_2 n)\) \(O(n)\) 稳定
基数排序 基数排序 \(O(d(n+r))\) \(O(d(n+r))\) \(O(d(n+r))\) \(O(r)\) 稳定

六、💖排序函数🧀

  • 复杂度 \(nlog(n)\)
1
sort(first,last,comp);

Warning

  • 左闭右开
  • comp是比较函数，sort自带四种sort
  • 默认从小到大
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int a[100];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    //从下标1开始，到下标a+n（左闭右开）
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
}

1、自定义顺序🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int a[100];
int cmp(int x, int y) { // 注意cmp函数的参数类型，此处为int数组
    return x > y;       // 从大到小排序
    //x < y 同理
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
}

2、结构体排序🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int a[100];

struct node {
    int a, b;
} e[100];
int cmp(node n1, node n2) { // 注意cmp函数的参数类型，此处为node结构体
    return n1.b > n2.b;     // 从大到小排序
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> e[i].a >> e[i].b;
    }
    sort(e + 1, e + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        cout << e[i].a << " " << e[i].b;
    }
}

1
2
3
4
5
6
int cmp(node n1, node n2) { // 注意cmp函数的参数类型，此处为node结构体
    if (n1.b == n2.b) {
        return n1.a < n2.a; // 如果b相同，则按a从小到大排序
    }
    return n1.b > n2.b; // 从大到小排序
}

例题🧀

e.g.12 [NOIP2007 普及组] 奖学金🧀

题目背景

NOIP2007 普及组 T1

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 \(5\) 名学生发奖学金。期末，每个学生都有 \(3\) 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 \(3\) 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 \(5\) 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

1
2
7 279  
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 \(7\) 号、\(5\) 号。这两名同学的总分都是 \(279\) (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 \(7\) 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

1
2
5 279  
7 279

则按输出错误处理，不能得分。

输入格式

共 \(n+1\) 行。

第 \(1\) 行为一个正整数 \(n \le 300\)，表示该校参加评选的学生人数。

第 \(2\) 到 \(n+1\) 行，每行有 \(3\) 个用空格隔开的数字，每个数字都在 \(0\) 到 \(100\) 之间。第 \(j\) 行的 \(3\) 个数字依次表示学号为 \(j-1\) 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 \(1\sim n\)（恰好是输入数据的行号减 \(1\)）。

保证所给的数据都是正确的，不必检验。

输出格式

共 \(5\) 行，每行是两个用空格隔开的正整数，依次表示前 \(5\) 名学生的学号和总分。

样例

样例输入 

1
2
3
4
5
6
7
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出 

1
2
3
4
5
6 265
4 264
3 258
2 244
1 237

样例 #2

样例输入 #2

1
2
3
4
5
6
7
8
9
8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

样例输出 #2

1
2
3
4
5
8 265
2 264
6 264
1 258
5 258

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
struct node {
    int Chinese;
    int Math;
    int English;
    int sum;
    int id;
} score[100005];

bool cmp(node a, node b) {
    if (a.sum == b.sum ) {
        if (a.Chinese == b.Chinese)
            return a.id < b.id;
        return a.Chinese > b.Chinese;
    } // 如果总分相同，则语文成绩高的优先，如果语文成绩也相同，则学号小的优先
    return a.sum > b.sum;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        score[i].id = i + 1;
        cin >> score[i].Chinese >> score[i].Math >> score[i].English;
        score[i].sum = score[i].Chinese + score[i].Math + score[i].English;
    }
    sort(score, score + n, cmp);
    for (int i = 0; i <5 ; i++) {
        cout << score[i].id << " " << score[i].sum << endl;
    }
}

e.g.13 数位排序🧀

问题描述

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当 两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时, 将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6, 小于 409 的数位 之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数 \(n,m\), 请问对 1 到 \(n\)采用这种方法排序时, 排在第 \(m\)个的元 素是多少?

输入格式

输入第一行包含一个正整数 \(n\) 。

第二行包含一个正整数 \(m\)。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

1
2
13
5

样例输出

1
3

样例说明

1 到 13 的排序为: \(1,10,2,11,3,12,4,13,5,6,7,8,9\)。第 5 个数为 3 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

struct node {
    int number;
    int sum;
} e[1000005];//一定注意数据规模

bool cmp(node a, node b) {

    if (a.sum == b.sum) {
        return a.number < b.number;
    }
    return a.sum < b.sum;
}
int main() {
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 1; i <= n; i++) {
        e[i].number = i;
        e[i].sum = 0;
    }
    for (int i = 1; i <= n; i++) {
        int number = e[i].number; //注意使用中间变量，不篡改原数组
        while (number) {
            e[i].sum += number % 10;
            number /= 10;
        }
    }
    sort(e + 1, e + 1 + n, cmp); 
    cout << e[m].number << endl ;
}

e.g. 14 排队接水🧀

题目描述

有 \(n\) 个人在一个水龙头前排队接水，假如每个人接水的时间为 \(T_i\)，请编程找出这 \(n\) 个人排队的一种顺序，使得 \(n\) 个人的平均等待时间最小。

输入格式

第一行为一个整数 \(n\)。

第二行 \(n\) 个整数，第 \(i\) 个整数 \(T_i\) 表示第 \(i\) 个人的接水时间 \(T_i\)。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例

样例输入 

1
2
10 
56 12 1 99 1000 234 33 55 99 812

样例输出 

1
2
3 2 7 8 1 4 9 6 10 5
291.90

提示

\(1\le n \leq 1000\)，\(1\le t_i \leq 10^6\)，不保证 \(t_i\) 不重复。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int number;
    int time;
} e[100005];
bool cmp(node a, node b) {
    return a.time < b.time;     //时间从小到大
}
int32_t main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> e[i].time;
        e[i].number = i;
    }
    sort(e + 1, e + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        cout << e[i].number << " ";
    }
    cout << endl;
    double sum=0;
    //e.time[1]*9+e.time[2]*8+…………
    for(int i=1;i<=n;i++){
        sum+=e[i].time*(n-i);
    }
    // cout<<sum<<endl;
    printf("%.2lf",sum/n);
}

e.g.15 ⭐母舰🧀

题目背景

广东汕头聿怀初中 Train#3 Problem 1

（有没有红警既视感~）

题目描述

在小 A 的星际大战游戏中，一艘强力的母舰往往决定了一场战争的胜负。一艘母舰的攻击力是普通的 MA（Mobile Armor）无法比较的。

对于一艘母舰而言，它是由若干个攻击系统和若干个防御系统组成的。两艘母舰对决时，一艘母舰会选择用不同的攻击系统去攻击对面母舰的防御系统。当这个攻击系统的攻击力大于防御系统的防御力时，那个防御系统会被破坏掉。当一艘母舰的防御系统全部被破坏掉之后，所有的攻击都会攻击到敌方母舰本身上去造成伤害。

这样说，一艘母舰对对面的伤害在一定程度上是取决于选择的攻击对象的。

在瞬息万变的战场中，选择一个最优的攻击对象是非常重要的。所以需要写出一个战斗系统出来，判断出你的母舰最多能对对手造成多少伤害并加以实现。

输入格式

输入第一行两个整数 \(M\) 和 \(N\)，表示对方母舰的防御系统数量和你的母舰的攻击系统数量。

接着 \(M\) 行每行一个整数每一个表示对方防御系统的防御力是多少。

接着 \(N\) 行每行一个整数每一个表示己方攻击系统的攻击力是多少。

输出格式

输出仅有一行，表示可以造成的最大伤害。

样例

样例输入 

1
2
3
4
5
6
7
8
9
3 5 
1000 
2000 
1200 
2100 
2000 
1200 
1000 
1000

样例输出 

1
2000

提示

样例解释

对方防御系统有 \(3\) 个，防御值为 \(1000(a),2000(b),1200(c)\)，己方攻击系统有 \(5\) 个，攻击值为 \(2100(d)，2000(e),1200(f),1000(g),1000(h)\)。第 \(1\) 轮攻击的最优方案是 \(d\) 攻击 \(b\)，\(e\) 攻击 \(c\)，\(f\) 攻击 \(a\)，\(g\) 和 \(h\) 攻击对方母舰本身，造成 \(2000\) 点伤害。

数据范围与约定

对于 \(80 \%\) 的数据，\(1 \le N,M \le 1000\)。

对于 \(100 \%\) 的数据，\(1 \le N,M \le 10 ^ 5\)。

—