算法導論學習筆記（一）排序算法之計數排序

基本思想

對于一個數x，确定小于x的元素個數。

即找到n個比x小的數，那麼x在數列中為第n+1小的數，則确定其排序位置。

算導上的僞代碼

COUNTING-SORT(A,B,k)
1   let C[0...k] be a new array
2   for i = 0 to k
3       C[i] = 0
4   for j = 1 to A.length
5       C[A[j]] = C[A[j]] + 1
6   //C[i] now contains the number of elements equal to i.
7   for i = 1 to k
8       C[i] = C[i] + C[i-1]
9   //C[i] now contains the number of elements less than or equal to i.
10  for j = A.length downto 1
11      B[C[A[j]]] = A[j]
12      C[A[j]] = C[A[j]] - 1
           

執行時間

第3行和第7行各執行k次，即O(k);

第5行和第11、12行各執行n次，即O(n);

總執行時間為O(n+k);

當k = O(n)時，執行時間為O(n)。

程式代碼

void countSort(int *sortArray,int n,int k,int *b)
{
    int c[k+10];
    for(int i=0;i<k;i++){
        c[i] = 0;
    }
    for(int i=0;i<n;i++){
        c[sortArray[i]]++;
    }
    for(int i=1;i<k;i++){
        c[i] += c[i-1];
    }
    for(int i=n-1;i>=0;i--){
        b[c[sortArray[i]]-1] = sortArray[i];
        c[sortArray[i]]--;
    }
}