計數排序（線性時間排序）--[算法導]

之前的排序都是通過比較得到的，即比較排序：在排序的最終結果中，各元素的次序依賴與它們之間的比較。而時間復雜度最好的也是O(nlgn)，接下來說一個未經比較的排序，而復雜度則是線性的。

計數排序:假設n個輸入元素的每一個都是在0-k區間內的一個整數，其中k為某個整數。當k = O(n)時，排序的運行時間為O(n)。

計數排序的基本思想是：對每一個輸入元素x，確定小於x的元素個數。利用這一信息，就可以直接把x放到它在輸出數組中的位置上了。例如，如果有17個元素小於x，則將x放在第18個位置即可。但是當存在幾個元素相同時，會稍許不同，否則中間會漏掉元素。

在計數排序算法中，假設輸入是一個數組A[1..n]，A.length = n。另外數組B[1...n]存放排序的輸出，C[0...k]提供臨時的存儲空間：

第1-2行，C數組賦值為0；

第3-4行，記錄各個元素的個數，下圖中a圖；

第6-7行，對數組C操作，C[i] = C[i] + C[i- 1];見下圖中b圖

第9-11行，排序...下圖中c，d，e圖是執行9-11代碼一次、二次、三次的結果，f是結果；

代碼：

#include 
#include 

using namespace std;

/*int Max(int A[], int length)
{
    int max = A[0];
    for(int i = 1; i < length; i++)
    {
        if(max < A[i])
            max = A[i];
    }

    return max;
}*/

int CountSort(int A[], int* B, int k, int length)
{
    int *C = new int[k];
    memset(C, 0, sizeof(int) * (k));

    for (int j = 0; j < length; j++)  //輔助C
    {
        C[A[j]] += 1;
    }

    for (int i = 1; i < k; i++)  //
    {
        C[i]= C[i]+C[i-1];
    }

    for (int j = length - 1; j >= 0; j--)
    {
        B[C[A[j]] - 1] = A[j];
        C[A[j]] = C[A[j]] - 1;  //若是出現同樣的數往前放
    }
    delete[] C;

    return 0;
}

int main()
{
    int A[] = {2, 5, 3, 0, 2, 3, 0, 3};
    //int A[] = {2, 9, 7, 1, 3, 5, 11, 4, 12, 35};

    int length = sizeof(A) / sizeof(int); //
    int* B = new int[length];

    int k = 10001;  //保證排序數據在0-k中
    //k = Max(A, length) + 1;  //k = max + 1;後面方便操作

    CountSort(A, B, k, length);  //計數排序

    for(int i = 0; i < length; i++)
        cout<