插入排序與冒泡排序：Java 實現與核心邏輯解析

插入排序與冒泡排序：Java 實現與核心邏輯解析

排序演算法是演算法入門的必修課。本文以插入排序為主，輔以冒泡排序對比，通過代碼實現與圖解剖析其核心邏輯、時間複雜度與適用場景。

一、插入排序——像整理撲克牌一樣思考

1.1 核心思想

將數組分為已排序區間與未排序區間。初始時已排序區間僅含首元素。每輪從未排序區間取出首個元素，在已排序區間中從右向左比較，找到插入位置並將較大元素右移，最後插入該元素。重複直到未排序區間為空。

1.2 代碼實現 (Java)

public class InsertSort {

    public InsertSort(int[] a) {
        int length = a.length;
        // 外層循環：遍歷無序區間 [1, length-1]
        for (int j = 1; j <= length - 1; j++) {
            int i = j - 1;           // 有序區間末尾索引
            int temp = a[j];         // 待插入元素（備份，避免覆蓋）
            // 內層循環：在有序區間 [0, i] 中從右向左尋找插入位置
            while (i >= 0 && a[i] > temp) {
                a[i + 1] = a[i];     // 較大元素右移
                i--;
            }
            a[i + 1] = temp;         // 插入空位
        }
    }

    public static void main(String[] args) {
        int[] a = {6, 8, 9, 43, 89, 5, 7, 3};
        new InsertSort(a);
        for (int n : a) {
            System.out.println(n);
        }
    }
}

1.3 關鍵細節解析

• 邊界條件 i >= 0：防止索引越界，原代碼用 if (i < 0) break; 等效但不如循環條件直觀。
• 備份變量 temp：因右移操作會覆蓋原位置值，必須先保存待插入元素。
• 原地排序：空間複雜度 O(1)，無需額外數組。

1.4 執行流程演示 (以數組 {6, 8, 9, 43, 89, 5, 7, 3} 為例)

二、冒泡排序——輕元素「冒泡」到頂端

2.1 核心思想

重複遍歷數組，比較相鄰元素，若逆序則交換。每輪最大元素會「沉底」到末尾，或視角轉換：最小元素像氣泡一樣「冒」到開頭。雙層循環，外層控制輪數，內層做比較交換。

2.2 代碼實現

public class BubbleSort {
    public static void sort(int[] a) {
        int n = a.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // 每輪將最大元素推到 n-1-i 位置
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 本輪無交換，說明已有序，提前結束
        }
    }
}

三、兩大排序深度對比

四、實戰選型建議

• 數據量 < 50 且近乎有序：插入排序性能極佳，甚至優於 O(n log n) 演算法（因常數項小）。
• 通用大規模排序：請直接使用 Arrays.sort() (雙軸快排) 或 Collections.sort() (TimSort)，不可手寫 O(n²) 排序。
• 面試考點：掌握插入排序的「哨兵優化」、「二分查找插入位置 (二分插入排序)」、以及希爾排序作為其改進版本。

五、總結

插入排序以「人類直覺整理撲克牌」的邏輯實現了原地穩定排序，代碼簡潔且對近乎有序數據極其敏感。冒泡排序雖同屬 O(n²) 但交換開銷大，工程上極少直接使用。理解兩者本質差異，有助於建立演算法分析的基本功——關注數據移動與比較次數的權衡。