排序算法计数排序

计数排序

  计数排序的可以在线性时间O(n)内完成对长度为n的数组进行排序，但是，该算法的缺陷主要有两点，一是通过牺牲了空间来换取时间的高效，二是，对数组元素的范围有要求，不能过大。

  代码如下:

//A[1...n] in the range of (0...k)
void CountingSort(int *A, int *B, int k, int n){
  int *C = new int[k];
  memset(C, 0, sizeof(C)*sizeof(int));
  for(int i = 0; i <= n-1; i++){
    C[A[i]] = C[A[i]] + 1;
  }
  for(int i = 1; i < k; i++){
    C[i] = C[i] + C[i - 1];
  }
  for(int i = n - 1; i >= 0; i--){
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }

  return ;
}

   代码中，A的待排序数组，B是函数输出的排好序的数组，k是数组元素的范围，即数组中最大元素不能超过k，n的待排序数组的长度