首页 > 代码库 > 计数排序

计数排序

2024-07-21 19:24:25   219人阅读

算法导论：

  • 任意一个比较排序算法，在最坏的情况下，至少要做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 }

 

计数排序


联系
我们