一、什麼是排序算法？爲什麼需要排序？¶

想象你有一堆雜亂的撲克牌，想把它們按大小順序排列；或者考試後想把同學的成績從高到低排序；甚至手機裏的照片想按拍攝時間從早到晚排列——這些場景都需要“排序”。排序算法，簡單說就是把一組無序的數據（比如數字、字符串）變成有序序列（通常是從小到大或從大到小）的方法。

爲什麼排序很重要？在計算機科學中，排序是最基礎也最核心的算法之一。高效的排序算法能讓後續的查找、統計等操作更快完成，比如數據庫查詢優化、數據分析、人工智能中的數據預處理等，都離不開排序。

二、插入排序：像整理撲克牌一樣簡單¶

基本思想¶

插入排序的核心是“逐步構建有序序列”。可以把它想象成你在整理撲克牌：每次從牌堆裏拿出一張未排序的牌，插入到已經排好序的牌堆中的正確位置。

步驟（以數組 [5, 3, 8, 4, 2] 爲例）¶

1. 初始狀態：數組前1個元素 [5] 已經是“有序牌堆”，剩下的元素 [3, 8, 4, 2] 是未排序的“待插入牌”。
2. 處理第一個待插入元素 3：把 3 與已排序的 5 比較，發現 3 < 5，於是把 5 右移一位，騰出位置插入 3，此時有序牌堆變爲 [3, 5]。
3. 處理第二個待插入元素 8：8 與已排序的 5 比較，8 > 5，無需移動，直接插入到末尾，有序牌堆變爲 [3, 5, 8]。
4. 處理第三個待插入元素 4：4 與 8 比較（8 > 4），左移一位；再與 5 比較（5 > 4），左移一位；再與 3 比較（3 < 4），停止移動，插入到 3 後面，有序牌堆變爲 [3, 4, 5, 8]。
5. 處理最後一個待插入元素 2：2 依次與 8、5、4、3 比較，全部大於 2，左移到最前面，最終數組變爲 [2, 3, 4, 5, 8]。

僞代碼¶

for i from 1 to n-1:  // 從第二個元素開始遍歷（第一個元素默認已排序）
    current = arr[i]  // 當前要插入的元素
    j = i - 1         // 已排序元素的最後一個位置
    while j >= 0 and arr[j] > current:  // 找到插入位置
        arr[j+1] = arr[j]  // 已排序元素右移一位
        j = j - 1          // 繼續向左比較
    arr[j+1] = current     // 插入當前元素

優缺點¶

• 時間複雜度：最好情況（已排序數組）是 O(n)（只需遍歷一次，無需移動元素）；最壞情況（逆序數組）是 O(n²)（每次都要移動所有已排序元素）；平均情況 O(n²)。
• 空間複雜度：O(1)（原地排序，不需要額外數組）。
• 穩定性：穩定（相等元素不會交換位置）。
• 適用場景：數據量小（比如幾百個元素）、接近有序的數據，或者對空間敏感的場景。

三、冒泡排序：像水中氣泡“冒”出來一樣¶

基本思想¶

冒泡排序的核心是“相鄰元素比較交換，大的數‘浮’到頂端”。可以想象水中的氣泡，大的氣泡會向上浮動，小的氣泡會被擠到下方。

步驟（以數組 [5, 3, 8, 4, 2] 爲例）¶

1. 第一輪遍歷：從第一個元素開始，依次比較相鄰元素，若順序錯誤則交換。
   - 比較 5 和 3：5 > 3，交換 → [3, 5, 8, 4, 2]
   - 比較 5 和 8：5 < 8，不交換 → [3, 5, 8, 4, 2]
   - 比較 8 和 4：8 > 4，交換 → [3, 5, 4, 8, 2]
   - 比較 8 和 2：8 > 2，交換 → [3, 5, 4, 2, 8]
   - 此時最大的數 8 已“浮”到末尾，第一輪結束。
2. 第二輪遍歷：忽略已“浮”到末尾的 8，重複比較前4個元素：
   - 比較 3 和 5：不交換 → [3, 5, 4, 2, 8]
   - 比較 5 和 4：交換 → [3, 4, 5, 2, 8]
   - 比較 5 和 2：交換 → [3, 4, 2, 5, 8]
   - 此時第二大的數 5 已“浮”到倒數第二位，第二輪結束。
3. 重複此過程：每輪“冒泡”會讓下一個最大的數就位，直到所有數有序。

僞代碼¶

for i from 0 to n-1:  // 遍歷數組
    swapped = false   // 標記是否發生交換
    for j from 0 to n-i-2:  // 每輪遍歷範圍縮小（已冒泡的數不再比較）
        if arr[j] > arr[j+1]:  // 相鄰元素順序錯誤
            swap(arr[j], arr[j+1])  // 交換
            swapped = true
    if not swapped:  // 若本輪無交換，數組已有序，提前退出
        break

優缺點¶

• 時間複雜度：最好情況（已排序數組）O(n)（提前退出）；最壞和平均情況 O(n²)。
• 空間複雜度：O(1)（原地排序）。
• 穩定性：穩定（相等元素不交換）。
• 適用場景：數據量極小（比如幾十個元素）、對代碼簡潔性要求高的場景（但實際工程中很少用，因爲效率低）。

四、歸併排序：分治思想的“分而治之”¶

基本思想¶

歸併排序是第一個體現“分治思想”的算法。核心是“先分解，後合併”：把數組分成兩半，各自排好序，再合併成一個有序數組。可以比喻成把蛋糕切成兩半，各自烤好後再拼在一起。

步驟（以數組 [5, 3, 8, 4, 2] 爲例）¶

1. 分解：先把數組分成兩半，左半 [5, 3] 和右半 [8, 4, 2]；繼續分解，直到每個子數組只有1個元素（自然有序）：[5]、[3]、[8]、[4]、[2]。
2. 合併：從最小的子數組開始，兩兩合併成有序數組：
   - 合併 [5] 和 [3] → [3, 5]；
   - 合併 [8] 和 [4] → [4, 8]；
   - 合併 [2] 單獨存在 → [2]；
   - 合併 [3, 5] 和 [4, 8] → [3, 4, 5, 8]；
   - 最後合併 [3, 4, 5, 8] 和 [2] → [2, 3, 4, 5, 8]。

僞代碼¶

function mergeSort(arr):
    if 數組長度 <= 1:  // 終止條件：單個元素已有序
        return arr
    mid = 數組長度 // 2  // 中間位置
    left = mergeSort(arr[0..mid-1])  // 遞歸排序左半
    right = mergeSort(arr[mid..n-1]) // 遞歸排序右半
    return merge(left, right)  // 合併左右有序數組

function merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  // 取較小元素
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])  // 剩餘元素加入
    result.extend(right[j:])
    return result

優缺點¶

• 時間複雜度：無論最好、最壞還是平均情況，都是 O(n log n)（分解 log n 次，每層合併 O(n)）。
• 空間複雜度：O(n)（合併時需要額外數組存儲結果）。
• 穩定性：穩定（合併時相等元素的相對順序不變）。
• 適用場景：數據量大（比如幾千到幾萬個元素）、對穩定性要求高的場景（如排序學生成績時，分數相同的按姓名排序）。

五、快速排序：高效的“分治”實戰¶

基本思想¶

快速排序是工程中最常用的高效排序算法，同樣基於分治思想，但比歸併排序更“靈活”。核心是“選基準，分兩半，遞歸排序”：選一個“基準數”，把數組分成“小於基準”和“大於基準”的兩部分，然後遞歸排序左右兩部分。

步驟（以數組 [5, 3, 8, 4, 2] 爲例）¶

1. 選基準：這裏選第一個元素 5 作爲基準數。
2. 分區：把數組分成兩部分：所有小於 5 的數在左邊，所有大於 5 的數在右邊。分區後可能得到 [3, 4, 2, 5, 8]（基準數 5 已在最終位置）。
3. 遞歸排序：對左邊 [3, 4, 2] 和右邊 [8] 重複上述過程：
   - 排序 [3, 4, 2]：選基準 3，分區得 [2, 3, 4]；
   - 排序 [8]：單個元素已有序。
4. 合併：最終數組爲 [2, 3, 4, 5, 8]。

分區過程（更詳細）¶

分區是快速排序的關鍵，常用方法是“雙指針法”：
- 左指針 i 從數組左邊開始，右指針 j 從數組右邊開始；
- 先移動 i 找到第一個大於基準的元素，再移動 j 找到第一個小於基準的元素，交換 i 和 j 位置；
- 重複直到 i 和 j 相遇，將基準數與相遇位置交換，得到分區結果。

以數組 [5, 3, 8, 4, 2] 爲例：
- 基準數 5，i=0，j=4；
- i 指向 5（等於基準，跳過），j 指向 2（小於基準，停止）；
- 交換 i=0 和 j=4 → [2, 3, 8, 4, 5]；
- i 右移到 1（3 < 5，跳過），j 左移到 3（4 < 5，跳過）；
- i=2（8 > 5，停止），j=3（4 < 5，停止）；
- 交換 i=2 和 j=3 → [2, 3, 4, 8, 5]；
- i=3，j=3，相遇，交換基準 5 和 i=3 位置 → [2, 3, 4, 5, 8]。

僞代碼¶

function quickSort(arr, left, right):
    if left < right:
        pivotIndex = partition(arr, left, right)  // 分區，返回基準位置
        quickSort(arr, left, pivotIndex - 1)     // 遞歸左半
        quickSort(arr, pivotIndex + 1, right)    // 遞歸右半

function partition(arr, left, right):
    pivot = arr[right]  // 選最右邊元素爲基準（更常用，避免極端情況）
    i = left - 1        // 小於基準的區域邊界
    for j from left to right-1:
        if arr[j] <= pivot:
            i += 1      // 擴展小於基準的區域
            swap(arr[i], arr[j])  // 交換到區域內
    swap(arr[i+1], arr[right])  // 基準放到最終位置
    return i + 1  // 返回基準位置

優缺點¶

• 時間複雜度：平均 O(n log n)（基準選得好時）；最壞情況 O(n²)（如數組已排序，且選第一個元素爲基準，此時分區後一邊爲空，另一邊 O(n) 長度，遞歸 log n 次）。
• 空間複雜度：O(log n)~O(n)（遞歸棧空間，平均 log n，最壞 n）。
• 穩定性：不穩定（相等元素可能被分到不同區域，相對順序改變）。
• 適用場景：大規模數據（如百萬級元素）、工程中最常用（如 Java 的 Arrays.sort() 對基本類型用快速排序）。

六、排序算法對比總結¶

七、初學者學習建議¶

1. 先理解思想：不要死記步驟，先明白“插入排序如何構建有序序列”“快速排序如何分治”。
2. 從簡單到複雜：先掌握插入、冒泡排序的直觀邏輯，再理解歸併排序的“分治”，最後攻克快速排序的“分區”。
3. 動手模擬：用紙上筆寫、或在代碼編輯器中運行小例子（比如數組 [3,1,4,2]），跟蹤每個算法的執行過程。
4. 關注核心差異：比如歸併排序的“合併”是關鍵，快速排序的“分區”是核心，這些是區別於其他算法的本質。

排序算法是算法的“基石”，掌握它們不僅能解決實際問題，更能培養邏輯思維和分治思想，爲後續學習更復雜的算法（如堆排序、基數排序）打下基礎。

小練習：嘗試用插入排序、快速排序分別排序數組 [7, 2, 6, 1, 8]，觀察每一步的變化！