计数排序-java

     今天看了一本书，书里有道题，题目很常见，排序，明了点说：

     需求：输入：最多有n个正整数，每个数都小于n，

n为10⁷ ,没有重复的整数

             输出：按升序排列

     思路：假设有一组集合 {1,3,5,6,11,12}，我们可以用字符串来表示这组集合，0 1 0 1 0 1 1 0 0 0 0 1 1 代表集合中的数值的位为1，其他的都为0.

     伪代码：

//  将一个字符数组全部置为0，大小为给的数据中的最大值
 for i = (0,n)
      ch[i] = 0;
 for each i in the int[]
      ch[i] = 1;
 for i = (0,n)
        if ch[i] == 1 then
           print();

       实现代码:

   1:      public static void main(String[] args) {

   2:          long start = System.currentTimeMillis();

   3:          int max=100000001; //因为要在第100000000位上置1，所以max>100000000

   4:          int b_sort[]={12,1,5,4,8,11,10,22,33,44,11,100000000,3,4432,32425,423423,1241,41241,4234121,421414,124144,12341414,34,242};

   5:          //初始化Char[],全部置为0

   6:          char[] ch_sort = new char[max];

   7:          for(int i=0;i<max;i++){

   8:              char ch='0';

   9:              ch_sort[i]=ch;

  10:          }

  11:          //在相应的位置上置1

  12:          for (int i=0;i<b_sort.length;i++){

  13:              ch_sort[b_sort[i]]='1';

  14:          }

  15:          //输出Index，同时排序结束

  16:          for(int i=0;i<max;i++){

  17:              if (ch_sort[i] == '1'){

  18:                  System.out.println(i+"  ");

  19:              }

  20:          }

  21:          //运行时间    

  22:          long end = System.currentTimeMillis();

  23:          System.out.println("运行时间：" + (end - start) + "毫秒");

  24:      } 

       在满足一定的需求上，这种排序算法还是很高效，有效的，甚至不仅排序，去除重复项什么的也是不错的选择，算法算法，能捉老鼠的都是好猫。很多时候给你点提示解决问题就变的理所当然了，但却不能第一时间想到，这是需要提高的地方。

       续：昨晚就想把重复的也给排出来，早上发现这个和计数排序就是一个模样

public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int max=100000001;
        int b_sort[]={12,1,1,1,1,1,1,1,1,1,1,1,1,1,1,5,4,4,8,11,8,10,22,1,33,44,33,11,100000000,3,4432,32425,423423,1241,41241,4234121,421414,124144,12341414,34,242};
        char[] ch_sort = new char[max];
        for(int i=0;i<max;i++){
            char ch='0';
            ch_sort[i]=ch;
        }

        for (int i=0;i<b_sort.length;i++){
            ch_sort[b_sort[i]]+=1;
        }

        for(int i=0;i<max;i++){

            if(ch_sort[i] != '0'){
                int a=0;
                a=(int)ch_sort[i]-48;
                for (int j=0;j<a;j++){
                System.out.print(i+"  ");
                    }
            }
        }

        long end = System.currentTimeMillis();
        System.out.println("运行时间：" + (end - start) + "毫秒");
    }

      既然能置1，当然也能置2置3，但是如果重复项超出ascii码怎么办？