计数排序
2023-02-18 16:34:56 时间
计数排序
有这样一道排序题:数组里有20个随机数,取值范围为从0到10,要求用最快的速度把这20个整数从小到大进行排序。
这种排序算法不是基于元素比较,而是利用数组下标来确定元素的正确位置。
在刚才的题目里,随即整数的取值范围是从0到10,那么这些整数的值肯定是在0到10这11个数里面。于是我们可以建立一个长度为11的数组,数组下标从0到10,元素初始值全为0,如下所示:
先假设20个随机整数的值是:9, 3, 5, 4, 9, 1, 2, 7, 8,1,3, 6, 5, 3, 4, 0, 10, 9, 7, 9
让我们先遍历这个无序的随机数组,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。
比如第一个整数是9,那么数组下标为9的元素加1:
第二个整数是3,那么数组下标为3的元素加1:
继续遍历数列并修改数组......
最终,数列遍历完毕时,数组的状态如下:
数组中的每一个值,代表了数列中对应整数的出现次数。
有了这个统计结果,排序就很简单了,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
、
public static int[] countSort(int[] array) {
//1.得到数列的最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
}
//2.根据数列的最大值确定统计数组的长度
int[] coutArray = new int[max + 1];
//3.遍历数列,填充统计数组
for(int i = 0; i < array.length; i++)
coutArray[array[i]]++;
//4.遍历统计数组,输出结果
int index = 0;
int[] sortedArray = new int[array.length];
for (int i = 0; i < coutArray.length; i++) {
for (int j = 0; j < coutArray[i]; j++) {
sortedArray[index++] = i;
}
}
return sortedArray;
}
相关文章
- C#开发微信公众平台-就这么简单(附Demo)
- 程序员的人性思考(续)
- 恋爱虽易,相处不易:当EntityFramework爱上AutoMapper
- 魅力 .NET:从 Mono、.NET Core 说起
- 分享我对 ASP.NET vNext 的一些感受,也许多年回过头看 So Easy!
- 我的“第一次”,就这样没了:DDD(领域驱动设计)理论结合实践
- 程序员的人性思考(下)
- 2015-写给明年现在的自己
- POCO Controller 你这么厉害,ASP.NET vNext 知道吗?
- Unity依赖注入使用详解
- 初试JqueryEasyUI(附Demo)
- ASP.NET WebApi OWIN 实现 OAuth 2.0
- 程序员的人性思考(上)
- Visual Studio 2015 开发 ASP.NET 5 有何变化?
- 拨开迷雾,找回自我:DDD 应对具体业务场景,Domain Model 到底如何设计?
- Repository 返回 IQueryable?还是 IEnumerable?
- 一缕阳光:DDD(领域驱动设计)应对具体业务场景,如何聚焦 Domain Model(领域模型)?
- 让 ASP.NET vNext 在 Mac OS 中飞呀飞。。。
- 小菜学习设计模式(五)—控制反转(Ioc)
- 掀起你的盖头来:Unit Of Work-工作单元