个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》《C++》《Linux》《网络》 《redis学习笔记》
文章目录
- 基数排序的定义和基本原理
- 基本原理
- 具体步骤
- 基数排序的优缺点：
- 代码实现
- 总结
基数排序的定义和基本原理
基数排序(Radix Sort)是一种非比较型整数排序算法，其基本原理是根据数字的每一位来进行排序。具体来说，基数排序通过将整数按位数切割成不同的数字，然后按每一位数进行排序(不断接近有序的过程)，最终得到有序序列。
基本原理
- 按位排序：基数排序从最低有效位(Least Significant Digit, LSD) 或 最高位有效位(Most Significant Digit, MSD)开始，逐位进行排序。对于有d位的整数(排序整数的最长长度d)，需要进行d趟排序。
- 使用桶排序：在每一轮排序中，将待排序的数字分配到不同的桶中，每个桶代表一个特定的数字范围。然后，从桶中取出数字并从新组合，形成新的有序序列
- 重复排序：重复上述过程，直到所有位数都排序完成。
具体步骤
- 确定最大值：找出待排序数组中的最大值，以确定需要进行多少趟排序
- 分配和搜集：根据当前位数，将每一个数字分配到相应的桶中，然后从桶中收集数字
- 重新排序：重复上述过程，直到所有位数都排序完成
下面列子，采用LSD：从最低位开始排序，逐步向上进行
基数排序的优缺点：
优点：
- 时间复杂度低：基数排序的时间复杂度为O(nk)， 其中n是待排序元素的数量，k是最大数的位数。
- 稳定性：基数排序是稳定的排序算法，相同值的元素在排序后保持其原有的顺序。
- 适用于大规模数据：基数排序特别适合处理大规模整数排序，能够有效利用计算机的并行处理能力
缺点：
- 空间复杂度高：基数排序需要额外的空间来存储中间结果，空间复杂度为O(n + k)或O(n + r)，其中r是桶的数量
- 适用范围有限：基数排序主要用于整数排序，对于浮点数或字符串等其它类型的数据，需要进行额外的转换或处理
- 位数限制：当待排序元素位数较多时，基数排序的效率会下降，因为需要进行更多的轮次分类
代码实现
// 基数排序，核心思想是通过逐位排序实现整体有序
// 使用到queue，[0, 9]个queue来排列每一位
void RadixSort(vector<int>& arr) {
int size = arr.size();
if (size == 0)
return;
// 找到最大值，确认最大位数
int maxVal = arr[0];
for (int i = 1; i < size; ++i) {
if (maxVal < arr[i])
maxVal = arr[i];
}
int maxDigits = to_string(maxVal).length();
// 初始化10个队列
vector<queue<int>> buckets(10);
// 逐位排序
for (int i = 0; i < maxDigits; ++i) {
int divisor = pow(10, i);
// 分配元素到桶中
for (int j = 0; j < size; ++j) {
int index = arr[j] / divisor % 10; // 获取当前位数
buckets[index].push(arr[j]);
}
// 从桶中收集元素
int index = 0;
for (int j = 0; j < 10; ++j) {
while (!buckets[j].empty()) {
arr[index++] = buckets[j].front();
buckets[j].pop();
}
}
}
}
总结
以上就是我总结的C++面试题，TCP和UDP方面(1)
