基数排序算法
2021/11/6 17:10:39
本文主要是介绍基数排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原理
把数字比较想象成每一位的多因素排序,只要保持每次排序的稳定即可,最高位权重最大最后排,这种是lsd类型,还有msd类型,通过分治递归来排序
代码实现
int getMaxBit(int* arr, int n) //找数组中最高的有几位 { int maxBit = 0; int max = arr[0]; int div = 1; for (int i = 1; i < n; i++) { if (max < arr[i]) { max = arr[i]; } } if (max / div == 0) { return 1; } int i = 1; while (max / div != 0) { maxBit++; div = pow(10, i); i++; } return maxBit; } void sort(int* arr, int n) //lsd 低位优先 { int* arrRes = (int*)malloc(sizeof(int) * n); int* arrCount = (int*)malloc(sizeof(int) * 10); //0-9 for (int i = 0; i < getMaxBit(arr, n); i++) //从低位开始排序 { int div = pow(10, i); for (int k = 0; k < 10; k++) { arrCount[k] = 0; } for (int j = 0; j < n; j++) //对每位进行计数 { arrCount[arr[j] / div % 10]++; } for (int k = 1; k < 10; k++) //增量数组 开始进行增量排序 { arrCount[k] = arrCount[k - 1] + arrCount[k]; } for (int k = n - 1; k >= 0; k--) { arrRes[arrCount[arr[k] / div % 10] - 1] = arr[k]; arrCount[arr[k] / div % 10]--; } memcpy(arr, arrRes, sizeof(int) * n); } free(arrRes); free(arrCount); }
评价
稳定,值范围远小于数组个数的时候效率高
这篇关于基数排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21订单系统资料入门教程:轻松管理你的订单
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java部署资料:新手入门教程
- 2024-09-21Java订单系统资料:新手入门教程与实战指南
- 2024-09-21Java管理系统资料入门教程
- 2024-09-21从零开始学习Java监控系统资料
- 2024-09-21Java就业项目资料:新手入门的必备教程
- 2024-09-21Java全端资料:初学者指南
- 2024-09-21Java全栈资料入门教程及资源汇总
- 2024-09-21Java日志系统资料入门教程