# 演算法 - Counting Sort

## 輸入格式

第一行：一個整數 N（1 ≤ N < 20000），表示陣列中的元素個數  
第二行：N 個以空格分隔的整數

---

## 輸出格式

排序後的 N 個整數，以空格分隔

---

## 演算法設計思路
遇到這類問題，我有兩種想法 ：

- **Merge Sort**
- 當 N < 40000 時，Merge Sort 最差情況為 $O(N^{1.3})$，比 Quick Sort、Shell Sort 的 $O(N \log N)$ 更快。

- **Counting Sort**
- 在數據集中時表現非常好，時間複雜度為 $O(N + k)$。
- 但若測資中有極大或極小值，導致 k 過大，則效能下降。

經過測試後，我這一次遇到的數字範圍約在 -22000 ~ 22000，所以我選擇使用Counting sort 來做！

---

## 使用 Counting Sort：字元範例

### 輸入範例：

e a a b d e c c

---

### 排序流程圖解：

#### Step 1：讀入字元 `e`，count['e']++

#### Step 2：讀入字元 `a`，count['a']++

#### Step 3：讀入字元 `a`，count['a']++

#### Step 4：讀入字元 `b`，count['b']++

#### Step 5：讀入字元 `d`，count['d']++

#### Step 6：讀入字元 `e`，count['e']++

#### Step 7：讀入字元 `c`，count['c']++

#### Step 8：讀入字元 `c`，count['c']++

#### Step 9：計算前綴和 start[]

#### Step 10：計算累加值 start + count

---

### 排序結果：

索引：    0   1   2   3   4   5   6   7  
內容：    a   a   b   c   c   d   e   e

---

## 原始 Java 程式碼（使用 Scanner）

import java.util.Scanner;

public class Main {
    static final int size = 44000; 
    static final int OFFSET = 22000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] number = new int[n];
        int[] count = new int[size];
        int[] start = new int[size];
        int[] output = new int[n];

        for (int i = 0; i < n; i++) {
            number[i] = sc.nextInt();
            count[number[i] + OFFSET]++;
        }

        for (int i = 0; i < size - 1; i++) {
            start[i + 1] = start[i] + count[i];
        }

        for (int i = 0; i < n; i++) {
            output[start[number[i] + OFFSET]++] = number[i];
        }

        for (int i = 0; i < n; i++) {
            System.out.print(output[i] + " ");
        }
    }
}

---

## 原始版本的缺點

- 使用 `Scanner` + `System.out.print()` 效率低
- 對於大量輸入輸出，執行速度慢

---

## 第一版優化：改用高速 I/O

### 優化方式：
- 輸入：改用 `System.in.read()` 搭配 buffer
- 輸出：改用 `System.out.write()` 及自製 `writeNum()`

public class Main {
    static final int SIZE = 44000;
    static final int OFFSET = 22000;
    static final int MAX = 20000;

    static final int[] count = new int[SIZE];
    static final int[] start = new int[SIZE];
    static final int[] number = new int[MAX];
    static final int[] output = new int[MAX];

    static final byte[] buf = new byte[1 << 20]; // 輸入緩衝 (2^20byte 約1MB)
    static int ptr = 0, len = 0;

    static final byte[] outbuf = new byte[1 << 23]; // 輸出緩衝 (2^23 約8MB)
    static int outptr = 0;

    public static void main(String[] args) throws Exception {
        len = System.in.read(buf);
        int n = readInt();

        for (int i = 0; i < n; i++) {
            number[i] = readInt();
            count[number[i] + OFFSET]++;
        }

        for (int i = 0; i < SIZE - 1; i++) {
            start[i + 1] = start[i] + count[i];
        }

        for (int i = 0; i < n; i++) {
            int val = number[i];
            int idx = start[val + OFFSET]++;
            output[idx] = val;
        }

        for (int i = 0; i < n; i++) {
            writeNum(output[i]);
        }

        System.out.write(outbuf, 0, outptr);
    }

    static int readInt() {
        int val = 0;
        byte b = buf[ptr++];
        while (b <= ' ') b = buf[ptr++]; // 遇到空格跳過

        boolean negative = (b == '-'); // 判斷是否為負數
        if (negative) b = buf[ptr++];    // 跳過負號

        do {
            val = (val << 3) + (val << 1) + (b & 15); //使用二進位做 val*10+b 
     // val << 3 = val * 2 ^ 3 = val * 8
     // val << 1 = val * 2 ^ 1 = val * 2
     // b & 15 二進制ASCII轉數字取後四位 所以b and 15(1二進制 = 00001111) 即可轉為數字
        
            if (ptr >= len) break;
            b = buf[ptr++];
        } while (b >= '0');

        return negative ? -val : val; 
    }

    static void writeNum(int num) {
        if (num < 0) {
            outbuf[outptr++] = '-'; 
            num = -num;
        }

        int tmpPtr = outptr;
        int digits = 0;

        do {
            outbuf[outptr++] = (byte) ('0' + num % 10);
            num /= 10;
            digits++;
        } while (num > 0);

        // 反轉數字部分
        for (int i = 0; i < digits / 2; i++) {
            byte temp = outbuf[tmpPtr + i];
            outbuf[tmpPtr + i] = outbuf[tmpPtr + digits - 1 - i];
            outbuf[tmpPtr + digits - 1 - i] = temp;
        }

        outbuf[outptr++] = ' ';
    }
}

---

### 效能阻礙分析

        for (int i = 0; i < n; i++) {
            number[i] = readInt();
            count[number[i] + OFFSET]++;
        }

        for (int i = 0; i < SIZE - 1; i++) {
            start[i + 1] = start[i] + count[i];
        }

        for (int i = 0; i < n; i++) {
            int val = number[i];
            int idx = start[val + OFFSET]++;
            output[idx] = val;
        }

        for (int i = 0; i < n; i++) {
            writeNum(output[i]);
        }

- 共使用 4 個 for 迴圈
- 空間使用量高：number[], output[], start[]
- 時間複雜度為：**2n + k**

---

## 第二版優化：節省空間 + 非穩定排序

### 核心優化重點：

- 使用 `short[] count` 節省記憶體
- 不使用 `start[]`、`output[]`、`number[]`
- 不保證穩定排序，但大幅提升效能

class Main {
    static final int SIZE = 44000;
    static final int OFFSET = 22000;
    static final short[] count = new short[SIZE];

    static final int BUF_SIZE = 1 << 19;
    static final byte[] buf = new byte[BUF_SIZE];
    static int ptr = 0, len = 0;

    static final byte[] outbuf = new byte[1 << 23];
    static int outptr = 0;
    static final byte[] numbuf = new byte[20]; 

    public static void main(String[] args) throws Exception {
        len = System.in.read(buf);
        int n = readInt();

        for (int i = 0; i < n; i++) {
            int x = readInt();
            int idx = x + OFFSET;
            if (count[idx] != 65535) count[idx]++;
        }

        int printed = 0;
        for (int i = 0; i < SIZE && printed < n; i++) {
            int times = count[i] & 0xFFFF;
            while (times-- > 0) {
                writeInt(i - OFFSET);
                printed++;
                if (printed == n) break;
            }
        }

        System.out.write(outbuf, 0, outptr);
    }

    static int readInt() {
        int x = 0;
        int b = buf[ptr++];
        while (b <= ' ') b = buf[ptr++];

        boolean neg = (b == '-');
        if (neg) b = buf[ptr++];

        while (b >= '0') {
            x = (x << 3) + (x << 1) + (b & 15);
            b = buf[ptr++];
        }
        return neg ? -x : x;
    }

    static void writeInt(int x) {
        if (x == 0) {
            outbuf[outptr++] = '0';
            outbuf[outptr++] = ' ';
            return;
        }

        if (x < 0) {
            outbuf[outptr++] = '-';
            x = -x;
        }

        int p = 0;
        while (x > 0) {
            numbuf[p++] = (byte) (x % 10 + '0');
            x /= 10;
        }
        while (p-- > 0) {
            outbuf[outptr++] = numbuf[p];
        }
        outbuf[outptr++] = ' ';
    }
}

---

## 兩版比較總表

| 項目 | 第一版（穩定） | 第二版（非穩定） |
|------------------|----------------|------------------|
| 穩定排序 | ⭕ 是 | ❌ 否 |
| 陣列使用 | 多 | 少（僅 count[]） |
| 記憶體佔用 | 高 | 低 |
| 實際時間複雜度 | O(2n + k) | O(n + k) |
| 適合場景 | 功能正確、教學 | 競賽、效能極限場景 |

---

## 總結建議

| 使用情境 | 建議使用版本 |
|----------------------|----------------|
| 需要穩定排序 | 第一版 |
| 極限效能需求 | 第二版 |
| 小型資料測試 | 第一版 |
| 線上比賽、大資料輸入 | 第二版 |

---
有任何建議、想法歡迎跟我說！！！