> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/3-search/sophisticated-sorting/3.3.6-counting-sort.md).

# 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)$$&#x20;

  $$O(k)+O(n)+O(k)+O(n)$$&#x20;
* Space Complexity: $$O(n+k)$$&#x20;

Counting sorting is a **unstable** sorting method.