基数排序 原创 排序算法 2021年7月16日 07:19 夏至未至 1118 当前内容 2295 字，在路上，马上到，马上到 说基数排序，其实就是多次的桶排，不过，这里只需要十个桶，基数排序基于多关键字，拿一个数256来说，它被分为各位，十位，百位，每位都是一个关键字，而且关键字的范围都 是在0-9的范围内； 先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数，和百位数； 以下是一个待排序数列：278-》109-》063-》930-》589-》184-》505-》269-》008-》083-》 1.按个位关键字排序，如图：  最后一行就是按个位桶排的序列。 2.按十位关键字排序，（一定是在1排序的序列基础上再按十位排序，目的是：如果十位相同，由于个位排好序，所以再入桶的时候，还是有序的），如图：  结果：  3.百位排序：排序序列基于2中排好的序列；  最终排序结果就出来了，下面用代码说话： ```cpp /* *基数排序 */ #pragma once #define MAXSIZE 1000 int getdigit(int x, int d) { int a[] = { 1, 1, 10, 100}; //最大三位数，所以这里只要百位就满足了。 return (x / a[d]) % 10; } //打印 void PrintArr(int ar[], int n) { for (int i = 0; i < n; ++i) { cout << ar[i] << " "; } cout << endl; } void lsdradix_sort(int arr[], int begin, int end, int d) { const int radix = 10; int count[radix], i, j; int *bucket = (int*)malloc((end - begin + 1)*sizeof(int)); //所有桶的空间开辟 //按照分配标准依次进行排序过程 for (int k = 1; k <= d; ++k) { //置空 for (i = 0; i < radix; i++) { count[i] = 0; } //统计各个桶中所盛数据个数 for (i = begin; i <= end; i++) { count[getdigit(arr[i], k)]++; } //count[i]表示第i个桶的右边界索引 for (i = 1; i < radix; i++) { count[i] = count[i] + count[i - 1]; } //把数据依次装入桶(注意装入时候的分配技巧) for (i = end; i >= begin; --i) //这里要从右向左扫描，保证排序稳定性 { j = getdigit(arr[i], k); //求出关键码的第k位的数字， 例如：576的第3位是5 bucket[count[j] - 1] = arr[i]; //放入对应的桶中，count[j]-1是第j个桶的右边界索引 --count[j]; //对应桶的装入数据索引减一 } //注意：此时count[i]为第i个桶左边界 //从各个桶中收集数据 for (i = begin, j = 0; i <= end; ++i, ++j) { arr[i] = bucket[j]; } } free(bucket); } void main() { int br[10] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83 }; cout << "原数据如下：" << endl; PrintArr(br, 10); lsdradix_sort(br, 0, 9, 3); //3位数 cout << "排序后数据如下：" << endl; PrintArr(br, 10); } ``` 本文标题： 基数排序 本文作者： 夏至未至 发布时间： 2021年7月16日 07:19 最近更新： 2021年7月28日 07:02 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 基数排序(1) 上一个 堆排序改进 下一个 选择排序 当前文章评论暂未开放,请移步至留言处留言。
