排序算法可視化圖鑒：七大經典算法原理、複雜度與動態演示

前言

排序是計算機科學最基礎也最迷人的課題之一。本文精選七大經典排序算法，從核心思想、步驟邏輯、時空複雜度、適用場景到動態 GIF 演示，構建直觀的算法心智模型，助你面試、教學、工程選型游刃有餘。

一、快速排序 — 實戰性能之王

核心思想

Tony Hoare 1962 年發明。分治策略：選基準，一趟掃描將數組分為「小於基準」與「大於基準」兩個子區，基準歸位，遞歸處理子區。

關鍵步驟

1. 選 Pivot（首元素、隨機、三數取中）。
2. Partition：雙指針左右掃描交換，最終 Pivot 位於有序位置。
3. 遞歸排序左右子數組。

動態演示

工程優化

• 小數組閾值切換插入排序（如 < 15）。
• 隨機化 Pivot 或三數取中避免有序數組退化 O(n²)。
• 尾遞歸優化 / 手動棧模擬遞歸限制棧深度。

二、歸併排序 — 穩定排序標桿

核心思想

典型分治法：遞歸拆分至單元素，再合併兩個有序子數組。合併過程需輔助數組，保證穩定性。

合併邏輯

1. 申請臨時數組，大小 = 左長 + 右長。
2. 雙指針比較左/右首元素，小者拷入臨時數組，指針前移。
3. 某側耗盡，將另一側剩餘元素批量拷入。
4. 將臨時數組拷回原數組對應區間。

動態演示

應用場景

• 外部排序（大文件、磁盤數據）。
• LinkedList 排序（不需隨機訪問）。
• 求逆序對、分治題模板。

三、堆排序 — 原地 O(n log n) 保底

核心思想

利用大頂堆/小頂堆（完全二叉樹 + 堆序性質）特性：堆頂恆為極值。構建堆 → 反復交換堆頂與末尾元素、縮小堆範圍、下沉調整。

動態演示

特點

• 時間複雜度恆定 O(n log n)，無最差情況退化。
• 原地排序，空間 O(1)。
• 不穩定，緩存局部性差於快排。

四、選擇排序 — 簡單直觀的「選最小」

邏輯

每輪從無序區選出最小元素，與無序區首位交換。雙層循環，交換次數最少（O(n)）。

動態演示

五、冒泡排序 — 教學經典，工程棄用

邏輯

相鄰比較，大者後移（「冒泡」到末尾）。可優化：若某輪無交換則提前終止。

動態演示

六、插入排序 — 小數組/近乎有序的王者

邏輯

維護前綴有序區，取後續元素在有序區從後向前掃描找位置，移動元素騰位插入。

優勢

• 最好情況 O(n)（已有序）。
• 穩定、原地、適應性強。
• 實際工程中作為快排/歸併的小數組基準排序。

動態演示

注：原文插入排序無 GIF，此處展示希爾排序動態圖，希爾為插入排序改進版。

七、希爾排序 — 插入排序的「跳躍式」升級

核心改進

針對插入排序「單步移動效率低」痛點，引入 增量序列（Gap）：將數組按間隔分組，各組內部插入排序，逐步縮小 Gap 至 1。利用「部分有序時插入排序極快」特性，實現亞 O(n²) 效率。

常用增量序列

• Shell 原版：N/2, N/4, ..., 1
• Hibbard：2^k - 1
• Sedgewick：最佳實踐序列

工程選型速查表

• 通用首選：Arrays.sort() (雙軸快排) / Collections.sort() (TimSort 歸併改進)。
• 海量數據外排：歸併排序（順序讀寫友好）。
• 嵌入式/內存極限：堆排序（O(1) 空間保底）。
• 近乎有序/小規模：插入排序 / TimSort。
• 需穩定性：歸併 / TimSort / 插入 / 冒泡。

結語

排序算法是算法思想的縮影：分治、貪心、數據結構、時空權衡。建議親手實現一次七大算法，並用可視化工具觀察數據流動，方能內化為直覺。