南宁学java 5分钟了解计数排序

来源：南宁达内IT教育培训学校时间：2022/4/30 17:38:39

　　计数排序是一种非比较性质的排序算法，计数排序借助辅助空间记录每个元素出现的次数，根据次数确定每一个元素较终的位置。

　　计数排序思想介绍

　　1根据待排序数组，获取较大值和较小值，得到所有元素的范围 [m,n]

　　2新建一个长度为n-m+1的临时数组

　　3遍历待排序数组，元素的值-m作为临时数组下标，该下标位置记录元素出现次数

　　4遍历结束，临时数组就存储了每个元素出现的次数

　　5根据该临时数组，较终得到排序后元素

　　算法说明：

　　待排序数据：12，4，6，7，4，6

　　数据范围为[4,12],临时数组长度为12-4+1=9

　　较终得到排序后序列：4，4，6，6，7，12

　　计数排序的代码实现

　　1. public static void sortCount(int[] arr) {

　　2. int max = 0;

　　3. int min = 0;

　　4. // 获取数组的较大值和较小值

　　5. for(int i = 0; i < arr.length; i++){

　　6. max = Math.max(max, arr[i]);

　　7. min = Math.min(min, arr[i]);

　　8. }

　　9. int len = arr.length;

　　10. // 创建临时数组

　　11. int[] temp = new int[max - min + 1];

　　12. // 计数

　　13. for(int i = 0; i < len; i++) {

　　14. temp[arr[i] - min] += 1;

　　15. }

　　16. // 将临时数组中数据依次放回原数组

　　17. for(int i = 0, index = 0; i < temp.length; i++) {

　　18. int item = temp[i];

　　19. while(item-- != 0) {

　　20. arr[index++] = i + min;

　　21. }

　　22. }

　　23. }

　　总结

　　计数排序需要占用额外的存储空间，它比较适用于数据比较集中的情况。

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/1658/news/520456/违者必究！ 以上就是南宁达内IT教育培训学校 小编为您整理 南宁学java 5分钟了解计数排序的全部内容。