介紹

直接插入排序是一種簡單直觀的排序算法，適用于小規模數據或基本有序的數據集。其核心思想是構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

原理

我們以下面這組數據為例

在開始排序前我們先了解直接插入排序的精髓

我們在打撲克時，習慣將手牌排成有序狀態。當我要為J排序時，我習慣把J拿出來，此時J的位置相當于空出來了，如果J的前面是K，那我把J插入到K的前面。這個過程相當于讓K后移到J起初的位置，再把J插入到空缺位置。

所以，直接插入排序的精髓在我看來就是騰出一個空位置。

有了這個認識我們現在來嘗試給數據排序：

–我定義出 i指針 和 j指針，i指針向后移動，j指針始終在 i指針的前一個位置

–利用"空位置"思想，把44取出，由變量tmp保存其數值。此時就相當于出現一個空位

–比較 j 和 j+1(其實就是i)，如果 j>j+1，就將 j挪到 j+1的位置。隨后數據會被分為有序區和無序區

–上面那個例子不能體現移動的過程，來看下面這個

tmp < 44，此時應該讓44后移

44移動后，“空缺”相當于出現在原本是44的位置。在移動的過程中，我們不去改變 i的值，所有控制都通過 j實現，j需要跟著往前移動，直到 j走出數組。

–我們再來看一次移動，后續邏輯都是相似的

我們插入5時，排序的過程如下圖所示

–總結這個過程：
將待排序數據分為已排序和未排序兩部分。初始時已排序部分僅包含第一個元素，未排序部分包含剩余元素。從未排序部分取出第一個元素，與已排序部分的元素從后向前依次比較，找到合適的位置插入。

代碼實現

void insertionSort(int arr[], int n)
{if (n <= 1) return; // 處理空數組或只有一個元素的情況int i, j;for (i = 1; i < n; i++){if (arr[i] < arr[i - 1]){int tmp = arr[i];for (j = i - 1; j >= 0 && tmp < arr[j]; j--){arr[j + 1] = arr[j];}arr[j + 1] = tmp;}}
}

分析

最好情況：數組已經是有序的，時間復雜度為O(N)，僅需遍歷一次
最壞情況：數組完全逆序，時間復雜度O(N^2)，i和j都要遍歷