排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
拥有稳定性这一特性的算法会让原本有相等键值的记录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的记录 R R R 和 S S S ，且在原本的列表中 R R R 出现在 S S S 之前，在排序过的列表中 R R R 也将会是在 S S S 之前。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
选择排序、堆排序、快速排序不是稳定排序。
参考链接：复杂度
时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 O O O 表示。
简单计算复杂度的方法一般是统计“简单操作”的执行次数，有时候也可以直接数循环的层数来近似估计。
时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。
基于比较的排序算法的时间复杂度下限是 O ( n l o g n ) O(nlogn) O(nlogn) 的。
当然也有不是 O ( n l o g n ) O(nlogn) O(nlogn) 的。例如，计数排序 的时间复杂度是 O ( n + w ) O(n+w) O(n+w) ，其中 w w w 代表输入数据的值域大小。
与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。
常见算法可以分为两大类：
冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i i i 次扫描后，数列的末尾 i i i 项必然是最大的 i i i 项，因此冒泡排序最多需要扫描 n − 1 n-1 n−1 遍数组就能完成排序。
冒泡排序是一种稳定的排序算法。
在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为 O ( n ) O(n) O(n) 。
在最坏情况下，冒泡排序要执行 ( n − 1 ) n 2 \frac{(n-1)n}{2} 2(n−1)n 次交换操作，时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
冒泡排序的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
void swap(int &a, int &b) {
if (a == b) return;
// x ^ x = 0
// x ^ 0 = x
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
void bubble_sort(int arr[], int n) {
bool swaped = true;
// 直到没有发生交换
while (swaped) {
swaped = false;
for (int i = 0; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swaped = true;
}
}
// 一轮冒泡确定一个最大值
--n;
}
}
选择排序（英语：Selection sort）是排序算法的一种，它的工作原理是每次找出第 i i i 小的元素（也就是 A i . . n A_i..n Ai..n 中最小的元素），然后将这个元素与数组第 i i i 个位置上的元素交换。
由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。
选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O ( n 2 ) O(n^2) O(n2) 。
void swap(int &a, int &b) {
if (a == b) return;
// x ^ x = 0
// x ^ 0 = x
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
void selection_sort(int arr[], int n) {
for (int i = 0; i < n; ++i) {
int min_idx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
插入排序是一种稳定的排序算法。
插入排序的最优时间复杂度为 O ( n ) O(n) O(n) ，在数列几乎有序时效率很高。
插入排序的最坏时间复杂度和平均时间复杂度都为 O ( n 2 ) O(n^2) O(n2) 。
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int cur = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > cur) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = cur;
}
}
归并排序（英语：merge sort）是一种采用了 分治 思想的排序算法。
归并排序分为三个步骤：
1. 将数列划分为两部分；
2. 将数列划分为两部分；
3. 合并两个子序列。
不难发现，归并排序的前两步都很好实现，关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。
归并排序是一种稳定的排序算法。
归并排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O ( n l o g n ) O(nlogn) O(nlogn) 。
归并排序的空间复杂度为 O ( n ) O(n) O(n) 。
int tmp_arr[MAX_N];
void merge_sort(int arr[], int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
// 至此，数组两边均有序
int k = 0, i = l, j = mid + 1;
// 合并
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
tmp_arr[k++] = arr[i++];
else
tmp_arr[k++] = arr[j++];
}
// 处理剩下的
while (i <= mid)
tmp_arr[k++] = arr[i++];
while (j <= r)
tmp_arr[k++] = arr[j++];
// 将数据复制回原数组
for (i = l, j = 0; i <= r; i++, j++)
arr[i] = tmp_arr[j];
}
归并排序还可以用来求逆序对的个数。
所谓逆序对，就是满足 a i > a j a_i>a_j ai>aj 且 i < j i<j i<j 的数对 ( i , j ) (i,j) (i,j) 。
int tmp_arr[MAX_N];
long long merge_sort(int arr[], int l, int r) {
if (l == r) return 0;
int mid = (l + r) >> 1;
long long ans = merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j])
tmp_arr[k++] = arr[i++];
else {
ans += mid - i + 1;
tmp_arr[k++] = arr[j++];
}
}
while (i <= mid)
tmp_arr[k++] = arr[i++];
while (j <= r)
tmp_arr[k++] = arr[j++];
for (i = l, j = 0; i <= r; ++i, ++j)
arr[i] = tmp_arr[j];
return ans;
}
另外，逆序对也可以用 树状数组、线段树 等数据结构求解。这三种方法的时间复杂度都是 O ( n l o g n ) O(nlogn) O(nlogn) 。
Merge Sort - GeeksforGeeks
归并排序 - 维基百科，自由的百科全书
逆序对 - 维基百科，自由的百科全书