Introduction to Sorting

排序入门

冒泡排序

HR - 非常简单

重点题目——在继续学习之前，请尽力解决这道题！

库排序

虽然通常不需要了解排序的实现原理，但你需要知道如何使用内置方法。


《算法竞赛入门》（CPH）	3.2 - C++中的排序	可在自定义结构体部分之前停止学习，该部分会在白银级内容中讲解
C++官方文档	std::sort	参考资料
Codeforces（CF）	C++技巧	前两个技巧与排序相关

静态数组

要对静态数组进行排序，可使用sort(arr, arr + N)，其中$N$为待排序元素的个数。也可通过替换arr和arr + N来指定排序范围。例如，sort(arr + 1, arr + 4)会对索引$[1, 4)$的元素进行排序。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {5, 1, 3, 2, 4};
    int N = 5;
    sort(arr, arr + N);
    for (int i = 0; i < N; i++) cout << arr[i] << " ";  // 输出结果：1 2 3 4 5
    cout << endl;

    int arr2[] = {5, 1, 3, 2, 4};
    sort(arr2 + 1, arr2 + 4);
    for (int i = 0; i < N; i++) cout << arr2[i] << " ";  // 输出结果：5 1 2 3 4
}

动态数组

要对动态数组（向量）进行排序，可使用sort(v.begin(), v.end())（或sort(begin(v), end(v))）。默认的排序函数会将数组按升序排列。同样，也可指定排序范围。例如，sort(v.begin() + 1, v.begin() + 4)会对索引$[1, 4)$的元素进行排序。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v{5, 1, 3, 2, 4};
    sort(v.begin(), v.end());
    // 输出结果：1 2 3 4 5
    for (int i : v) { cout << i << " "; }
    cout << endl;
}

（动态）对与元组数组

默认情况下，C++中的“对”（pair）会先按照第一个元素排序，若第一个元素相等，则再按照第二个元素排序。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int, int>> v{{1, 5}, {2, 3}, {1, 2}};
    sort(v.begin(), v.end());
    /*
    * 输出结果：
    * 1 2
    * 1 5
    * 2 3
    */
    for (pair<int, int> p : v) { cout << p.first << " " << p.second << endl; }
}

元组（tuple）的排序方式与此类似。

题目

警告！

青铜级题目设计时，通常不需要使用时间复杂度为$\mathcal{O}(N\log N)$的排序算法（反复提取最小值的$\mathcal{O}(N^2)$时间复杂度算法通常就足够了）。

状态	来源	题目名称	难度	标签
		CSES	不同的数（Distinct Numbers）	简单	显示标签：排序
		Codeforces（CF）	赌场游戏（Playing in a Casino）	简单	显示标签：排序
		Codeforces（CF）	皮划艇（Kayaking）	中等	显示标签：贪心、排序
http://oj.oldmoon.cn/p/U1617FB3	青铜级	牛为什么过马路 III（Why Did the Cow Cross the Road III）	中等	显示标签：模拟、排序
http://oj.oldmoon.cn/p/U2223DB1	青铜级	牛学院（Cow College）	中等	显示标签：排序
http://oj.oldmoon.cn/p/U1516JB2	青铜级	愤怒的牛（Angry Cows）	困难	显示标签：模拟、排序
		Codeforces（CF）	排列器（Permutator）	困难	显示标签：贪心、排序

注：在“集合入门”模块中还有更多与排序相关的题目。

自我检测

数组$[7, 2, 6, 3, 1]$经过一轮冒泡排序后会变成什么样子？

1. $[2, 6, 3, 1, 7]$

2. $[1, 2, 7, 6, 3]$

3. $[1, 2, 3, 6, 7]$