Java 直接插入排序算法完整實現與泛型優化

算法原理

直接插入排序將數組分為「已排序區」與「未排序區」，初始已排序區僅含首元素。每次從未排序區取首元素，在已排序區從右向左掃描，將大於該元素的值右移，騰出空位插入，時間複雜度 O(n²)，穩定排序。

代碼架構

1. 交換工具類

public class Swapper {
    public static > void swap(int i, int j, T[] array) {
        T tmp = array[i]; array[i] = array[j]; array[j] = tmp;
    }
    public static void swap(int i, int j, int[] array) { ... }
}

2. 插入排序核心類

• 單例模式 InsertionSortord.getInstance()
• 提供 doSort(int...) 基礎類型版與 doSortT(T[]) 泛型版
• 使用「哨兵」變量減少數組訪問，vacancy 記錄空位索引

核心邏輯片段

for (int i = 1; i < length; i++) {
    if (array[i] < array[i-1]) {
        int sentry = array[i];
        int vacancy = i;
        for (int j = i-1; j >= 0; j--) {
            if (array[j] > sentry) {
                array[j+1] = array[j];
                vacancy = j;
            }
        }
        array[vacancy] = sentry;
    }
}

3. 測試類

int[] arr = {3,5,4,2,6};
insertSort.doSort(arr);      // 基礎類型
Integer[] arr2 = {3,5,4,2,6};
insertSort.doSortT(arr2);    // 泛型

性能特徵與適用場景

優化方向

• 二分查找插入位置 → 折半插入排序（比較次數降為 O(n log n)，移動次數不變）
• 希爾排序：分組插入，大幅減少移動操作
• 小數組閾值切換：快排/歸併排序中小分區改用插入排序

1. 上一篇文章： Java 調用百度 IP 定位 API 獲取地理位置實戰
2. 下一篇文章： Java 圖片裁剪與儲存完整實作教學

Java 程式設計入門

Java 動態代理：從原理到實戰的完整指南

代理模式核心思想 代理 為委託類（被代理類）提供替身，兩大價

Java 發送郵件完整教學：JavaMail API、簡單郵件、HTML 郵件、附件與 SMTP 認證實作

Java 發送郵件完整實作指南 使用 Java 應用程式發送

Java EE 5 重塑企業級開發：從 J2EE 到 Java EE 的範式轉移

前言：不只是改名，更是重新定義 Sun 將 J2EE 1.5

JVM 深度解析：架構、類載入與執行引擎核心原理

Java 虛擬機（JVM）是 Java 跨平台的基石，理解其