3.3.6 - Counting Sort

1. 演算法

1. 計算每種資料(鍵值)的出現次數，並紀錄在陣列Count[]中

2. 計算每種資料(鍵值)在Count[]的起始位置，並記錄在Start[]中

3. 依Start[]照將排序結果輸出

    int max = 0;
    int n = strlen(arr);
    // 尋找最大值
    for (int i = 0;i<n;i++)
        if (arr[i]>max) 
            max = arr[i];
            
    // counting計算出現次數
    char count[max];
    char start[max];
    for (int i = 0; i<n; i++)
        count[i] = 0;
    for (int i = 0; i<n; i++)
        count[arr[i]-1]++; //為了配合陣列的index
        
    // 記錄起始位置
    start[0]=1;
    for (int i = 1; i<max; i++)
        start[i] = start[i-1]+count[i-1];
        
    char output[n];
    for (int i = 0; i<n; i++){
        output[start[arr[i]-1]-1] = arr[i];
        start[arr[i]-1]++;
    }

2. 性質

• Time Complexity: $O(n+k)$

  $O(k)+O(n)+O(k)+O(n)$
• Space Complexity: $O(n+k)$

Counting sorting is a unstable sorting method.