在前面三天，我們分別介紹了氣泡排序 (Bubble Sort)、選擇排序 (Selection Sort)、插入排序 (Insertion Sort)。這三個演算法都是經典的「基礎排序」，時間複雜度同樣是 $O(n^2)$，但它們在設計思路、操作方式、適用場景上各有不同。今天我們就來做一次系統化的分析比較。

設計思路

• 氣泡排序 (Bubble Sort): 核心概念是「交換相鄰元素」，每一輪把最大（或最小）的元素一步步冒泡到邊界。
• 選擇排序 (Selection Sort): 核心概念是「每輪選出極值」，然後與前端位置交換。
• 插入排序 (Insertion Sort): 核心概念是「維持已排序區」，每次將新元素插入到正確位置。

可以看到，三者的直覺都很容易理解:

• 氣泡像是把氣泡推到最上面。
• 選擇像是比賽排名，每次挑出最小值。
• 插入像是整理撲克牌，每張牌插到正確位置。

演算法流程比較

複雜度分析

優缺點比較

適用場景

• 氣泡排序: 適合教學與理解「交換」的概念，不適合實務使用。
• 選擇排序: 在「交換成本高」但「比較成本低」的場景可能有用，但實務上幾乎被淘汰。
• 插入排序:
  • 適合小型資料集 (例如幾十筆以內)。
  • 適合幾乎有序的資料。
  • 常用於複雜排序演算法 (如 QuickSort、Timsort) 的子程序，提升效率。

總結

氣泡、選擇、插入三種排序演算法雖然都屬於 $O(n^2)$，但它們代表了三種不同的思路:

• 氣泡: 反覆比較相鄰元素 → 強調交換操作。
• 選擇: 每次挑選極值 → 強調選拔策略。
• 插入: 逐步建立有序區 → 強調元素移動與插入。

在教學上，這三種演算法是理解排序的最佳起點，幫助我們掌握不同的思考角度。在實務上，雖然它們幾乎不會直接使用，但插入排序在某些特殊場景仍具實用價值。