如何利用java实现一个计数排序功能-创新互联
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
创新互联专业成都做网站、网站制作,集网站策划、网站设计、网站制作于一体,网站seo、网站优化、网站营销、软文推广等专业人才根据搜索规律编程设计,让网站在运行后,在搜索中有好的表现,专业设计制作为您带来效益的网站!让网站建设为您创造效益。本篇文章给大家分享的是有关如何利用java 实现一个计数排序功能,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。
java 实现计数排序和桶排序实例代码
目录
比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。
在 冒泡排序 之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在 归并排序、快速排序 之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均 O(nlogn) 。
比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度 O(n) 。
非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
计数排序
计数排序适用数据范围
计数排序需要占用大量空间,它仅适用于数据比较集中的情况。比如 [0~100],[10000~19999] 这样的数据。
过程分析
计数排序的基本思想是: 对每一个输入的元素arr[i],确定小于 arr[i] 的元素个数。
所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i],所以 arr[i] 应该放在数组的第6个位置上。
下面给出两种实现:
算法流程(1)
需要三个数组:
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的大值减最小值+1
输出数组 int[] res = new int[arr.length];
1.求出待排序数组的大值max=6, 最小值min=1
2.实例化辅助计数数组help,help数组中每个下标对应arr中的一个元素, help用来记录每个元素出现的次数
3.计算 arr 中每个元素在help中的位置 position = arr[i] - min,此时 help = [1,0,2,1,1,1]; (3出现了两次,2未出现)
4.根据 help 数组求得排序后的数组,此时 res = [1,3,3,4,5,6]
public static int[] countSort1(int[] arr){ if (arr == null || arr.length == 0) { return null; } int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; //找出数组中的大最小值 for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } int help[] = new int[max]; //找出每个数字出现的次数 for(int i = 0; i < arr.length; i++){ int mapPos = arr[i] - min; help[mapPos]++; } int index = 0; for(int i = 0; i < help.length; i++){ while(help[i]-- > 0){ arr[index++] = i+min; } } return arr; }
分享题目:如何利用java实现一个计数排序功能-创新互联
URL标题:http://myzitong.com/article/idsep.html