演算法筆記：八大排序演算法

演算法>Algorithm>C++>競程>教學
35k 詞
0 瀏覽次數
SORTING_MATRIX_SIMULATOR_v2.0 // 點擊演算法後按鈕跳轉說明
System Standby... // Choose an Algorithm
📖 跳轉到 Bubble Sort 說明

什麼是 Big O (時間複雜度)?

Big O 描述演算法在資料量 n 趨近無限大時的效能趨勢。

演算法 平均 最差 空間 穩定
Bubble Sort O(n²) O(n²) O(1) ✅
Selection Sort O(n²) O(n²) O(1) ❌
Insertion Sort O(n²) O(n²) O(1) ✅
Merge Sort O(n log n) O(n log n) O(n) ✅
Quick Sort O(n log n) O(n²) O(log n) ❌
Heap Sort O(n log n) O(n log n) O(1) ❌
Counting Sort O(n+k) O(n+k) O(k) ✅
Radix Sort O(nk) O(nk) O(n+k) ✅

🔴 Bubble Sort（氣泡排序）

核心思想：每輪把相鄰的兩個元素互比，如果左邊比較大就交換。這樣最大數字會像泡泡一樣「浮」到最右端，然後一直縮小範圍重複這個動作。

什麼時候用？ 幾乎不用於實戰，但因為邏輯最直覺，是學習演算法的起點。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 優化：提早結束
    }
}

int main() {
    vector<int> v = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(v);
    for (int x : v) cout << x << " ";
}
// Output: 11 12 22 25 34 64 90

🔴 Selection Sort（選擇排序）

核心思想：每一輪從「尚未排序的部分」找出最小值，然後跟最前面的元素交換。每輪確定一個位置正確的元素。

注意：Selection Sort 永遠執行 O(n²) 次比較，無論資料本身是否已排序，這是它的最大缺點。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

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

🔴 Insertion Sort（插入排序）

核心思想：想像左手拿著已排好的牌，右手每次從右邊抽一張，然後插進左手牌堆的正確位置。

什麼時候用？ 資料已接近排序完成時（nearly sorted），時間複雜度接近 O(n)！在 std::sort 的 IntroSort 實作中，當子陣列縮到小於 16 個元素時，會切換為 Insertion Sort。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

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

🟡 Merge Sort（合併排序）

核心思想：分治法 (Divide and Conquer). 不斷把陣列對半切，直到每個子陣列只剩 1 個元素。然後再一一將兩個有序陣列「合併」成一個有序陣列。

什麼時候用？ 需要穩定排序且時間複雜度穩定在 O(n log n) 的場合，例如處理鏈結串列、外部排序（待排資料超過記憶體大小）。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> L(arr.begin() + l, arr.begin() + m + 1);
    vector<int> R(arr.begin() + m + 1, arr.begin() + r + 1);
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main() {
    vector<int> v = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v, 0, v.size() - 1);
    for (int x : v) cout << x << " ";
}

🟡 Quick Sort（快速排序）

核心思想：挑一個 Pivot（基準點），把所有比 Pivot 小的元素放到左邊，比 Pivot 大的放到右邊。然後遞迴對左右兩側重複這個動作。

什麼時候用？ 這是實際最常用的排序法。std::sort 的底層 (IntroSort) 即是以 Quick Sort 為核心。平均 O(n log n)，且記憶體使用效率高（In-place）。

⚠️ 坑點：如果每次都選最小/最大值當 Pivot，退化成 O(n²)。實務上要用亂數選 Pivot 或三數取中來避免。

C++ 競程寫法（推薦用 std::sort）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

// 競程直接用 std::sort，底層已是 IntroSort (Quick+Heap+Insertion)
int main() {
    vector<int> v = {10, 7, 8, 9, 1, 5};
    sort(v.begin(), v.end()); // 升冪
    sort(v.begin(), v.end(), greater<int>()); // 降冪

    // 自訂排序
    sort(v.begin(), v.end(), [](int a, int b) {
        return a % 3 < b % 3; // 按模 3 餘數升冪
    });
}

// 手刻版本（理解用）
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

🟡 Heap Sort（堆積排序）

核心思想：利用 Max-Heap（最大堆積） 這種資料結構。先把陣列建成 Max-Heap，然後每次把堆頂（最大值）取出放到末端，再對剩下的部分重新整理成 Heap，重複直到結束。

什麼時候用？ 當你需要 O(n log n) 且 O(1) 空間複雜度的穩定效能（Quick Sort 最差退化，Merge Sort 需要額外空間）。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

// 競程中 priority_queue 就是一個 Max-Heap
int main() {
    priority_queue<int> maxHeap;
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    for (int x : v) maxHeap.push(x);

    vector<int> sorted;
    while (!maxHeap.empty()) {
        sorted.push_back(maxHeap.top());
        maxHeap.pop();
    }
    reverse(sorted.begin(), sorted.end());
    for (int x : sorted) cout << x << " ";
}

// 手刻 Heap Sort
void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

🔵 Counting Sort（計數排序）

核心思想：不靠「比較」來排序！先統計每個數字出現幾次，再依序填回陣列。

限制條件：只適用於整數，且數值範圍 k 不能太大（k = max - min），因為需要建立大小為 k 的計數陣列。

什麼時候用？ 數字範圍明確且較小時（例如成績 0100、字元 0255、APCS 中 N ≤ 10⁶ 且值域為 0~10⁶）可達到 O(n+k) 的速度，比比較式排序更快。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    vector<int> count(range, 0);
    for (int x : arr) count[x - minVal]++;

    int idx = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]-- > 0) arr[idx++] = i + minVal;
    }
}

int main() {
    vector<int> v = {4, 2, 2, 8, 3, 3, 1};
    countingSort(v);
    for (int x : v) cout << x << " ";
    // Output: 1 2 2 3 3 4 8
}

結論

情境 推薦
不知道選什麼 std::sort (Quick/IntroSort)
需要穩定排序 Merge Sort / std::stable_sort
數值範圍小的整數 Counting Sort
已接近排序 Insertion Sort
O(1) 空間且穩定 O(n log n) Heap Sort

💡 競程中 99% 的排序直接用 sort() 就夠了。理解底層邏輯的意義在於：當題目限制特殊時，你才知道挑哪把刀。

SORTING_MATRIX_SIMULATOR_v2.0 // 點擊演算法後按鈕跳轉說明
System Standby... // Choose an Algorithm
📖 跳轉到 Bubble Sort 說明

🔴 Bubble Sort（氣泡排序）

核心思想：每輪把相鄰的兩個元素互比，如果左邊比較大就交換。這樣最大數字會像泡泡一樣「浮」到最右端，然後一直縮小範圍重複這個動作。

什麼時候用？ 幾乎不用於實戰，但因為邏輯最直覺，是學習演算法的起點。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 優化：提早結束
    }
}

int main() {
    vector<int> v = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(v);
    for (int x : v) cout << x << " ";
}
// Output: 11 12 22 25 34 64 90

🔴 Selection Sort（選擇排序）

核心思想：每一輪從「尚未排序的部分」找出最小值，然後跟最前面的元素交換。每輪確定一個位置正確的元素。

注意：Selection Sort 永遠執行 O(n²) 次比較，無論資料本身是否已排序，這是它的最大缺點。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

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

🔴 Insertion Sort（插入排序）

核心思想：想像左手拿著已排好的牌，右手每次從右邊抽一張，然後插進左手牌堆的正確位置。

什麼時候用？ 資料已接近排序完成時（nearly sorted），時間複雜度接近 O(n)！在 std::sort 的 IntroSort 實作中，當子陣列縮到小於 16 個元素時，會切換為 Insertion Sort。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

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

🟡 Merge Sort（合併排序）

核心思想：分治法 (Divide and Conquer). 不斷把陣列對半切，直到每個子陣列只剩 1 個元素。然後再一一將兩個有序陣列「合併」成一個有序陣列。

什麼時候用？ 需要穩定排序且時間複雜度穩定在 O(n log n) 的場合，例如處理鏈結串列、外部排序（待排資料超過記憶體大小）。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> L(arr.begin() + l, arr.begin() + m + 1);
    vector<int> R(arr.begin() + m + 1, arr.begin() + r + 1);
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

int main() {
    vector<int> v = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(v, 0, v.size() - 1);
    for (int x : v) cout << x << " ";
}

🟡 Quick Sort（快速排序）

核心思想：挑一個 Pivot（基準點），把所有比 Pivot 小的元素放到左邊，比 Pivot 大的放到右邊。然後遞迴對左右兩側重複這個動作。

什麼時候用？ 這是實際最常用的排序法。std::sort 的底層 (IntroSort) 即是以 Quick Sort 為核心。平均 O(n log n)，且記憶體使用效率高（In-place）。

⚠️ 坑點：如果每次都選最小/最大值當 Pivot，退化成 O(n²)。實務上要用亂數選 Pivot 或三數取中來避免。

C++ 競程寫法（推薦用 std::sort）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

// 競程直接用 std::sort，底層已是 IntroSort (Quick+Heap+Insertion)
int main() {
    vector<int> v = {10, 7, 8, 9, 1, 5};
    sort(v.begin(), v.end()); // 升冪
    sort(v.begin(), v.end(), greater<int>()); // 降冪
    
    // 自訂排序
    sort(v.begin(), v.end(), [](int a, int b) {
        return a % 3 < b % 3; // 按模 3 餘數升冪
    });
}

// 手刻版本（理解用）
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) swap(arr[++i], arr[j]);
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

🟡 Heap Sort（堆積排序）

核心思想：利用 Max-Heap（最大堆積） 這種資料結構。先把陣列建成 Max-Heap，然後每次把堆頂（最大值）取出放到末端，再對剩下的部分重新整理成 Heap，重複直到結束。

什麼時候用？ 當你需要 O(n log n) 且 O(1) 空間複雜度的穩定效能（Quick Sort 最差退化，Merge Sort 需要額外空間）。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

// 競程中 priority_queue 就是一個 Max-Heap
int main() {
    priority_queue<int> maxHeap;
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    for (int x : v) maxHeap.push(x);

    vector<int> sorted;
    while (!maxHeap.empty()) {
        sorted.push_back(maxHeap.top());
        maxHeap.pop();
    }
    // sorted 是降冪，反轉後得升冪
    reverse(sorted.begin(), sorted.end());
    for (int x : sorted) cout << x << " ";
}

// 手刻 Heap Sort
void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
    for (int i = n-1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

🔵 Counting Sort（計數排序）

核心思想：不靠「比較」來排序！先統計每個數字出現幾次，再依序填回陣列。

限制條件：只適用於整數，且數值範圍 k 不能太大（k = max - min），因為需要建立大小為 k 的計數陣列。

什麼時候用？ 數字範圍明確且較小時（例如成績 0100、字元 0255、APCS 中 N ≤ 10⁶ 且值域為 0~10⁶）可達到 O(n+k) 的速度，比比較式排序更快。

C++ 競程寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    
    vector<int> count(range, 0);
    for (int x : arr) count[x - minVal]++;
    
    int idx = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]-- > 0) arr[idx++] = i + minVal;
    }
}

int main() {
    vector<int> v = {4, 2, 2, 8, 3, 3, 1};
    countingSort(v);
    for (int x : v) cout << x << " ";
    // Output: 1 2 2 3 3 4 8
}

結論

情境 推薦
不知道選什麼 std::sort (Quick/IntroSort)
需要穩定排序 Merge Sort / std::stable_sort
數值範圍小的整數 Counting Sort
已接近排序 Insertion Sort
O(1) 空間且穩定 O(n log n) Heap Sort

💡 競程中 99% 的排序直接用 sort() 就夠了。理解底層邏輯的意義在於：當題目限制特殊時，你才知道挑哪把刀。

留言