java如何實插入排序算法

# Java如何實現插入排序算法

## 1. 插入排序算法概述

插入排序（Insertion Sort）是一種簡單直觀的排序算法，其基本思想是將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增1的有序表。插入排序適用于小規模數據或基本有序的數據集合。

### 1.1 算法特點
- **時間復雜度**：
  - 最優情況（已排序數組）：O(n)
  - 最壞情況（逆序數組）：O(n2)
  - 平均情況：O(n2)
- **空間復雜度**：O(1)（原地排序）
- **穩定性**：穩定排序算法

## 2. 插入排序工作原理

插入排序的工作方式類似于整理撲克牌：
1. 從第二個元素開始（假設第一個元素已排序）
2. 取出當前元素，與前面已排序的元素逐個比較
3. 找到合適位置后插入該元素
4. 重復上述過程直到數組完全排序

## 3. Java實現插入排序

### 3.1 基礎實現

```java
public class InsertionSort {
    
    public static void insertionSort(int[] arr) {
        // 從第二個元素開始遍歷
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i]; // 當前需要插入的元素
            int j = i - 1;
            
            // 將比key大的元素向后移動
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // 插入key到正確位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前: " + Arrays.toString(arr));
        
        insertionSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

3.2 優化版本（減少交換操作）

public static void optimizedInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 使用System.arraycopy優化元素移動
        while (j >= 0 && arr[j] > key) {
            j--;
        }
        if (j + 1 != i) {
            System.arraycopy(arr, j + 1, arr, j + 2, i - (j + 1));
            arr[j + 1] = key;
        }
    }
}

4. 算法分析

4.1 時間復雜度對比

4.2 與其他排序算法比較

• 比冒泡排序和選擇排序效率更高
• 在小規模數據上優于快速排序和歸并排序
• 是TimSort和希爾排序的基礎組成部分

5. 實際應用場景

5.1 適用場景

• 小規模數據排序（n < 100）
• 基本有序的數據集
• 作為更復雜算法的子過程（如快速排序的小數組處理）

5.2 不適用場景

• 大規模隨機數據（性能較差）
• 對時間復雜度要求嚴格的場景

6. 擴展實現

6.1 泛型版本實現

public static <T extends Comparable<T>> void genericInsertionSort(T[] arr) {
    for (int i = 1; i < arr.length; i++) {
        T key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j].compareTo(key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

6.2 遞歸實現

public static void recursiveInsertionSort(int[] arr, int n) {
    if (n <= 1) return;
    
    recursiveInsertionSort(arr, n - 1);
    
    int key = arr[n - 1];
    int j = n - 2;
    
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}

7. 性能測試

public static void main(String[] args) {
    // 測試10,000個隨機數排序
    int[] largeArray = new Random().ints(10000).toArray();
    
    long start = System.nanoTime();
    insertionSort(largeArray);
    long end = System.nanoTime();
    
    System.out.printf("插入排序耗時: %.2f ms%n", (end - start) / 1_000_000.0);
}

8. 總結

插入排序雖然在大數據量上效率不高，但其簡單直觀的實現方式和在小數據量上的優秀表現，使其仍然具有重要價值。理解插入排序有助于掌握更復雜的排序算法，也是學習算法設計思想的良好起點。

關鍵點總結： 1. 插入排序是穩定的原地排序算法 2. 適合小規?；蚧居行驍祿?3. Java實現僅需10行左右核心代碼 4. 可以通過減少交換操作進行優化 “`