一、排序简介
排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法．排序算法多种多样，性质也大多不同．
稳定性
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变．
拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 𝑅 和 𝑆，且在原本的列表中 𝑅 出现在 𝑆 之前，在排序过的列表中 𝑅 也将会是在 𝑆 之前．
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序．
选择排序、堆排序、快速排序、希尔排序不是稳定排序．
时间复杂度
时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 𝑂 表示．
简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计．
时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度．OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了．
基于比较的排序算法的时间复杂度下限是 𝑂(𝑛log𝑛) 的．
当然也有不是 𝑂(log𝑛) 的．例如:计数排序的时间复杂度是 𝑂(𝑛 +𝑤)，其中 𝑤 代表输入数据的值域大小．
空间复杂度
与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模．一般来说，空间复杂度越小，算法越好．
二、选择排序
选择排序（英语：Selection sort）是一种简单直观的排序算法．它的工作原理是每次找出第 𝑖 小的元素，然后将这个元素与数组第 𝑖 个位置上的元素交换．
稳定性
选择排序的稳定性取决于其具体实现．
倘若使用链表实现，由于链表的任意位置插入和删除均为 𝑂(1) ，故无需使用 swap（交换两个元素）操作：每次从未排序部分选择最小元素（若有多个，选取第 1 个）后，将其插入到未排序部分的第 1 个元素之前，这样就能够保证稳定性．
假如使用数组实现（OI 中一般的实现方式），由于数组任意位置插入和删除均为 𝑂(𝑛) ，故只能使用 swap 将未排序部分的元素移到已排序部分．swap 操作使得数组实现的选择排序不稳定．
下面给出的实现示例均是基于数组元素的交换，因此均为不稳定的．
时间复杂度
选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 𝑂(𝑛2) ．
代码实现
void selection_sort(int a, int n) {
for (int i = 1; i < n; ++i) {
int ith = i;
for (int j = i + 1; j <= n; ++j) {
if (a[j] < a[ith]) {
ith = j;
}
}
swap(a[i], a[ith]);
}
}
三、冒泡排序
定义
冒泡排序（英语：Bubble sort）是一种简单的排序算法．由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序．
过程
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换．当没有相邻的元素需要交换时，排序就完成了．
经过 𝑖 次扫描后，数列的末尾 𝑖 项必然是最大的 𝑖 项，因此冒泡排序最多需要扫描 𝑛 −1 遍数组就能完成排序．
稳定性
冒泡排序是一种稳定的排序算法．
时间复杂度
在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 𝑂(𝑛)．
在最坏情况下，冒泡排序要执行 2𝑛(𝑛−1)次交换操作，时间复杂度为 𝑂(𝑛2)．
冒泡排序的平均时间复杂度为 𝑂(𝑛2)．
代码实现
// 假设数组的大小是 n + 1，冒泡排序从数组下标 1 开始
void bubble_sort(int *a, int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
四、插入排序
定义
插入排序（英语：Insertion sort）是一种简单直观的排序算法．它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置．
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌．
稳定性
插入排序是一种稳定的排序算法．
时间复杂度
插入排序的最优时间复杂度为 𝑂(𝑛)，在数列几乎有序时效率很高．
插入排序的最坏时间复杂度和平均时间复杂度都为 𝑂(𝑛2)．
代码实现
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
五、sort快速排序
定义
快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法．
基本原理与实现
过程
快速排序的工作原理是通过 分治 的方式来将一个数组排序．
快速排序分为三个过程：
- 将数列划分为两部分（要求保证相对大小关系）；
- 递归到两个子序列中分别进行快速排序；
- 不用合并，因为此时数列已经完全有序．
和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系．具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数．为了保证平均时间复杂度，一般是随机选择一个数 𝑚 来当做两个子数列的分界．
之后，维护一前一后两个指针 𝑝 和 𝑞，依次考虑当前的数是否放在了应该放的位置（前还是后）．如果当前的数没放对，比如说如果后面的指针 𝑞 遇到了一个比 𝑚 小的数，那么可以交换 𝑝 和 𝑞 位置上的数，再把 𝑝 向后移一位．当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇．
其实，快速排序没有指定应如何具体实现第一步，不论是选择 𝑚 的过程还是划分的过程，都有不止一种实现方法．
第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了．
代码实现
bool cmp(int a, int b){
return a>b;
}
int main(){
int n, a[1000005];
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];
}
return 0;
}
六、桶排序
定义
桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况．
过程
桶排序按下列步骤进行：
- 设置一个定量的数组当作空桶；
- 遍历序列，并将元素一个个放到对应的桶中；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把元素再放回原来的序列中．
稳定性
如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法．
由于每块元素不多，一般使用插入排序．此时桶排序是一种稳定的排序算法．
时间复杂度
桶排序的平均时间复杂度为 𝑂(𝑛 +𝑛2/𝑘 +𝑘)（将值域平均分成 𝑛 块 + 排序 + 重新合并元素），当 𝑘 ≈𝑛 时为 𝑂(𝑛).
桶排序的最坏时间复杂度为 𝑂(𝑛2)．
实现
constexpr int N = 100010;
int n, w, a[N];
vector<int> bucket[N];
void insertion_sort(vector<int>& A) {
for (int i = 1; i < A.size(); ++i) {
int key = A[i];
int j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
}
void bucket_sort() {
int bucket_size = w / n + 1;
for (int i = 0; i < n; ++i) {
bucket[i].clear();
}
for (int i = 1; i <= n; ++i) {
bucket[a[i] / bucket_size].push_back(a[i]);
}
int p = 0;
for (int i = 0; i < n; ++i) {
insertion_sort(bucket[i]);
for (int j = 0; j < bucket[i].size(); ++j) {
a[++p] = bucket[i][j];
}
}
}
