桶排序
将每个元素放入对应的桶当中，再按桶的顺序将元素输出。
1
2
rep(i, 1, n+1) bucket[a[i]]++;
rep(i, 1, MAX+1) rep(j, 1, bucket[i]+1) print("%d ", i);
缺点：受限于元素值域范围 $[1, MAX]$ 。
元素排名：
1
2
3
rep(i, 1, n+1) bucket[a[i]]++;
rep(i, 1, MAX+1) bucket[i] += bucket[i-1];
rep(i, 1, n+1) printf("%d ", bucket[a[i]]--); // 输出 a[i] 的排名
若当前有若干个 $a[i]$ 值都相同，则 $bucket[a[i]]$ 表示的就是目前最后一个 $a[i]$ 的排名
1
2
3
rep(i, 1, n+1) bucket[a[i]]++;
rep(i, 1, MAX+1) bucket[i] += bucket[i-1];
rep(i, 1, n+1) new_a[bucket[a[i]]--] = a[i];
$new_a[\ ]$ 即为排序后的数组。
注意：
对于具有相同元素值的元素，会将其按与循环相反的顺序，放入排序后的数组中。
（结合上述 “ $bucket[a[i]]$ 表示的就是目前最后一个 $a[i]$ 的排名 ” 理解）
因此，在用桶排序处理多关键字排序，遇到当前关键字相等时，
会将元素按照与循环遍历顺序相反的顺序，排列在当前关键字相等的区间内。
因此，此处涉及：
- 低优先级的关键字应先进行桶排序，这样在高优先级关键字排序时，遇到关键字相等的情况时，低优先级关键字已经是有序的了。
- 确定元素排名时，循环遍历元素的顺序会影响到当前关键字相等的区间内元素的顺序，即与循环遍历的顺序相反。
多关键字桶排序
设元素有两个关键字，
按第一关键字从小到大排序，第一关键字相等时按第二关键字从小到大排序，
当两个元素的第一关键字相等时，需要比较两个元素的第二关键字，
当两个元素的第二关键字相等时，则只需要任意排序。
因此，先将所有元素按照其第二关键字进行桶排序后，
获取在第二关键字下的排名 $id2[\ ]$
$id2[i]$ 表示，在第二关键字下，排在第 $i$ 位的元素下标是 $id2[i]$
此时，倒序遍历 $id2[\ ]$ ，即，按第二关键字从大到小的顺序，
（使得排序后，在第一关键字相同的情况下，第二关键字会是从小到大的顺序）
查找此时 $id2[i]$ 对应元素下标的元素 $a[id2[i]]$ ，
根据其第一关键字的值 $a[id2[i]].x$ ，
找到其在第一关键字排序下的排名 $bucket1[a[id2[i]].x]$ ，
则，排序后数组 $new_a[\ ]$ 在该排名位置下的元素值即为 $a[id2[i]]$ 。
1
2
3
4
5
6
rep(i, 1, n+1) bucket1[a[i].x]++;
rep(i, 1, n+1) bucket2[a[i].y]++;
rep(i, 1, MAX+1) bucket1[i] += bucket1[i-1];
rep(i, 1, MAX+1) bucket2[i] += bucket2[i-1];
per(i, 1, n+1) id2[bucket2[a[i].y]--] = i;
per(i, 1, n+1) new_a[bucket1[a[id2[i]].x]--] = a[id2[i]];
基数排序
将每一个数看作是一个多关键字的元素，每一位上的权值就是一个关键字，权值的优先级从高位到低位递减。
如 $123$ 可以看作是一个有 $3$ 个关键字的元素，其第一关键字是 $1$ ，第二关键字是 $2$ ，第三关键字是 $3$ 。
这样，基数排序就相当于是，将每个数看作一个多关键字元素的基于多关键字的桶排序。
优化：
上述例子是按以 $10$ 的幂次作基数分关键字，其实可以按 $2$ 的幂次作基数分关键字，通过位运算可获得更高的效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* ----- 基数排序 -----
< 使用 >
1. 调用 Radix_Sort(a, n)
.. a 为待排序数组首地址，
.. n 为数组元素个数
.. 调用后 a[] 已排好序
*/
int _b[N];
inline void Radix_Sort(int *a, int n) {
int t[4][0x100], *b = _b;
memset(t, 0, sizeof(t));
rep(i, 0, n) rep(j, 0, 4) ++t[j][(a[i] >> (j << 3)) & 0xff];
rep(i, 1, 0x100) rep(j, 0, 4) t[j][i] += t[j][i-1];
rep(j, 0, 4) {
per(i, 0, n) b[--t[j][(a[i] >> (j << 3)) & 0xff]] = a[i];
swap(a, b);
}
}
注意：
1
2
// 这里采用前置 -- 操作符的原因是让 b[] 的下标从 0 开始，与 a[] 匹配
per(i, 0, n) b[--t[j][(a[i] >> (j << 3)) & 0xff]] = a[i];
