更新：
删去了其他比较trivial的排序，留下了算法竞赛中用的略微多的排序思维。
删掉了useless的排序方法（希尔等等）。
修正了代码语言，Java语言由于当时第一版所写的错误过多，因而删除，再加上在运行速度上不及C++。
1.快速排序
是一种基于分治的排序方法。
思路
对需要排序的区间[l,r]进行下面的操作：
(1) 如果区间长度小于等于1直接退出，否则在区间中选择一个数字x作为比较元素。
(2) 将大于x的数字放右边，小于x的数字放左边，等于x的可左可右，将x放在两组数字中间。
**(3)**此时x的位置确认，对其左右两边的区间分别进行递归即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void quicksort(int l,int r) {
if(l >= r) return;
std::swap(a[l], a[l + rand() % (r - l + 1)]);
int x = a[l];
int i = l,j = r;
while(i < j) {
while(i < j && a[i] > x) {
j--;
if(i < j) {
a[i++] = a[j];
}
}
while(i < j && a[i] < x) {
i++;
if(i < j) {
a[j--] = a[i];
}
}
}
a[i] = x;
quicksort(l, i - 1);
quicksort(i + 1, r);
}
|
2.归并排序
是一种基于分治的排序方法。
思路
对需要排序的区间[l,r]进行下面的操作：
(1) 如果区间长度小于等于1直接退出，否则将区间分为[l,m],[m + 1,r]两个部分，其中 m = (l + r) / 2。
(2) 递归对两个子区间进行归并排序。
(3) 将两个已经排好序的子区间进行合并。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void mergesort(int l,int r) {
if(l == r) return;
int m = (l + r) / 2;
mergesort(l,m);
mergesort(m + 1, r);
int p1 = l, p2 = m + 1,tot = 0;
while(p1 <= m && p2 <= r) {
if(a[p1] <= a[p2])
c[++tot] = a[p1++];
else
c[++tot] = a[p2++];
}
while(p1 <= m)
c[++tot] = a[p1++];
while(p2 <= r)
c[++tot] = a[p2++];
for(int i=1;i <= tot; i++) {
a[i + l - 1] = c[i];
}
}
|
3.计数排序
思路
计数排序适合于值域范围校的数字排序
(1) 统计每个数字出现了几次。
(2) 统计完每个元素的出现次数后，求一边前缀和，我们就知道了每个数字在排完序后的序列中出现位置的范围。
(3) 把数字填入对应的位置即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #define endl "\n"
int n, m, a[N + 1], c[M + 1], r[N + 1];
inline void countingsort() {
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) {
++c[a[i]];
}
for(int i=1;i<=m;i++)
for(int j=1;j<=c[i];j++)
std::cout << i << " ";
std::cout << endl;
for(int i=2;i<=m;i++) {
c[i] += c[i - 1];
}
for(int i=n; i; --i) {
r[i] = c[a[i]]--;
}
for(int i=1;i<=n;i++) {
std::cout << r[i] << " ";
}
std::cout << endl;
}
|
4.基数排序
思路
将每个待排序的元素拆分成m个关键字，然后从后往前依次对这m个关键字进行排序。
特别的
（基数排序经常被用于进行字符串的排序，比如说后缀数组的核心就是基数排序）。
(1) 我们只要把数字按第 i 个及以后的关键字从小到大的顺序放到数组里，再做一次计数排序就好。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int n, m, a[N + 1], sa[N + 1], v[N + 1], r[N + 1], c[10];
inline void countingsort() {
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
++c[v[i]];
for(int i=1;i<=9;i++)
c[i] += c[i - 1];
for(int i=n;i;--i)
r[sa[i]] = c[v[sa[i]]]--;
for(int i=1;i<=n;i++)
sa[r[i]] = i;
}
inline void radixsort() {
for(int i=1;i<=n;i++)
sa[i] = i;
int x = i;
for(int i=1;i<=m;i++,x *= 10) {
for(int j=i;j<=n;j++)
v[j] = a[j] / x % 10;
countingsort();
}
}
|