模板 – 基数排序
基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数,可以在的线性时间内完成排序,其中为每个关键字的值域大小。
以下代码将对int
范围内的整数,以前位和后位为关键字进行排序。可以发现,在数据个数,其表现不如基于比较的快速排序算法。因此,在值域很大而数据较少时,应合理调整策略。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
const int N = 1e6 + 10; int a[N], ta[65540], tmp[N]; inline void radix_sort (int a[], int l, int r) { memset (ta, 0, sizeof ta); for (int i = l; i <= r; ++i) ++ta[a[i] & 0xffff]; for (int i = 1; i <= 0xffff; ++i) ta[i] += ta[i - 1]; for (int i = l; i <= r; ++i) tmp[l + --ta[a[i] & 0xffff]] = a[i]; memset (ta, 0, sizeof ta); for (int i = l; i <= r; ++i) ++ta[tmp[i] >> 16]; for (int i = 1; i <= 0xffff; ++i) ta[i] += ta[i - 1]; for (int i = r; i >= l; --i) a[l + --ta[tmp[i] >> 16]] = tmp[i]; }