计数排序算法
2021/11/6 17:10:40
本文主要是介绍计数排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原理
针对于范围小数量大的数组,直接遍历一次对所有数进行计数,然后自己根据计数结果写数组
代码实现
void sort(int* arr, int n, int min, int max) //不稳定 { const int RAN = max - min + 1; int* arrRes = (int*)malloc(sizeof(int) * n); int* arrCount = (int*)malloc(sizeof(int) * RAN); //计数数组 for (int i = 0; i < RAN; i++) { arrCount[i] = 0; } for (int i = 0; i < n; i++) { arrCount[arr[i] - min]++; } for (int i = 0, j = 0; i < RAN; i++) { while (arrCount[i] > 0) { arrRes[j] = i + min; j++; arrCount[i]--; } } memcpy(arr, arrRes, sizeof(int) * n); free(arrRes); free(arrCount); }
优化思路
原来的方法是不稳定的,因为数组是我们自己写的,这次我们把计数数组优化成增量数组,记录每种数最后的排序,然后倒序遍历原数组找到所有位置
void sortP(int* arr, int n, int min, int max) //稳定 { const int RAN = max - min + 1; int* arrRes = (int*)malloc(sizeof(int) * n); int* arrCount = (int*)malloc(sizeof(int) * RAN); for (int i = 0; i < RAN; i++) { arrCount[i] = 0; } for (int i = 0; i < n; i++) { arrCount[arr[i] - min]++; } for (int i = 1; i < RAN; i++) //修改成增量数组,记录每种数字最后一个的排序位置 { arrCount[i] = arrCount[i - 1] + arrCount[i]; } for (int i = n - 1; i >= 0; i--) //倒序获取每个数字位置 { arrRes[arrCount[arr[i] - min] - 1] = arr[i]; arrCount[arr[i] - min]--; } 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日志系统资料入门教程