插入排序
插入排序的重点在于：在排第 $k$ 个元素的时候，前 $k-1$ 个已经有序。因此只要把第 $k$ 个元素放到它应该在的地方即可。1
2
3
4
5
6
7
8
9
10
11
12void sort1(int* a, int n){
for(int i = 1; i < n; ++i){
int tmp = a[i], j;
for(j = i; j > 0; --j){
if(tmp < a[j - 1])
a[j] = a[j - 1];//向后面移动
else
break;
}//寻找位置
a[j] = tmp;//插入
}
}
选择排序
简单直观的排序方法。
始终寻找当前的最小值，放在它应当在的地方。1
2
3
4
5void sort2(int *a, int n){
for(int i = 0; i < n - 1; ++i)
for(int j = i + 1; j < n; ++j)
if(a[i] > a[j])swap(a[i], a[j]);
}
冒泡排序
比较相邻元素，调整顺序以达到排序的目的。1
2
3
4
5
6void sort3(int *a, int n){
for(int i = 0; i < n - 1; ++i)
for(int j = 0; j < n - i; ++j)
if(a[j] > a[j + 1])
swap(a[j], a[j + 1]);//交换过程
}
希尔排序
希尔排序使用了一个序列（称之为增量序列）
其中 。
排序时，从大到小依次选择增量。设当前选择的增量为 ，则将序列划为若干组，元素之间间隔为 ，然后每组内部进行一个插入排序。随着增量减小数据间的有序程度也就越高，最终在增量达到 $1$ 时达到有序。
增量序列的选择直接与算法的效率挂钩。此处用的为 $Hibbard$ 增量，即 $1,3,7,…,2^k-1$。如果选择的增量较好的话可以达到比较高的效率，如 $O(n^{7/6})$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void sort4(int *a, int n){
int h[] = {1, 3, 7, 15, 31};
for(int i = lower_bound(h, h + 5, n) - h - 1; i >= 0; --i){//寻找最大增量
for(int j = h[i]; j < n; ++j){
int tmp = a[j], k;
for(k = j; k >= h[i]; k -= h[i]){
if(tmp < a[k - h[i]])
a[k] = a[k - h[i]];
else
break;
}
a[k] = tmp;
}
}
}
以上为常见的 $O(n^2)$ 排序算法。
归并排序
分治算法的典型应用，将数据层层分割，直到最简单的两个一组的情况，然后不断进行二路归并。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void Merge(int *a, int *tmp, int lhead, int rhead, int rend){
int lpos = lhead, rpos = rhead, tpos = lhead;
while (lpos < rhead && rpos < rend){
if (a[lpos] < a[rpos])
tmp[tpos++] = a[lpos++];
else
tmp[tpos++] = a[rpos++];
}
while(lpos < rhead) tmp[tpos++] = a[lpos++];
while(rpos < rend) tmp[tpos++] = a[rpos++];
for(int i = lhead; i < rend; ++i)
a[i] = tmp[i];
}
void MergeSort(int *a, int left, int right){//左闭右开
int n = right - left, mid = (right + left) >> 1;
if(n == 1)return ;
MergeSort(a, left, mid);
MergeSort(a, mid, right);
Merge(a, b, left, mid, right);
}
归并排序一个典型的应用是用于统计逆序对的数量。我们知道，对一个逆序对，要么两个元素都在左半边。要么都在右半边，要么一个在左半边一个在右半边。都在左半边或者右半边的我们递归的去求，而对第三种情况我们在二路归并的时候统计。
原地归并排序
原地归并排序的思想在于“交换”。
原版归并排序的瓶颈在于，进行二路归并的时候，必须要使用辅助数组帮助归并。而原地归并排序使用的是一种交换的策略。设当前要合并的两个数组的头指针分别为 $i, j$。我们先将 $i$ 向后移动，直到其到达 $j$ 处或者 $i$ 指向的数大于 $j$ 指向的数。然后，我们用另一个指针，设为 $k$，从 $j$ 处向后移动，直到 $k$ 指向的数大于 $i$ 指向的数。
这时容易发现，$i$ 之前的数都已经在应该在的位置上了。而如果把 $[j, k)$ 与 $[i, j)$ 这两段数交换位置，那么 $[j, k)$ 也将就位。而交换两段序列可以用经典的“手摇”算法在线性时间内解决。交换完之后，将 $i$ 向后移动 $k-j$ 个位置，将 $j$ 移动到 $k$ 的位置，然后递归的做下去，直到二路归并完成。
容易发现，在某些情况下原地归并排序的二路归并过程时间复杂度可以达到 $O(n^2)$ 的水平，因此一般情况下并不使用这种算法。
快速排序
快速排序的关键在于选择基准以及分割策略，其余的工作交给递归即可。
一种比较优秀的选择基准的方法是对最左端，最右端，和最中间的三个数排序，选择第二大（即中间大小）的数作为基准。这种选择比纯粹的随机选择和固定的选择更加高明。之后，将基准和当前序列的倒数第二个值交换。（这种选择基准的方法出自《数据结构与算法分析：C 语言描述（第二版）》）
分割时，利用两个指针，其中一个（设为 $i$）从最左边向右扫，另一个（设为 $j$）从倒数第二个位置向左扫。$i$ 只会在大于或等于基准的位置停下，$j$ 只会在小于或等于基准的位置停下。此时若 $i<j$，那么交换 $i$ 和 $j$ 对应的数；若 $i \ge j$，那么指针停止行动，本次分割结束。之后由于 $i$ 指针左右分别为小于等于和大于等于基准的数，故把基准换到 $i$ 所在位置，再对 $i$ 两侧递归执行排序。
以上的做法避免了几个隐患：
- 基准换到倒数第二个位置，为 $i$ 提供了一个界限；同时选择基准时进行的排序也为 $j$ 提供了一个界限。
- $i$ 和 $j$ 在遇到等于基准的值时都会停下，这是因为当多个相同元素存在时，若 $i$ 和 $j$ 都不停下，那么 $i$ 会一直进行到接近末尾的地方，导致分割出来的左右两边序列长度不均衡，进而导致算法实际运行效率变差。
1 | void Median3(int *a, int left, int right){ |
堆排序
建立一个堆，直接操作即可。此处不再赘述。
以上为常见的 $O(n\log n)$ 排序算法。
记数排序
计数排序的中心思想是：对于每一个输入的元素 $x$，确定小于或等于 $x$ 的元素的个数。利用这一信息，即可把该元素放在他应在的位置。
它的时间复杂度是 $O(n+w)$，其中 $n$ 是被排序的数的数目，$w$ 是被排序的数的值域大小。1
2
3
4
5
6
7
8
9
10void CountingSort(int *a, int *cnt, int *ans, int n){
for(int i = 0; i <= 10; ++i)
cnt[i] = 0;
for(int i = 0; i < n; ++i)
cnt[a[i]]++;
for(int i = 1; i <= 10; ++i)
cnt[i] += cnt[i - 1];
for(int i = n - 1; i >= 0; --i)
ans[--cnt[a[i]]] = a[i];
}
基数排序
基数排序执行这样一个过程：对 $n$ 个 $d$ 位数，从最低位开始，一直到最高位，以数的当前位上的数字作为关键字进行排序。
桶排序
桶排序将 $n$ 个分布在 $[0,1)$ 上的实数放入 $m$ 个“桶”里，每个桶对应着一个区间，并且对每一个桶里的数据进行排序，以达到总体的有序。
以上为常见的线性时间复杂度排序算法。
拓展：对 10 亿个互不相同的 32 位整数排序
这是一个非常经典的问题。在这个题目中，直接使用 $O(n\log n)$ 级别的排序算法效率会很差。因此，我们考虑利用条件本身。
条件是 10 亿个不同的 32 位整数，那么我们就可以用 32 亿个 bit 位用于标记。遍历这些数，对于数 $i$，将第 $i$ 个 bit 位置为 1。处理完所有的数后，按 bit 位的编号从小到大遍历一遍 bit 位，依次将是 1 的 bit 位的下标放进数组里。这样就完成了排序。这种排序方法和 $O(n\log n)$ 的排序方法相比，无论是时间还是空间都占优。
参考资料：
- 《数据结构与算法分析：C 语言描述（第二版）》
- 《算法导论》