本篇文章連結：https://4yu.dev/post/Sort-Algorithm/

本文架構 🔗

線性排序演算法種類 🔗

  1. 氣泡排序 Bubble Sort
  2. 選擇排序 Selection Sort
  3. 插入排序 Insertion Sort
  4. 快速排序 Quick Sort
  5. 合併排序 Merge Sort
  6. 堆排序 Heap Sort
  7. 希爾排序 Shell Sort
  8. 計數排序 Counting Sort
  9. 桶排序 Bucket Sort
  10. 基數排序 Radix Sort

每個排序演算法的內容 🔗

  • 排序介紹
  • 動畫演示
  • 實作步驟
  • C++ 程式碼
  • 注意事項
  • 時間複雜度
  • 總結

測試模板 🔗

本文介紹的 10 種排序演算法都會附上寫好的函式，這裡提供可 EOF 輸入的測試模版，請在區塊中加上各種排序演算法函式，若沒有指定呼叫方法則直接呼叫函式名稱即可運作

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
#include <bits/stdc++.h>
using namespace std;

vector<int> v;

// 可以將底下的某個排序演算法函式複製起來放進來這個區塊
// ----------------------------------------------





// ----------------------------------------------

int main(void)
{
    int n;
    while (cin >> n) v.emplace_back(n);

    // 這行放入某個排序演算法函式名稱用來呼叫 例如：BubbleSort();
    // ------------------------------------------

    // ------------------------------------------
    
    for (auto &i : v) cout << v[i] << " ";
    return 0;
}

排序演算法的詳細介紹 🔗

氣泡排序 Bubble Sort 🔗

氣泡排序是一種簡單的排序演算法，原理是依序比較相鄰的兩個元素，如果前一個元素大於後一個元素，就交換它們的位置，重複進行直到排序完成。
因為排序過程中較大的元素會像氣泡一樣慢慢浮到數列的右端，所以叫氣泡排序。

動畫演示 🔗

BubbleSort 動畫演示

實作步驟 🔗

  1. 外層 for 迴圈控制待排序的數量，每一輪會減少一個，直到排序完成
  2. 內層 for 迴圈表示每輪需要比較的次數
  3. 如果前一個數大於後一個數，則使用 swap() 交換

C++ Code 🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort()
{
    int n = v.size();
    for (int i=n; i>1; --i)
    {
        for (int j=0; j<i-1; ++j)
        {
            if (v[j] > v[j+1]) 
            {
                swap(v[j],v[j+1]);
            }
        }
    }
}

優化 🔗

如果某輪沒有發生交換，就代表數列已經排好了可以提前結束，這樣可以減少後面發生不必要的比較

C++ Code 🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort()
{
    int n = v.size();
    for (int i=n; i>1; --i)
    {
        bool check = false;
        for (int j=0; j<i-1; ++j)
        {
            if (v[j] > v[j+1]) 
            {
                swap(v[j],v[j+1]);
                check = true;
            }
        }
        if (!check) break;
    }
}

時間複雜度 🔗

  • 時間複雜度：O(n2)O(n^2)

    每一輪排序都需要進行 n−in-i 次比較，而最多需要進行 n−1n-1 輪排序。
    因此，總的比較次數為 (n−1)+(n−2)+...+2+1=(n2−n)/2(n-1)+(n-2)+...+2+1=(n^2-n)/2
    取最高次項所以時間複雜度為 O(n2)O(n^2)

總結 🔗

氣泡排序演算法是一種簡單但效率較低的排序演算法，通常只適用於小規模資料的排序。

選擇排序 Selection Sort 🔗

選擇排序是一種簡單的排序演算法，它的原理是選擇最小的元素，與第一個元素交換位置，然後在剩下的元素中選擇最小的元素，與第二個元素交換位置，以此類推，重複直到排序完成。

動畫演示 🔗

Selection Sort 動畫演示

實作步驟 🔗

  1. 外層 for 迴圈遍歷 0→n−10 \to n-1 個元素
  2. 每輪設最小值為第 ii 個元素
  3. 內層迴圈從 ii 開始往後遍歷到底，更新最小值位置
  4. 交換第 ii 個元素與最小值

C++ Code 🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectionSort()
{
    int n = v.size();
    for (int i=0; i<n-1;++i)
    {
        int mini = i;
        for (int j=i; j<n; ++j)
        {
            if (v[j] < v[mini])
            {
                mini = j;   
            }
        }
        swap(v[i], v[mini]);
    }
}

時間複雜度 🔗

  • 時間複雜度：O(n2)O(n^2)

    選擇排序的核心操作是選擇最小元素，將其與當前位置交換，而選擇最小元素需要在未排序的序列中進行線性搜索，因此需要執行 nn 次循環和 nn 次內層循環，時間複雜度為 O(n2)O(n^2)。

總結 🔗

選擇排序演算法是一種簡單但效率較低的排序演算法，通常只適用於小規模資料的排序，且較不穩定，如當元素相等時，彼此順序還是會改變。

插入排序 Insertion Sort 🔗

將未排序的資料依次插入已排序序列中，形成新的已排序序列。

動畫演示 🔗

Insertion Sort 動畫演示

實作步驟 🔗

  1. for 遍歷 1→n−11 \to n-1 個元素
  2. 暫時取出 v[i]v[i] 為待插入元素 設 jj 為插入點 初始為 i−1i-1
  3. 用 while 迴圈開始由後往前掃描 確認在範圍內且待插入元素小於掃到的元素
  4. 把掃過的元素往後面搬 且 jj 遞減
  5. 若碰到最前面了或是遇到比待插入元素還要大的就退出 while 迴圈
  6. 將 插入點 設為待插入元素 v[i]v[i]

C++ Code 🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertSort()
{
    int n = v.size();
    for (int i=1; i<n;++i)
    {
        int temp = v[i], j = i-1;
        while (j >= 0 && temp < v[j])
        {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = temp;
    }
}

注意事項 🔗

  • while 迴圈條件要設定邊界，插入點須 ≥0\ge 0。

時間複雜度 🔗

  • 時間複雜度：O(n2)O(n^2)

    要遍歷 n−1n-1 個元素，每次要往前掃瞄並搬動元素

總結 🔗

插入排序演算法是一種簡單但效率較低的排序演算法，通常只適用於小規模資料的排序。

合併排序 Merge Sort 🔗

合併排序 Merge Sort 是一種基於分治法的排序演算法，也是一種比較經典且常用的排序演算法之一。

合併排序的主要流程包括分解、排序和合併三個步驟。
首先將要排序的序列分成兩部分，分別對這兩部分進行排序，最後將排好序的兩個部分合併起來即可得到排序後的序列。
在排序的過程中，通過遞歸地將序列分解成小問題，再利用合併操作將小問題的解合併成原問題的解。

動畫演示 🔗

Merge Sort 動畫演示

實作步驟 🔗

  1. 定義 MergeSort() 將 l、r 作為參數
  2. 算出 mid 拆成兩半 當 l == r 代表已排好可以返回，否則分別遞迴做拆分
  3. 呼叫 merge() 帶入 l,r 將 [l,r] 區間中兩個已排序的數列合併成一個已排序的數列
  4. merge() 先算出 mid 以及建立一個暫存的數列，長度設為合併後的數列長度
  5. for 用兩個指針分別從 l 和 mid 開始遍歷，哪個較小就先放入暫存數列中（注意邊界）
  6. 將排序好的暫存數列全部更新至原數列中

C++ Code 🔗

呼叫時請用 MergeSort(0, v.size());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge(int l, int r)
{
    int mid = (l+r)/2, tmp[r-l+1];
    for(int i=l, j=mid+1, k=0; i<=mid || j<=r; ++k)
    {
        if((v[i] <= v[j] && i <= mid) || j > r) tmp[k] = v[i++];
        else tmp[k] = v[j++];
    }
    for(int i=l, j=0; i<=r; ++i, ++j) v[i] = tmp[j];
}

void MergeSort(int l, int r)
{
    if(l == r) return;
    int mid = (l+r)/2;
    MergeSort(l, mid); MergeSort(mid+1, r);
    merge(l, r);
}

注意事項 🔗

  • 注意邊界 在 merge()merge() 中 確保 i,ji,j 兩指針不會跑出兩數列
  • 注意分割遞迴終止條件 是 l == r
  • tmp 的長度是 r−l+1r-l+1
  • for 的 kk 從 00 開始 取左時 ++i 取右時 ++j
  • 比大小時注意要多加上邊界條件 且若右數列取完了就直接取左列元素
  • 最後要把暫存元素更新到原數列中時 注意初始位置

時間＆空間複雜度 🔗

  • 平均時間複雜度：O(nlog⁡n)O(n\log n)

    在平均情況下，合併排序的時間複雜度為 O(nlog⁡n)O(n\log n)。這是因為在合併排序的過程中，每個元素都需要進行一次比較，而且每個元素都需要被移動到新數組中的正確位置，這樣每個元素都需要進行 log⁡n\log n 級別的操作。

  • 空間複雜度：O(n)O(n)

    合併排序需要額外的空間來存儲排序過程中的元素，這些儲存空間的大小與待排序數列的大小相同。

總結 🔗

合併排序是一種高效穩定的排序算法，通過分治的思想，先拆分問題再合併解決。其時間複雜度為 O(nlog⁡n)O(n \log n)，在處理大量資料時表現良好。在實作時需要注意指針的起始值、合併區間的邊界問題等細節。

快速排序 Quick Sort 🔗

快速排序 Quick Sort 是一種常見的分治演算法，被認為是最快的排序演算法之一。
它是選擇一個基準元素（通常是中間點），通過一趟排序將待排序列分為兩部分，
其中一部分的所有元素都比基準元素小，另一部分的所有元素都比基準元素大，
然後再按照此方法對這兩部分分別進行快速排序，直到整個序列有序。

動畫演示 🔗

本動畫以左邊當基準點
Quick Sort 動畫演示

實作步驟 🔗

  1. 選擇中間點為基準點元素 pivot
  2. 找到左邊大於等於基準點的元素以及右邊小於等於基準點的元素
  3. 如果左邊大於等於右邊，交換它們
  4. 遞迴排序左半部分以及右半部分

C++ Code 🔗

呼叫時請用 QuickSort(0, v.size());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void QuickSort(int l, int r) 
{
    if (l >= r) return;
    int i = l, j = r, pivot = v[(l + r) / 2];
    while (i <= j) 
    {
        while (v[i] < pivot) i++;
        while (v[j] > pivot) j--;
        if (i <= j) 
        {
            swap(v[i], v[j]);
            i++; j--;
        }
    }
    QuickSort(l, j); QuickSort(i, r);
}

時間複雜度 🔗

  • 平均時間複雜度：O(nlog⁡n)O(n\log n)

    在平均情況下，每次切分都能將數列分為近似相等的兩個子數列，快速排序的時間複雜度為 O(nlog⁡n)O(n\log n)。

  • 最壞時間複雜度：O(n2)O(n^2)

    當數列已經排好序或接近排好序時，選擇第一個或最後一個元素作為基準元素，時間複雜度會退化為 O(n2)O(n^2)。

注意事項 🔗

  • 需要注意邊界條件，例如遞迴結束的條件。
  • 快速排序是一個不穩定的排序演算法，相同元素的相對位置可能會在排序後發生變化。
  • 在選擇 pivot 時，可以選擇任意一個元素作為 pivot，但選擇哪個 pivot 會影響到排序的效率。如果每次都選擇最小或最大的元素作為 pivot，就會導致最壞情況下的時間複雜度從 O(nlog⁡n)O(n\log n) 暴增為 O(n2)O(n^2)。因此，為了避免這種情況，可以選擇隨機的 pivot，通常選擇數列的中間元素作為 pivot，這樣可以確保每次排序的平均時間複雜度都是 O(nlog⁡n)O(n\log n)。

總結 🔗

快速排序演算法是透過分治，達成高效率的排序演算法。它可以在短時間內對大型資料進行排序。儘管最壞情況下的時間複雜度較高，但在大多數情況下，它的表現都很優秀。

堆積排序 Heap Sort 🔗

堆積排序 Heap Sort 是一種使用二元樹 Binary Tree 資料結構的排序演算法。

堆可以看作是一個完全二元樹，它具有以下兩個性質：

  1. 父節點的值永遠大於或等於（小於或等於）子節點的值。
  2. 堆中任意節點的子樹都符合上述特點。

實作步驟 🔗

  1. 建立堆：將待排序的數列轉換成一個堆。這一步可以通過從最後一個非葉子節點開始，對每個節點進行調整來實現。具體來說，對於一個父節點，如果它的子節點的值比它的值大（或小），就交換它們，直到子樹也是一個堆，調整完成後就得到了一個初始的大根堆。
  2. 排序：從堆的尾部開始，每次取出堆頂元素與堆尾元素交換位置。交換後，堆的長度減1，重複此操作直到堆的大小為1，由於每次都是取出堆頂元素，所以得到的數列就是有序的，以保證元素依然構成一個大根堆。

C++ Code 🔗

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
void heapify(int n, int i) 
{
    int mx = i; // 初始化最大值為根節點
    int lt = 2 * i + 1; // 找到左子節點的索引
    int rt = 2 * i + 2; // 找到右子節點的索引
    if (lt < n && v[lt] > v[mx]) // 如果左子節點的值比最大值還要大
    { 
        mx = lt; // 更新最大值的索引為左子節點的索引
    }
    if (rt < n && v[rt] > v[mx]) // 如果右子節點的值比最大值還要大
    { 
        mx = rt; // 更新最大值的索引為右子節點的索引
    }
    if (mx != i) // 如果最大值不是根節點
    { 
        swap(v[i], v[mx]); // 把最大值交換到根節點
        heapify(n, mx); // 遞迴對以最大值為根的子樹進行heapify操作
    }
}

void HeapSort() 
{
    int n = v.size();
    for (int i = n / 2 - 1; i >= 0; i--) // 建立最大堆
    { 
        heapify(n, i);
    }
    for (int i = n - 1; i > 0; i--) // 進行堆排序
    { 
        swap(v[0], v[i]); // 把最大值與根節點交換
        heapify(i, 0); // 對剩餘元素進行 heapify 操作
    }
}

時間＆空間複雜度 🔗

  • 時間複雜度：O(nlogn)O(nlogn)

    在堆積排序中，排序的主要操作是下潛，即將堆頂元素下潛到合適的位置，這個操作的時間複雜度是 O(logn)。在排序過程中，需要執行 n 次下潛操作，因此排序的時間複雜度為 O(nlogn)O(nlogn)。

  • 空間複雜度：O(1)O(1)

    由於堆積排序是一種原地排序算法，因此它的空間複雜度是 O(1)O(1)，即不需要額外的空間。在堆排序中，只需要用到常數個變量作為中間變量，不需要額外的數組或其他資料結構。

注意事項 🔗

  1. 記得使用交換操作來實現堆的調整和排序。
  2. 調整堆的時候，要先找到子節點中的最大值，然後再和父節點比較，如果子節點的值比父節點大，就將子節點的值上移。
  3. 調整堆的時候，要特別注意邊界情況，例如在定位左右子節點的時候，要判斷右子節點是否存在。

總結 🔗

堆排序是一種高效的排序算法，它具有良好的時間複雜度和空間複雜度，並且它只需要一個輔助空間來存儲堆，可以實現原地排序，因此堆排序在排序大資料時非常有效。但是在實際應用中，由於堆排序的常數因子比較大，因此實際運行速度可能不如快速排序和插入排序等算法。

希爾排序（Shell Sort） 🔗

希爾排序（Shell Sort）是一種插入排序的改進版，其基本思想是先將待排序的序列按照一定間隔分成幾個子序列，然後對每個子序列進行插入排序。接著逐步縮小間隔，重複進行上述操作，直到間隔縮小到1時，最後對整個序列進行一次插入排序，完成排序。

希爾排序的主要優點是在比較次數和移動次數上都有所改進，因為希爾排序採用分組的方式進行插入排序，每次排序可以使得一定程度上有序，因此在進行後面的排序時就可以利用前面排序時建立的有序性，減少比較次數和移動次數，此外希爾排序不需要額外的儲存空間。

實作步驟 🔗

  1. 首先選擇一個增量序列，這個序列的選擇可以影響希爾排序的效率。
  2. 將待排序的序列按照增量序列分成幾個子序列，對每個子序列進行插入排序。
  3. 逐步縮小增量序列，重複上述操作，直到增量為 1 時，最後對整個序列進行一次插入排序，完成排序。

C++ Code 🔗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ShellSort() 
{
    int n = v.size();
    // 初始化增量 gap，設為 n/2、n/4、n/8、...直到 1
    for (int gap = n / 2; gap > 0; gap /= 2) 
    {
        // 以 gap 為間隔，對每個子序列進行插入排序
        for (int i = gap; i < n; i++) 
        {
            int temp = v[i], j;
            for (j = i; j >= gap && v[j - gap] > temp; j -= gap) 
            {
                v[j] = v[j - gap];
            }
            v[j] = temp;
        }
    }
}

時間＆空間複雜度 🔗

  • 時間複雜度：

    希爾排序的時間複雜度取決於子序列的間隔序列（Increment sequence），一般會使用 Hibbard 增量序列（Hibbard’s increment sequence），其公式為：hk=2k−1h_k = 2^k - 1，其中 k 為子序列的索引，h_k 為對應的增量。

    • 平均時間複雜度：O(n(logn)2)O(n(logn)^2)
    • 最壞時間複雜度：O(n(logn)2)O(n(logn)^2)
    • 最佳時間複雜度：O(n)O(n)

  • 空間複雜度：O(1)O(1)

    希爾排序是一種原地排序算法，只需要一個輔助變量來進行元素交換，因此空間複雜度為 O(1)O(1)

注意事項 🔗

  1. 在實際應用中，希爾排序的實現需要根據具體情況進行優化，選擇合適的增量序列，以及在實現中注意避免不必要的交換和比較操作，從而提高排序的效率。
  2. 增量序列的選擇很重要，通常建議使用 Shell 提出的增量序列（1, 4, 13, 40, …），但也可以根據具體情況進行調整。
  3. 插入排序可以使用直接插入排序或折半插入排序，具體選擇哪種排序算法可以根據實際情況進行選擇。
  4. 希爾排序的實現比較複雜，需要較好的理解和熟練的實現技巧。此外，在某些特殊情況下，希爾排序的效率可能會比其他排序算法低，因此在實際應用中需要仔細選擇排序算法。

總結 🔗

希爾排序是一種高效的排序算法，它通常比傳統的插入排序要快很多，特別是對於大型資料集。希爾排序采用分組的方式進行插入排序，每次排序可以使得一定程度上有序，因此在進行後面的排序時就可以利用前面排序時建立的有序性，減少比較次數和移動次數。

計數排序（Counting Sort） 🔗

計數排序（Counting Sort）是一種線性時間的排序算法，它可以用於排序一定範圍內的整數。計數排序的核心思想是先統計每個元素出現的次數，然後根據元素出現的次數，將元素排列成有序序列。

動畫演示 🔗

計數排序動畫演示

實作步驟 🔗

  1. 計算待排序數組中每個元素出現的次數。假設待排序的元素範圍為 [0, k]，則可以創建一個長度為 k+1 的計數數組，對於每個出現的元素值，在計數數組中相應的位置上加一。
  2. 對計數數組進行遍歷，依次累加前面所有元素的值，得到每個元素在有序序列中的位置。從計數數組的第二個元素開始，依次將前一個元素的值加到當前元素上，最終得到一個每個元素在有序序列中的位置的累加數組。
  3. 根據計數數組和有序序列的位置信息，將元素依次放入有序序列中。從原數組末尾開始，對每個元素值，從累加數組中取得對應的位置，把該元素放入有序序列中的該位置。每放入一個元素，該位置在累加數組中的值就需要減一。
  4. 將有序序列返回到原數組中。

C++ Code 🔗

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
void CountingSort() 
{
    int n = v.size();
    int max_val = 100;  // 假設元素的範圍為[0,100]

    // 計算元素出現的次數，初始化計數數組為0
    vector<int> count(max_val + 1, 0);
    for (int i = 0; i < n; i++) 
    {
        count[v[i]]++;  // 計算v[i]出現的次數
    }

    // 累加前面所有元素的值，得到每個元素在有序序列中的位置
    for (int i = 1; i <= max_val; i++) 
    {
        count[i] += count[i - 1];  // 累加前面所有元素的值
    }

    // 根據計數數組和有序序列的位置信息，將元素依次放入有序序列中
    vector<int> result(n, 0);
    for (int i = n - 1; i >= 0; i--) 
    {
        result[count[v[i]] - 1] = v[i];  // 將v[i]放到有序序列的對應位置上
        count[v[i]]--;  // 將計數數組中對應元素的值減1
    }

    // 將結果返回到原數組中
    for (int i = 0; i < n; i++) 
    {
        v[i] = result[i];
    }
}

注意事項 🔗

  • 計數排序只適用於元素範圍較小的情況。如果元素範圍過大，則需要創建過大的計數數組，進而影響排序的效率和空間複雜度。
  • 計數排序是一種穩定的排序演算法。如果待排序數組中有相等的元素，排序後相等元素的相對位置不會改變。
  • 計數排序對於浮點數和負整數排序的支援不好。

時間＆空間複雜度 🔗

  • 時間複雜度：O(n+k)O(n+k)

    計數排序的時間複雜度可以分為兩部分：計數過程和排序過程。首先是計數過程，需要對整個序列進行一次遍歷，把每個元素出現的次數記錄在計數數組中。由於計數數組的大小等於待排序序列的範圍，因此計數過程的時間複雜度為 O(n+k)O(n+k)，其中 n 是序列的長度，k 是序列中元素的範圍。接下來是排序過程，需要遍歷待排序序列，根據計數數組中的信息將每個元素放置到排序好的位置上。由於只需要遍歷一次待排序序列，因此排序過程的時間複雜度為 O(n)O(n)。因此，計數排序的時間複雜度為 O(n+k)O(n+k)，其中 n 為待排序元素的數量，k 為待排序元素的最大值。需要注意的是，當範圍 k 比較大時，計數排序的效率可能會比較低。

  • 空間複雜度：O(k)O(k)

    計數排序的空間複雜度主要取決於計數數組的大小 k。因此，計數排序的空間複雜度為 O(k)。需要注意的是，當範圍 k 比較大時，計數排序的空間複雜度也會相應增加。

總結 🔗

計數排序是一種高效的排序算法，適用於元素範圍較小的場景，在各種應用中都有著廣泛的應用，例如對於年齡、成績等數值型資料的排序。

儘管它的時間複雜度比其他常用排序算法（如快速排序和合併排序）更小，但是它的應用受到了很大的限制，因為它需要在內存中創建一個大小為k的計數數組，如果k太大，計數數組將占用大量內存。此外，計數排序也不適用於具有負值元素的數組。

桶排序（Bucket Sort） 🔗

桶排序（Bucket Sort）是一種非常簡單的排序演算法，它的基本思想是將要排序的資料分為幾個桶，每個桶裡的資料都有一定的範圍。然後，對每個桶中的資料進行排序，最後按照桶的順序將所有桶中的資料合併起來。

實作步驟 🔗

  1. 建立一個 vector 來儲存待排序數列。
  2. 找出數列中的最大值和最小值，並算出每個桶的範圍。
  3. 建立桶(bucket)的數量，這裡以 10 個桶作為範例，並建立一個 vector，裡面包含了 10 個子 vector，分別代表每個桶的元素。
  4. 將資料分配到對應的桶中，具體的方法是透過取整和乘法來判斷資料應該放在哪個桶中。
  5. 對每個桶中的資料進行排序，可以使用 std::sort 函式。
  6. 將排序後的資料依次放回原數組中。

C++ Code 🔗

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
void bucketSort() 
{
    int n = v.size();

    // 建立桶（bucket）的數量，這裡以 10 個桶作為範例
    const int bucket_num = 10;
    vector<vector<int>> buckets(bucket_num);

    // 將資料分配到對應的桶中
    for (int i = 0; i < n; i++) 
    {
        int index = v[i] / bucket_num;
        buckets[index].push_back(v[i]);
    }

    // 對每個桶中的資料進行排序
    for (int i = 0; i < bucket_num; i++) 
    {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 將排序後的資料依次放回原數組中
    int k = 0;
    for (int i = 0; i < bucket_num; i++) 
    {
        for (int j = 0; j < buckets[i].size(); j++)
        {
            v[k] = buckets[i][j];
            k++;
        }
    }
}

注意事項 🔗

  • 桶的大小設置：桶的大小應當選擇適中的值，太小會增加排序的時間複雜度，太大會佔用過多的空間。
  • 桶的數量：桶的數量應當根據資料的範圍和桶的大小進行設置。桶的數量不夠，會造成資料的堆積；桶的數量太多，會浪費空間。
  • 將資料分配到桶(bucket)中時，要注意取整和乘法的方法，避免產生錯誤。
  • 桶內部排序算法的選擇：桶內部的排序算法可以是任何一種穩定的排序算法，例如插入排序、冒泡排序等等。需要根據具體的應用場景選擇最優的算法。

時間＆空間複雜度 🔗

  • 時間複雜度：O(n+k)O(n+k)

    計數排序的時間複雜度可以分為兩部分：計數過程和排序過程。首先是計數過程，需要對整個序列進行一次遍歷，把每個元素出現的次數記錄在計數數組中。由於計數數組的大小等於待排序序列的範圍，因此計數過程的時間複雜度為 O(n+k)O(n+k)，其中 n 是序列的長度，k 是序列中元素的範圍。接下來是排序過程，需要遍歷待排序序列，根據計數數組中的信息將每個元素放置到排序好的位置上。由於只需要遍歷一次待排序序列，因此排序過程的時間複雜度為 O(n)O(n)。因此，計數排序的時間複雜度為 O(n+k)O(n+k)，其中 n 為待排序元素的數量，k 為待排序元素的最大值。需要注意的是，當範圍 k 比較大時，計數排序的效率可能會比較低。

  • 空間複雜度：O(n+k)O(n+k)

    桶排序的空間複雜度取決於桶的數量和每個桶內部元素的個數。由於每個桶內部的元素個數都不超過n/k，因此每個桶所需的空間是 O(n/k)O(n/k)。總空間複雜度就是 O(n+k)O(n + k)。如果k接近n，則空間複雜度就會接近 O(n)O(n)。需要注意的是，當k比較大時，可能會出現空間浪費的情況，因此需要根據具體情況來選擇適當的桶數量。

總結 🔗

桶排序是一種簡單但有效的線性時間複雜度排序算法，優點是簡單易懂，而且比較容易實現。桶排序在資料分佈比較集中的情況下效果較好，但當資料分佈比較分散時，則會產生較多的桶(bucket)。適用於待排序資料分布範圍有限的情況。

基數排序（Radix Sort） 🔗

基數排序是一種非比較排序算法，適用於整數排序。基本思想是根據排序元素的位數，將整數按照位數從低到高或者從高到低進行排序，可以使用桶排序或計數排序等算法來實現。它的排序過程是先從最低有效位開始，依次對每一位進行排序，直到最高有效位。

例如，將一個整數序列按照個位、十位、百位的順序來排序。首先，按照個位進行排序，將序列中所有數字根據個位數分成10個桶，分別把它們放進對應的桶中。然後，按照桶的順序把數字放回原序列中。接下來，再按照十位進行排序，以此類推，直到按照最高有效位進行排序為止。

動畫演示 🔗

基數排序動畫演示

實作步驟 🔗

  1. 找出數組中最大的元素，確定最高位數，用變數 digit 記錄；
  2. 從最低位數開始，將數組中的元素按照該位數的值放入相應的桶子（桶子數量為 10，分別代表 0~9）中，並計算每個桶子中的元素個數；
  3. 計算每個桶子中元素在暫存陣列中的結束位置；
  4. 把元素按照桶子中的順序放入暫存陣列中；
  5. 把暫存陣列中的元素放回原陣列；
  6. 重複步驟 2~5 直到排序完成。

C++ Code 🔗

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
39
40
void RadixSort() 
{
    int max = *max_element(v.begin(), v.end()); // 找出最大值
    int digit = 1;
    vector<int> tmp(v.size()); // 建立暫存的 vector

    while (max / digit > 0) 
    {
        vector<int> count(10); // 計數排序用的計數陣列

        // 計算每個桶子中的元素個數
        for (int i = 0; i < v.size(); i++) 
        {
            int bucket = (v[i] / digit) % 10;
            count[bucket]++;
        }

        // 計算每個桶子中元素在暫存陣列中的結束位置
        for (int i = 1; i < count.size(); i++) 
        {
            count[i] += count[i-1];
        }

        // 把元素放入暫存陣列
        for (int i = v.size() - 1; i >= 0; i--) 
        {
            int bucket = (v[i] / digit) % 10;
            tmp[count[bucket] - 1] = v[i];
            count[bucket]--;
        }

        // 把暫存陣列中的元素放回原陣列
        for (int i = 0; i < v.size(); i++) 
        {
            v[i] = tmp[i];
        }

        digit *= 10; // 到下一個數位
    }
}

注意事項 🔗

  • 基數排序適用於位數相同的數列排序，如果位數不同，需將所有數字補齊至相同位數。
  • 每個位數的排序需要使用穩定排序算法，以保證相同位數上的數字相對位置不變。
  • 實作時需要用到桶來存儲數字，桶的數量與基數相同，這將需要額外的空間開銷。

時間＆空間複雜度 🔗

  • 時間複雜度：O(d(n+k))O(d(n+k))

    其中 d 為最大位數，n 為數組大小，k 為桶子數量，通常為 10（代表數字 0~9）。因為每一位數都要進行一次計數排序，計數排序的時間複雜度為 O(n+k)O(n+k)，所以時間複雜度為 O(d(n+k))。

  • 空間複雜度：O(n+k)O(n+k)

    基數排序的空間複雜度主要由暫存陣列和計數陣列決定，因此空間複雜度為 O(n+k)O(n+k)。

總結 🔗

總結來說，基數排序是一種穩定性較好且時間複雜度為線性的排序算法，但對於數字位數較大的情況下，其空間複雜度較高，可能需要額外的存儲空間。基數排序的優點是能夠處理不同長度的數字，且在數字大小範圍有限的情況下，表現優於快速排序和堆排序。但是，它需要額外的空間儲存桶，且當數字大小範圍非常大時，需要大量的額外空間，並且其時間複雜度也會增加。

排序演算法的分類 🔗

比較排序 Comparison Sort 🔗

  • 交換類排序 Exchange Sort
    • 氣泡排序
    • 快速排序
  • 選擇類排序 Selection Sort
    • 選擇排序
    • 堆積排序
  • 插入類排序 Insertion Sort
    • 插入排序
    • 希爾排序
  • 合併類排序 Merge Sort
    • 合併排序

非比較排序 Non-Comparison Sort 🔗

  • 計數排序
  • 桶排序
  • 基數排序

排序演算法的比較 🔗

排序演算法 最差時間複雜度 平均時間複雜度 最佳時間複雜度 空間複雜度 方式 穩定度
氣泡排序 O(n2)O(n^2) θ(n2)\theta(n^2) ω(n)\omega(n) O(1)O(1) In-place ✅
選擇排序 O(n2)O(n^2) θ(n2)\theta(n^2) ω(n2)\omega(n^2) O(1)O(1) In-place ❌
插入排序 O(n2)O(n^2) θ(n2)\theta(n^2) ω(n)\omega(n) O(1)O(1) In-place ✅
合併排序 O(nlog⁡n)O(n\log n) θ(nlog⁡n)\theta(n \log n) ω(nlog⁡n)\omega(n\log n) O(n)O(n) Out-place ✅
快速排序 O(n2)O(n^2) θ(nlog⁡n)\theta(n\log n) ω(nlog⁡n)\omega(n\log n) O(log⁡n)O(\log n) In-place ❌
堆積排序 O(nlog⁡n)O(n\log n) θ(nlog⁡n)\theta(n\log n) ω(nlog⁡n)\omega(n\log n) O(1)O(1) In-place ❌
希爾排序 O(nlog⁡2n)O(n \log^2 n) θ(nlog⁡n)\theta(n\log n) ω(nlog⁡2n)\omega(n \log^2 n) O(1)O(1) In-place ❌
計數排序 O(n+k)O(n+k) θ(n+k)\theta(n+k) ω(n+k)\omega(n+k) O(k)O(k) Out-place ✅
桶排序 O(n2)O(n^2) θ(n+k)\theta(n+k) ω(n+k)\omega(n+k) O(n+k)O(n+k) Out-place ❌
基數排序 O(n×k)O(n \times k) θ(n×k)\theta(n \times k) ω(n×k)\omega(n \times k) O(n+k)O(n+k) Out-place ✅

特點與優缺點 🔗

排序演算法 主要特點 優點 缺點
氣泡排序 一種簡單的交換排序演算法，每次將相鄰的元素進行比較和交換 實現簡單，程式易懂 時間複雜度較高，效率低
選擇排序 每次選出最小（大）的元素放到已排序序列的末尾 實現簡單，程式易懂，穩定 時間複雜度較高，效率低
插入排序 將未排序元素逐個插入到已排序的序列中，從後往前比較 實現簡單，對小規模資料排序效率高 時間複雜度較高，對大規模資料排序效率較低
合併排序 分治策略，將序列遞迴划分為子序列，然後將子序列合併 時間複雜度較低，效率較高，穩定 需要較大的輔助空間
快速排序 分治策略，選定一個基準元素，將序列分為左右兩部分，遞迴排序 時間複雜度較低，效率較高，適用於大規模資料排序 不穩定，最壞情況下時間複雜度較高
堆積排序 將序列構建成大根堆（小根堆），每次將堆頂元素與末尾元素交換，重新調整堆 時間複雜度較低，效率較高，適用於大規模資料排序 不穩定
希爾排序 插入排序的改進版本，設定一個增量，將序列劃分為若干子序列進行排序 對於中等規模資料排序效率較高 不穩定
計數排序 統計序列中各元素的出現次數，根據出現次數和元素值的關係排序 時間複雜度較低，適用於資料範圍較小的整數排序 對於資料範圍較大的情況需要較大的輔助空間
桶排序 將元素劃分到不同的桶中，對每個桶中的元素進行排序，最後合併 適用於元素值分佈較均勻的情況，時間複雜度較低 對於元素值分佈不均勻的情況效率較低
基數排序 按照元素的位數進行排序，從低位到高位進行排序，每一位使用穩定排序演算法進行排序 適用於大規模資料排序且穩定，可以處理多關鍵字排序 需要額外的記憶體空間且時間複雜度高，效率較低

文章總結 🔗

在本文中，我們介紹了 10 種常見的排序演算法，每種演算法都有其優點和缺點。
在實際應用中，需要根據具體的情況選擇最適合的排序演算法。
如果你想學習排序演算法，我建議利用本文章及網路上各種資源，理解各個演算法中的原理，並且嘗試自己實作出這些演算法。
通過不斷的練習，你將能更深入地理解這些排序演算法的原理和應用，或許能夠應用來解決現實中的問題，希望此篇文章能讓你有所收穫！

All 排序動畫

參考資料 🔗

此篇文章因內容繁多，所以在整理資料及撰寫上，可能會有些錯誤，也請大家多留言或善用右側聊天室提出問題，我會馬上勘誤修正，謝謝。

回到導覽頁面