本文主要是介绍程序分享--排序算法--基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》《做好面试准备，迎接2024金三银四》。
推荐热榜内容：《架构实战--以海量存储系统讲解热门话题：分布式概念》
-------------------------------------正文----------------------------------------
基数排序：概述
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序：算法描述
1.取得数组中的最大数，并取得位数；
2.arr为原始数组，从最低位开始取每个位组成radix数组；
3.对radix进行计数排序（利用计数排序适用于小范围数的特点）；
#include <iostream>
#include <vector>
#include <queue>void radixSort(std::vector<int>& arr)
{int maxDigit = 0;// 找出数组中最大数的最大位数for (int i = 0; i < arr.size(); i++) {int temp = arr[i];while (temp) {temp /= 10;maxDigit = maxDigit > (i + 1) ? maxDigit : (i + 1);}}std::vector<std::queue<int>> buckets(10); // 建立10个桶for (int digit = 0; digit < maxDigit; digit++) {// 将数分配到桶中for (int i = 0; i < arr.size(); i++) {int digitVal = (arr[i] / (int)pow(10, digit)) % 10;buckets[digitVal].push(arr[i]);}// 再将桶中的数回收到原数组中int index = 0;for (int i = 0; i < buckets.size(); i++) {while (!buckets[i].empty()) {arr[index++] = buckets[i].front();buckets[i].pop();}}}
}int main() {std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);for (int num : arr) {std::cout << num << " ";}return 0;
}这篇关于程序分享--排序算法--基数排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
