1.选择排序
每次找出第 i 小的元素（也就是 a[i] ~ a[n] 中最小的元素），然后将这个元素与数组上第 i 个位置上的元素互换。
时间复杂度：$O(n^2)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
| void ssort(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]);
}
}
|
2.冒泡排序
依次检查两两相邻的元素，如果满足给定的排序条件，就将相邻的两个元素交换。
时间复杂度：$O(n^2)$
代码：
1
2
3
4
5
6
7
8
9
10
| void ssort(int *a, int n)
{
for(int i = 1; i < n; i++)
{
for(int j = 1; j < n; j++)
{
if(a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
}
|
3.桶排序
桶排序的步骤如下：
- 设置一定大小的数组作为空桶
- 遍历序列，将数字放进对应桶中
- 遍历桶，将非空桶放回原序列中
时间复杂度：$O(n)$
事实桶排序的应用要比这丰富的多。待补充。
4.快速排序
快速排序的步骤如下：
- 设置一个分界点 x
- 将原序列分成 ≤x 和 ≥x 两个序列
- 递归处理
时间复杂度：$O(nlogn)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void qsort(int *q, int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
qsort(q, l, j);
qsort(q, j+1, r);
}
|
要解释一下的是，中间对于序列划分的操作，实际上是建立了双指针：当 i 指针前进到一个大于 x ，且 j 指针前进到一个小于 x 的位置时，就将 i 指针和 j 指针对换。这样就保证了其满足过程二中的性质。
值得一提的是，这种写法要比某谷上随机化+去重后的代码跑的还快，而且并未使用新的空间，可以说是一种非常优秀的写法。
5.归并排序
归并排序的步骤如下：
- 设置中点 x，将原序列均分成前后两个序列
- 对前后两个序列分别递归，排序
- 将两个序列合并（想想两副洗好的扑克牌）
时间复杂度：$O(nlogn)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void msort(int *q, int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
msort(q, l, mid), msort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}
|
6.堆排序
用堆来存储序列，每次将堆顶元素（最小值）拿出，然后维护。
时间复杂度：$O(nlogn)$
代码参考数据结构堆即可。