这里看看
基数排序 – 码到城攻基数排序
https://www.codecomeon.com/posts/20/
说基数排序，其实就是多次的桶排，不过，这里只需要十个桶，基数排序基于多关键字，拿一个数256来说，它被分为各位，十位，百位，每位都是一个关键字，而且关键字的范围都
是在0-9的范围内；
先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数，和百位数；
以下是一个待排序数列：278-》109-》063-》930-》589-》184-》505-》269-》008-》083-》
1.按个位关键字排序，如图：
最后一行就是按个位桶排的序列。
2.按十位关键字排序，（一定是在1排序的序列基础上再按十位排序，目的是：如果十位相同，由于个位排好序，所以再入桶的时候，还是有序的），如图：
结果：
3.百位排序：排序序列基于2中排好的序列；
最终排序结果就出来了，下面用代码说话：
/* *基数排序 */ #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); }赐教！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/229362.html原文链接：https://javaforall.net
