排序演算法 Sort Algorithm
本篇文章連結:https://4yu.dev/post/Sort-Algorithm/
公開發布日期:2023/02/25
本文架構
線性排序演算法種類
- 氣泡排序 Bubble Sort
- 選擇排序 Selection Sort
- 插入排序 Insertion Sort
- 快速排序 Quick Sort
- 合併排序 Merge Sort
- 堆排序 Heap Sort
- 希爾排序 Shell Sort
- 計數排序 Counting Sort
- 桶排序 Bucket Sort
- 基數排序 Radix Sort
每個排序演算法的內容
- 排序介紹
- 動畫演示
- 實作步驟
- C++ 程式碼
- 注意事項
- 時間複雜度
- 總結
測試模板
本文介紹的 10 種排序演算法都會附上寫好的函式,這裡提供可 EOF 輸入的測試模版,請在區塊中加上各種排序演算法函式,若沒有指定呼叫方法則直接呼叫函式名稱即可運作
1 |
|
排序演算法的詳細介紹
氣泡排序 Bubble Sort
氣泡排序是一種簡單的排序演算法,原理是依序比較相鄰的兩個元素,如果前一個元素大於後一個元素,就交換它們的位置,重複進行直到排序完成。
因為排序過程中較大的元素會像氣泡一樣慢慢浮到數列的右端,所以叫氣泡排序。
動畫演示

實作步驟
- 外層 for 迴圈控制待排序的數量,每一輪會減少一個,直到排序完成
- 內層 for 迴圈表示每輪需要比較的次數
- 如果前一個數大於後一個數,則使用 swap() 交換
C++ Code
1 | void BubbleSort() |
優化
如果某輪沒有發生交換,就代表數列已經排好了可以提前結束,這樣可以減少後面發生不必要的比較
C++ Code
1 | void BubbleSort() |
時間複雜度
- 時間複雜度:
每一輪排序都需要進行 次比較,而最多需要進行 輪排序。
因此,總的比較次數為
取最高次項所以時間複雜度為
總結
氣泡排序演算法是一種簡單但效率較低的排序演算法,通常只適用於小規模資料的排序。
選擇排序 Selection Sort
選擇排序是一種簡單的排序演算法,它的原理是選擇最小的元素,與第一個元素交換位置,然後在剩下的元素中選擇最小的元素,與第二個元素交換位置,以此類推,重複直到排序完成。
動畫演示

實作步驟
- 外層 for 迴圈遍歷 個元素
- 每輪設最小值為第 個元素
- 內層迴圈從 開始往後遍歷到底,更新最小值位置
- 交換第 個元素與最小值
C++ Code
1 |