首页 > 代码库 > 算法笔记_129:计数排序(Java)
算法笔记_129:计数排序(Java)
目录
1 问题描述
2 解决方案
2.1比较计数排序
2.2 分布计数排序
1 问题描述
给定一组数据,请使用计数排序,得到这组数据从小到大的排序序列。
2 解决方案
2.1比较计数排序
下面算法的时间复杂度为O(n^2),空间复杂度为O(n)。此方法对于任意一组数据均可排序。
具体代码如下:
package com.liuzhen.practice; public class Main { public void comparisonCountingSort(int[] A) { int[] temp = new int[A.length]; int[] count = new int[A.length]; for(int i = 0;i < A.length - 1;i++) { for(int j = i + 1;j < A.length;j++) { if(A[i] < A[j]) count[j]++; else count[i]++; } } for(int i = 0;i < A.length;i++) temp[count[i]] = A[i]; for(int i = 0;i < A.length;i++) A[i] = temp[i]; return; } public static void main(String[] args) { Main test = new Main(); int[] A = {2,3,1,4,6,4,3,5,3,2,5,3,5,2,3,4,5,2,54,3,21}; test.comparisonCountingSort(A); for(int i = 0;i < A.length;i++) System.out.print(A[i]+" "); } }
运行结果:
1 2 2 2 2 3 3 3 3 3 3 4 4 4 5 5 5 5 6 21 54
2.2 分布计数排序
下面算法的时间复杂度为O(n),空间复杂度为O(n)。该方法的时间效率要优于快速排序和合并排序,但是此方法对于给定数据有一定的要求,即数组中元素满足min <= A[i] <= max,且在min ~ max之间的所有元素在数组A中均有出现。
具体代码如下:
package com.liuzhen.practice; public class Main1 { //数组A中所有均大于等于min,小于等于max,并且min~max之间的所有元素在数组A中均出现 public void distributionCountingSort(int[] A, int min, int max) { int[] temp = new int[A.length]; int[] D = new int[max - min + 1]; for(int i = 0;i < A.length;i++) D[A[i] - min]++; for(int i = 0;i < max - min;i++) D[i + 1] = D[i + 1] + D[i]; for(int i = 0;i < A.length;i++) { int j = A[i] - min; temp[D[j] - 1] = A[i]; D[j]--; } for(int i = 0;i < A.length;i++) A[i] = temp[i]; return; } public static void main(String[] args) { Main1 test = new Main1(); int[] A = {1,2,3,4,5,6,7,8,9,2,4,5,4,3,4,5,2,3,4,5,2,3,5,4,2,3,5,4,3,2,5,3,3,5}; test.distributionCountingSort(A, 1, 9); for(int i = 0;i < A.length;i++) System.out.print(A[i]+" "); } }
运行结果:
1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 7 8 9
参考资料:
1.《算法设计与分析基础》 第3版 Anany Levitin 著 潘彦 译
算法笔记_129:计数排序(Java)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。