插入排序（Insertion Sort）是一種簡單直觀的排序算法，它的核心思想類似於我們整理撲克牌時的操作：將未排序的元素逐個插入到已排序部分的正確位置，從而逐步構建整個有序數組。這種算法適合小規模數據的排序，實現起來也比較容易理解。
基本思路¶
想象你手中有一副打亂的撲克牌，你會一張一張地將牌插入到正確的位置：
1. 從第2張牌開始（默認第1張牌已排序），將當前牌記爲「待插入元素」。
2. 將待插入元素與已排序部分的牌從後往前比較：
- 如果已排序的牌比待插入元素大，就把這張已排序的牌後移一位。
- 重複此過程，直到找到一個比待插入元素小的牌，或者已經比較到最左邊。
3. 將待插入元素插入到這個位置，此時已排序部分長度增加1。
4. 重複步驟1-3，直到所有牌都插入完畢。
Java代碼實現¶
以下是使用Java實現插入排序的完整代碼，包含詳細註釋：
public class InsertionSort {
// 插入排序方法
public static void insertionSort(int[] arr) {
// 數組爲空或只有一個元素時，本身已排序，無需操作
if (arr == null || arr.length <= 1) {
return;
}
// 從第2個元素開始（索引1），逐步將元素插入到已排序部分
for (int i = 1; i < arr.length; i++) {
// 保存當前待插入的元素
int current = arr[i];
// j表示已排序部分的最後一個元素的索引，初始爲i-1
int j = i - 1;
// 比較已排序部分的元素，若比current大則後移
// 循環終止條件：j >= 0 且 arr[j] > current
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; // 將已排序元素後移一位
j--; // 繼續向前比較前一個元素
}
// 找到插入位置，將current放入arr[j+1]
arr[j + 1] = current;
}
}
// 測試方法：驗證排序是否正確
public static void main(String[] args) {
int[] arr = {5, 2, 4, 6, 1, 3};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
insertionSort(arr);
System.out.println("排序後：" + java.util.Arrays.toString(arr));
}
}
代碼執行過程解析¶
以數組 {5, 2, 4, 6, 1, 3} 爲例，逐步演示插入排序的過程：
初始數組：[5, 2, 4, 6, 1, 3]¶
第1輪（i=1，current=2）：¶
- 已排序部分：
[5] - 比較：
arr[0]=5 > 2，所以將5後移到arr[1]，j變爲-1 - 插入位置：
arr[0] = 2 - 結果：
[2, 5, 4, 6, 1, 3]
第2輪（i=2，current=4）：¶
- 已排序部分：
[2, 5] - 比較：
arr[1]=5 > 4，將5後移到arr[2]，j=0 - 比較：
arr[0]=2 <= 4，停止循環 - 插入位置：
arr[1] = 4 - 結果：
[2, 4, 5, 6, 1, 3]
第3輪（i=3，current=6）：¶
- 已排序部分：
[2, 4, 5] - 比較：
arr[2]=5 <= 6，無需移動 - 插入位置：
arr[3] = 6 - 結果：
[2, 4, 5, 6, 1, 3]（數組未變化）
第4輪（i=4，current=1）：¶
- 已排序部分：
[2, 4, 5, 6] - 比較：
arr[3]=6 > 1→ 後移6到arr[4]，j=2 - 比較：
arr[2]=5 > 1→ 後移5到arr[3]，j=1 - 比較：
arr[1]=4 > 1→ 後移4到arr[2]，j=0 - 比較：
arr[0]=2 > 1→ 後移2到arr[1]，j=-1 - 插入位置：
arr[0] = 1 - 結果：
[1, 2, 4, 5, 6, 3]
第5輪（i=5，current=3）：¶
- 已排序部分：
[1, 2, 4, 5, 6] - 比較：
arr[4]=6 > 3→ 後移6到arr[5]，j=3 - 比較：
arr[3]=5 > 3→ 後移5到arr[4]，j=2 - 比較：
arr[2]=4 > 3→ 後移4到arr[3]，j=1 - 比較：
arr[1]=2 <= 3，停止循環 - 插入位置：
arr[2] = 3 - 最終結果：
[1, 2, 3, 4, 5, 6]
算法特性總結¶
-
時間複雜度：
- 最好情況（數組已排序）：O(n)（僅需n-1次比較）
- 最壞情況（數組逆序）：O(n²)（n-1次內層循環，每次比較n次）
- 平均情況：O(n²) -
空間複雜度：O(1)（原地排序，僅需一個臨時變量保存待插入元素）
-
穩定性：穩定排序（相等元素的相對順序不會改變）
-
適用場景：適合小規模數據或幾乎有序的數據，因爲小規模數據的O(n²)影響較小。
總結¶
插入排序的核心是“逐步插入”，通過將元素與已排序部分比較並移動，最終構建有序數組。Java實現時需要注意保存待插入元素（避免覆蓋），以及正確處理邊界條件（j的終止條件）。這種算法雖然時間複雜度較高，但實現簡單，穩定性和原地性使其在小規模數據排序中表現良好。