Go语言视频零基础入门到精通

javalearner

以往的排序算法中，各个元素的位置基于元素直接的比较，这类排序称为比较排序。任意一个比较排序算法在最坏情况下，都需要做Ω(nlgn)次的比较。   而计数排序是基于非排序的思想的，计数排序假设n个输入元素中的每一个都是介于0到k之间的整数。   计数排序的思想是对每一个输入元素x，确定出小于x的元素个数，有了这一信息，就可以把x直接放在它在最终输出数组的位置上，例如，如果有17个元素小于x，则x就是属于第18个输出位置。当几个元素相同时，方案要略作修改。 计数排序是稳定的。 参考资料《算法导论第二版》8.2节计数排序。   以下为参考代码，输入数组为随机生成的，每个输入元素取值范围为[0,k)。
  
   
   

     
   

     
   
  

1. public class Counting_sort {
   
2.   public static void main(String[] args) {
   
3.    int[] input = new int[10];
   
4.    int k = 5;// 输入元素都是介于0到k之间
   
5.    // 随机生成输入数组，所有元素都介于0到k之间
   
6.    for (int i = 0; i < input.length; i++) {
   
7.     input[i] = (int) (Math.random() * k);// 数字范围[0,k)
   
8.    }
   
9.    System.out.print("输入数组");
   
10.    for (int i = 0; i < input.length; i++) {
    
11.      System.out.print(input[i] + " ");
    
12.    }
    
13.    int[] output = new int[input.length];
    
14.    countsort(input, output, k);
    
15.    System.out.print("输出数组");
    
16.    for (int i = 0; i < output.length; i++) {
    
17.      System.out.print(output[i] + " ");
    
18.    }
    
19.   }
    
20.   public static void countsort(int[] input, int[] output, int k) {
    
21.     // input为输入数组，output为输出数组，k表示有所输入数字都介于0到k之间
    
22.     int[] c = new int[k];// 临时存储区
    
23.     int len = c.length;
    
24.     // 初始化
    
25.     for (int i = 0; i < len; i++) {
    
26.       c[i] = 0;
    
27.     }
    
28.     // 检查每个输入元素，如果一个输入元素的值为input[i],那么c[input[i]]的值加1，
    
29.    //此操作完成后，c[i]中存放了值为i的元素的个数
    
30.     for (int i = 0; i < input.length; i++) {
    
31.       c[input[i]]++;
    
32.     }
    
33.    
    
34.    // 通过在c中记录计数和，c[i]中存放的是小于等于i元素的数字个数
    
35.     for (int i = 1; i < len; i++) {
    
36.       c[i] = c[i] + c[i - 1];
    
37.     }
    
38.        
    
39.     // 把输入数组中的元素放在输出数组中对应的位置上
    
40.     for (int i = input.length - 1; i >= 0; i--) {// 从后往前遍历
    
41.       output[c[input[i]] - 1] = input[i];
    
42.       c[input[i]]--;// 该操作使得下一个值为input[i]的元素直接进入输出数组中input[i]的前一个位置
    
43.     }
    
44.   }
    
45. }
    

复制代码

运行结果：
C:java>java Counting_sort
输入数组4 4 4 0 3 1 1 1 4 3 输出数组0 1 1 1 3 3 4 4 4 4
C:java>java Counting_sort
输入数组2 0 0 4 2 1 2 4 3 4 输出数组0 0 1 2 2 2 3 4 4 4
C:java>java Counting_sort
输入数组4 2 3 1 0 4 0 1 0 3 输出数组0 0 0 1 1 2 3 3 4 4
C:java>java Counting_sort
输入数组1 3 4 1 4 2 2 3 4 4 输出数组1 1 2 2 3 3 4 4 4 4
C:java>java Counting_sort
输入数组0 0 1 2 0 1 3 0 4 2 输出数组0 0 0 0 1 1 2 2 3 4
C:java>java Counting_sort
输入数组3 2 2 4 1 0 1 0 1 1 输出数组0 0 1 1 1 1 2 2 3 4
C:java>java Counting_sort
输入数组1 1 4 2 3 3 2 0 2 1 输出数组0 1 1 1 2 2 2 3 3 4
C:java>java Counting_sort
输入数组1 2 0 1 0 1 1 2 3 4 输出数组0 0 1 1 1 1 2 2 3 4
C:java>java Counting_sort
输入数组1 4 3 1 1 3 2 0 4 4 输出数组0 1 1 1 2 3 3 4 4 4



  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/15/000002562.zip