Monday, July 21, 2014

Counting sort

Question:
A sort algorithm in O(n+k), not comparing value method.
Space: O(n+k).
Answer:
//针对c数组的大小,优化过的计数排序
public class CountSort{
 public static void main(String []args){
  //排序的数组
  int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
  int b[] = countSort(a);
  for(int i : b){
   System.out.print(i + "  ");
  }
  System.out.println();
 }
 public static int[] countSort(int []a){
  int b[] = new int[a.length];
  int max = a[0], min = a[0];
  for(int i : a){
   if(i > max){
    max = i;
   }
   if(i < min){
    min = i;
   }
  }
  //这里k的大小是要排序的数组中,元素大小的极值差+1
  int k = max - min + 1;
  int c[] = new int[k];
  for(int i = 0; i < a.length; ++i){
   c[a[i]-min] += 1;//优化过的地方,减小了数组c的大小
  }   //c[a[i]-min]== count.for position.
  for(int i = 1; i < c.length; ++i){
   c[i] = c[i] + c[i-1];
  }    //accumulated pos.
  for(int i = a.length-1; i >= 0; --i){
   b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
  }
  return b;
 }
}

No comments:

Post a Comment