首页 > 代码库 > 计数排序
计数排序
算法导论：
- 任意一个比较排序算法，在最坏的情况下，至少要做n*lg(n)次的比较，因此堆排序与归并排序是渐近最优的比较排序算法
- 但计数排序、基数排序和桶排序都不采用比较的方式来确定元素的顺序，因此下界n*lg(n)对它们并不适用
计数排序假设被排序的元素都在范围[0, k]中，k为正整数，当k=O(n)的时候，计数排序的运行时间为O(n)，计数排序是稳定的
代码：
1 package sorts; 2 3 import java.util.Arrays; 4 import java.util.Random; 5 6 public class CountingSort { 7 /** 8 * @param a the target array 9 * @param b the array to store the result of the sort10 * @param k in the target array, each element is in the range [0, k]11 * */12 public static void sort(int[] a, int[] b, int k) {13 int[] c = new int[k+1]; // counting array14 for (int i = 0; i < k; i++) {15 c[i] = 0;16 }17 for (int i = 0; i < a.length; i++) {18 ++c[a[i]]; // c[x] is the number of elements in ‘a‘ equal to x.19 }20 for (int i = 1; i <= k; i++) {21 c[i] = c[i] + c[i-1]; // c[x] is the number of elements in ‘a‘ no more than x.22 }23 for (int i = a.length - 1; i >= 0; i--) {24 b[c[a[i]]-1] = a[i]; // convert to index, must subtract 125 --c[a[i]];26 }27 }28 29 // test30 public static void main(String[] args) {31 Random random = new Random();32 int num = 10;33 int bound = 100;34 int[] a = new int[num];35 int[] b = new int[num];36 for (int i = 0; i < num; i++) {37 a[i] = random.nextInt(bound);38 }39 CountingSort.sort(a, b, bound-1);40 System.out.println(Arrays.toString(b));41 }42 }
计数排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。