java 实现计数排序和桶排序实例代码

时间:2021-05-19

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;}

算法流程(2)

需要三个数组:

待排序数组 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用来记录每个元素之前出现的元素个数

3.计算 arr 每个数字应该在排序后数组中应该处于的位置,此时 help = [1,1,4,5,6,7];

4.根据 help 数组求得排序后的数组,此时 res = [1,3,3,4,5,6]

public static int[] countSort2(int[] arr){ 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 - min + 1]; //找出每个数字出现的次数 for(int i = 0; i < arr.length; i++){ int mapPos = arr[i] - min; help[mapPos]++; } //计算每个数字应该在排序后数组中应该处于的位置 for(int i = 1; i < help.length; i++){ help[i] = help[i-1] + help[i]; } //根据help数组进行排序 int res[] = new int[arr.length]; for(int i = 0; i < arr.length; i++){ int post = --help[arr[i] - min]; res[post] = arr[i]; } return res;}

桶排序

网络流传桶排序算法勘误

网络各博文中流程的桶排序算法实际上都是计数排序,并非标准的桶排序。有问题的文章:

经典排序算法 - 桶排序Bucket sort

桶排序算法

排序算法 之 桶排序

最快最简单的排序算法:桶排序
桶排序适用数据范围

桶排序可用于最大最小值相差较大的数据情况,比如[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.遍历桶数组,把排序好的元素放进输出数组

public static void bucketSort(int[] arr){ 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 bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } //将每个元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } System.out.println(bucketArr.toString()); }

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章