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=newint[]{4,3,6,3,5,1};
辅助计数数组int[]help=newint[max-min+1];//该数组大小为待排序数组中的最大值减最小值+1
输出数组int[]res=newint[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]
publicstaticint[]countSort1(int[]arr){
if(arr==null||arr.length==0){
returnnull;
}
intmax=Integer.MIN_VALUE;
intmin=Integer.MAX_VALUE;
//找出数组中的最大最小值
for(inti=0;i<arr.length;i++){
max=Math.max(max,arr[i]);
min=Math.min(min,arr[i]);
}
inthelp[]=newint[max];
//找出每个数字出现的次数
for(inti=0;i<arr.length;i++){
intmapPos=arr[i]-min;
help[mapPos]++;
}
intindex=0;
for(inti=0;i<help.length;i++){
while(help[i]-->0){
arr[index++]=i+min;
}
}
returnarr;
}
算法流程（2）
需要三个数组:
待排序数组int[]arr=newint[]{4,3,6,3,5,1};
辅助计数数组int[]help=newint[max-min+1];//该数组大小为待排序数组中的最大值减最小值+1
输出数组int[]res=newint[arr.length];
1.求出待排序数组的最大值max=6，最小值min=1
2.实例化辅助计数数组help，help用来记录每个元素之前出现的元素个数
3.计算arr每个数字应该在排序后数组中应该处于的位置，此时help=[1,1,4,5,6,7];
4.根据help数组求得排序后的数组，此时res=[1,3,3,4,5,6]
publicstaticint[]countSort2(int[]arr){
intmax=Integer.MIN_VALUE;
intmin=Integer.MAX_VALUE;
//找出数组中的最大最小值
for(inti=0;i<arr.length;i++){
max=Math.max(max,arr[i]);
min=Math.min(min,arr[i]);
}
int[]help=newint[max-min+1];
//找出每个数字出现的次数
for(inti=0;i<arr.length;i++){
intmapPos=arr[i]-min;
help[mapPos]++;
}
//计算每个数字应该在排序后数组中应该处于的位置
for(inti=1;i<help.length;i++){
help[i]=help[i-1]+help[i];
}
//根据help数组进行排序
intres[]=newint[arr.length];
for(inti=0;i<arr.length;i++){
intpost=--help[arr[i]-min];
res[post]=arr[i];
}
returnres;
}
桶排序
网络流传桶排序算法勘误
网络各博文中流程的桶排序算法实际上都是计数排序，并非标准的桶排序。有问题的文章：
经典排序算法-桶排序Bucketsort
桶排序算法
排序算法之桶排序
最快最简单的排序算法：桶排序
桶排序适用数据范围
桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000],这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
过程分析
桶排序的基本思想是：把数组arr划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值max、最小值min
2.我们使用动态数组ArrayList作为桶，桶里放的元素也用ArrayList存储。桶的数量为(max-min)/arr.length+1
3.遍历数组arr，计算每个元素arr[i]放的桶
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组
publicstaticvoidbucketSort(int[]arr){
intmax=Integer.MIN_VALUE;
intmin=Integer.MAX_VALUE;
for(inti=0;i<arr.length;i++){
max=Math.max(max,arr[i]);
min=Math.min(min,arr[i]);
}
//桶数
intbucketNum=(max-min)/arr.length+1;
ArrayList<ArrayList<Integer>>bucketArr=newArrayList<>(bucketNum);
for(inti=0;i<bucketNum;i++){
bucketArr.add(newArrayList<Integer>());
}
//将每个元素放入桶
for(inti=0;i<arr.length;i++){
intnum=(arr[i]-min)/(arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(inti=0;i<bucketArr.size();i++){
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！