核心思想
插入排序是一種基于元素比較的原地排序算法，其核心思想是將數組分為“已排序”和“未排序”兩部分，逐個將未排序元素插入到已排序部分的正確位置。
例如撲克牌在理牌的時候，一般會將大小王、2、A、花牌等按大小順序插入到左邊，3、4等小牌會往右邊靠，這和插入排序是同一個原理
復雜度
時間復雜度
| 場景 | 時間復雜度 | 具體說明 |
|---|---|---|
| ?最佳情況? | O(n) | 數組已完全有序，每次只需比較一次（無需移動元素） |
| ?最差情況? | O(n2) | 數組完全逆序，每個元素需比較并移動所有已排序元素（如?[5,4,3,2,1]） |
| ?平均情況? | O(n2) | 部分有序數組的插入操作需要約 n2/4 次比較和移動 |
空間復雜度
O(1)：原地排序算法，僅需固定數量的額外空間（如?key?和索引變量?j）
代碼實現（Java）
//插入排序，升序排序舉例
void insertionSort(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) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}
}
