Counting Sort | GeeksforGeeks

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

 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的大小
  }
  for(int i = 1; i < c.length; ++i){
   c[i] = c[i] + c[i-1];
  }
  for(int i = a.length-1; i >= 0; --i){
   b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
  }
  return b;
 }

http://rosettacode.org/wiki/Sorting_algorithms/Counting_sort#Java
public static void countingSort(int[] array, int min, int max){

 int[] count= new int[max - min + 1];
 for(int number : array){
  count[number - min]++;
 }
 int z= 0;
 for(int i= min;i <= max;i++){
  while(count[i - min] > 0){
   array[z]= i;
   z++;
   count[i - min]--;
  }
 }
}

void countSort(char *str)

{

    // The output character array that will have sorted str

    char output[strlen(str)];

    // Create a count array to store count of inidividul characters and

    // initialize count array as 0

    int count[RANGE + 1], i;

    memset(count, 0, sizeof(count));

    // Store count of each character

    for(i = 0; str[i]; ++i)

        ++count[str[i]];

    // Change count[i] so that count[i] now contains actual position of

    // this character in output array

    for (i = 1; i <= RANGE; ++i)

        count[i] += count[i-1];

    // Build the output character array

    for (i = 0; str[i]; ++i)

    {

        output[count[str[i]]-1] = str[i];

        --count[str[i]];

    }

    // Copy the output array to str, so that str now

    // contains sorted characters

    for (i = 0; str[i]; ++i)

        str[i] = output[i];

}

2. It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.
3. It is often used as a sub-routine to another sorting algorithm like radix sort.

Read full article from Counting Sort | GeeksforGeeks