以下是插入排序的詳細解析，包含基礎實現、常見變體的完整代碼示例，以及各變體的對比表格：

---

一、插入排序基礎實現

原理

將元素逐個插入到已排序序列的合適位置，逐步構建有序序列。

代碼示例

public class InsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; 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; // 插入到正確位置}}
}

復雜度分析

• 時間復雜度：
  • 最壞/平均：O(n2)（逆序或隨機數據）。
  • 最好（已有序）：O(n)。
• 空間復雜度：O(1)。
• 穩定性：穩定（相同值的元素相對順序不變）。

---

二、常見變體及代碼示例

1. 優化版（減少移動次數）

改進點：通過減少元素移動的次數，優化內層循環。
適用場景：數據接近有序時效率更高。

public class OptimizedInsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;// 找到插入位置后一次性移動元素while (j >= 0 && arr[j] > key) {j--;}// 將 j+1 到 i 的元素后移一位for (int k = i; k > j + 1; k--) {arr[k] = arr[k - 1];}arr[j + 1] = key;}}
}

2. 二分插入排序

改進點：用二分查找確定插入位置，減少比較次數。
適用場景：數據規模較大時，減少比較時間。

public class BinaryInsertionSort {void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int left = 0, right = i - 1;// 二分查找插入位置while (left <= right) {int mid = (left + right) / 2;if (arr[mid] > key) {right = mid - 1;} else {left = mid + 1;}}// 移動元素并插入for (int j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}arr[left] = key;}}
}

3. 遞歸實現

改進點：用遞歸替代循環，代碼結構更清晰。
適用場景：教學或代碼風格偏好遞歸。

public class RecursiveInsertionSort {void sort(int[] arr, int n) {if (n <= 1) return;sort(arr, n - 1); // 先排序前 n-1 個元素int key = arr[n - 1];int j = n - 2;// 將比 key 大的元素后移while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}

---

三、變體對比表格

變體名稱	時間復雜度	空間復雜度	穩定性	主要特點	適用場景
基礎插入排序	O(n2)（平均/最壞）， O(n)（最好）	O(1)	穩定	簡單易實現，適合小規模或部分有序數據	小數據或接近有序的場景
優化版（減少移動次數）	O(n2)（平均/最壞）， O(n)（最好）	O(1)	穩定	減少內層循環的移動次數	數據接近有序時效率提升
二分插入排序	O(n2)（平均/最壞）， O(n log n)（比較次數）	O(1)	穩定	用二分查找減少比較次數	數據規模較大時減少比較時間
遞歸實現	O(n2)（所有情況）	O(n)	穩定	遞歸替代循環，代碼結構清晰	教學或代碼風格偏好遞歸的場景

---

四、關鍵選擇原則

1. 基礎場景：優先使用基礎實現，因其簡單且適用于小規模數據。
2. 優化需求：
   • 接近有序數據：優化版（減少移動次數）可提升效率。
   • 大規模數據：二分插入排序通過減少比較次數優化性能。
3. 代碼風格：遞歸實現適合教學或偏好函數式編程的場景，但需注意棧空間開銷。
4. 穩定性需求：所有變體均穩定，適用于需要保持元素相對順序的場景（如排序帶鍵值的記錄）。
5. 極端場景：已排序數據時，基礎實現的時間復雜度降至 O(n)，是插入排序的優勢場景。

通過選擇合適的變體，可在特定場景下優化性能或代碼可讀性，同時保持算法的穩定性。