模板 – 基数排序

基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数,可以在O(kn+i=1kwi)\mathrm{O}(kn + \sum\limits_{i=1}^{k}w_i)的线性时间内完成排序,其中wiw_i为每个关键字的值域大小。

以下代码将对int范围内的整数,以前1616位和后1616位为关键字进行排序。可以发现,在数据个数n7×104n \leq 7\times 10^4,其表现不如基于比较的快速排序算法。因此,在值域很大而数据较少时,应合理调整策略。

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 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]; }
  • 2021年12月8日