本篇文章連結:https://4yu.dev/post/Sort-Algorithm/
公開發布日期:2023/02/25


本文架構

線性排序演算法種類

  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)
{