排序演算法 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() |