计数排序-java

时间:2022-02-18 22:21:49

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

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

n为107 ,没有重复的整数

输出:按升序排列

思路:假设有一组集合 {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:      } 
       在满足一定的需求上,这种排序算法还是很高效,有效的,甚至不仅排序,去除重复项什么的也是不错的选择,算法算法,能捉老鼠的都是好猫。很多时候给你点提示解决问题就变的理所当然了,但却不能第一时间想到,这是需要提高的地方。
       续:昨晚就想把重复的也给排出来,早上发现这个和计数排序就是一个模样
   1:  public static void main(String[] args) {
   2:          long start = System.currentTimeMillis();
   3:          int max=100000001;
   4:          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};
   5:          char[] ch_sort = new char[max];
   6:          for(int i=0;i<max;i++){
   7:              char ch='0';
   8:              ch_sort[i]=ch;
   9:          }
  10:   
  11:          for (int i=0;i<b_sort.length;i++){
  12:              ch_sort[b_sort[i]]+=1;
  13:          }
  14:   
  15:          for(int i=0;i<max;i++){
  16:              
  17:              if(ch_sort[i] != '0'){
  18:                  int a=0;
  19:                  a=(int)ch_sort[i]-48;
  20:                  for (int j=0;j<a;j++){
  21:                  System.out.print(i+"  ");
  22:                      }
  23:              }
  24:          }
  25:          
  26:          long end = System.currentTimeMillis();
  27:          System.out.println("运行时间:" + (end - start) + "毫秒");
  28:      }

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