排序算法筆記：選擇、插入、快速、希爾排序 C++/Java 實現

1. 簡單選擇排序

思路：每輪在未排序區選最小，換到有序區末尾。

void selectSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        swap(a[i], a[minIdx]);
    }
}

複雜度：O(n²)，不穩定，交換次數少（≤ n）。

2. 直接插入排序

思路：將新元素插入已有序序列適當位置。

void insertSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) a[j + 1] = a[j--];
        a[j + 1] = key;
    }
}

複雜度：O(n²)，穩定，近乎有序時 O(n)，適合小規模/基本有序數據。

3. 快速排序

思路：選基準，雙向掃描分區，遞歸處理左右子區。

void quickSort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[(l + r) / 2];
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    quickSort(a, l, j);
    quickSort(a, i, r);
}

複雜度：平均 O(n log n)，最壞 O(n²)（可隨機化基準避免），不穩定，原地排序。

4. 希爾排序

思路：按增量分組插入排序，逐步縮小增量至 1。

void shellSort(vector<int>& a) {
    int n = a.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i], j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

複雜度：依賴增量序列，常見 O(n^1.5)，不穩定，是插入排序的高效改進。

複雜度總結表

工程建議

• 小數組（< 50）：插入排序常比快速排序快。
• 通用排序：std::sort (IntroSort：快速+堆+插入混合)，保證 O(n log n) 最壞情況。
• 需穩定：std::stable_sort (歸併排序)。
• 整數限定範圍：計數/基數排序 O(n)。

總結

掌握四大基礎排序的核心邏輯、代碼模板、複雜度特性與適用場景，是算法面試與工程優化的基本功。實際開發中優先使用標準庫，僅在極端性能敏感或特殊約束下手寫排序。