【数据结构】基数排序的原理及实现

👦个人主页：Weraphael
✍🏻作者简介：目前正在准备26考研
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵，希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍

---

一、什么是基数排序

我们以往学习的排序算法，诸如快速排序、选择排序、冒泡排序等，主要是通过关键字之间的比较和移动数据这两种方法实现的。而基数排序是一种非比较的排序算法，其核心思想是将数值拆分为各个位上的数字，按照这些位上的数字的大小依次进行排序。

常见的排序策略有：

• 最高位优先(MSD,Most Significant Digit)：从数据的最高位开始排序，即先对最高位进行排序，然后依次处理低位。
• 最低位优先(LSD, Least Significant Digit)：从数据的最低位开始进行排序，即先对个位排序，然后对十位排序，接着对百位排序，依此类推。

大致的过程就是：可以想象用一个“桶”来存放不同位上的数字，如果排序的对象都是十进制数据。在每一位的排序过程中，将每一位的值放入对应的桶中，再将桶中的数据按顺序取出，进行下一轮排序，直至序列有序为止。值得一提的是，从桶中按顺序取数据的过程可以抽象成一个队列（先进先出）。因此，基数排序本质就是分发数据 + 回收数据的过程。

以上文字理解如果抽象的话，接下来我带大家画图理解。

二、基数排序的过程（图画）

假设有如下序列：[278, 109, 63, 930, 589, 184, 505, 269, 8, 83]。以最低位优先策略为例。

• 第一轮分发和回收

• 第二轮分发和回收

• 第三轮分发和回收
  

三、代码实现

#define MAX_DIGIT 3 // 序列的最大位数
#define RADIX 10 // 桶的个数
// 因为拍的是十进制数，所以桶的个数给10个就足够了// 数值第k次分发的位值
int GetKey(int value, int k)
{int res = 0;while (k >= 1){res = value % 10;value /= 10;k--;}return res;
}// 分发数据
void Distribute(int a[], int n, int time, queue<int> q[RADIX])
{for (int i = 0; i < n; i++) // 遍历数组{// 我们要知道当前数要放在哪个桶int key = GetKey(a[i], time);q[key].push(a[i]);}
}// 回收
void collect(int a[], queue<int> q[RADIX])
{int j = 0;for (int i = 0; i < RADIX; i++) // 遍历桶{while (q[i].size() != 0){a[j] = q[i].front();j++;q[i].pop();}}
}void radix_sort(int a[], int n)
{queue<int> q[RADIX]; // 用队列来模拟桶// 最多要 分配+回收 序列中的最大位数次for (int i = 1; i <= MAX_DIGIT; i++) {// 分发数据Distribute(a, n, i, q); // 传入i表示分发到第几位了// 回收数据collect(a, q);}
}

【测试结果】

四、基数排序的时空复杂度分析

时间复杂度：

• 对于分发操作：对每个元素，都需要计算当前位的键值，并将其放入对应的桶中。对于每一轮的排序，分配操作需要遍历所有的元素，因此时间复杂度是O(n)，其中n是元素的个数。

• 对于回收操作：每轮排序时，所有桶中的元素需要按顺序重新收集到数组中。对于每一轮的排序，收集操作也需要遍历所有的元素，因此时间复杂度是O(n)。

因此，基数排序的时间复杂度是 O(n * d)。其中，n是元素个数，d是数字的最大位数。

空间复杂度：

• 存储桶：每个桶是一个队列，最多存储n个元素。由于桶的数量是固定的（10个桶），因此桶所占用的空间是O(n)。

因此，基数排序的空间复杂度是O(n)。

五、基数排序的使用场景

基数排序通常不直接用于带有负数和浮点数的数据。这是因为在处理负数和浮点数时，基数排序的使用会比较复杂。而它的设计主要是针对非负整数的排序。它通常用于处理具有较为固定的数值长度，并且长度不能过大。长度过大就会导致基数排序的时间复杂度近似为O(n^2)

其应用场景包括但不限于：

1. 整数排序：当数据为整数时，尤其是在数字范围相对较小且数据量很大的情况下，基数排序表现尤为出色。例如：排序手机号码、身份证号码、邮政编码、学号等。
2. 字符串排序：基数排序也可以应用于字符串排序，尤其是当字符串的长度固定或者长度较短时。基数排序通过逐字符（ASCII码）排序来实现字符串排序，适用于字典序排列等场景。例如：排序带有前缀的字符串，如URL、文件名等。
3. 时间戳排序：基数排序也适用于需要根据时间戳排序的应用场景。时间戳通常是由年月日时分秒等组成，基数排序能够高效处理。
4. ...