在《資料結構》系列的文章中, 我們通過向量 (Vector) 已經介紹過如何在一個連續的陣列中插入若干個物件. 現在想像一個序列, 如果給定的序列是有序的, 而且每一次的插入都插入到對應的位置, 使得插入後的序列仍然有序, 那麼無論進行多少次的插入, 始終可以保持序列有序. 建立在這樣的思想之上, 於是有了插入排序

首先, 我們希望保持排序的穩定性, 於是我們不考慮如果在序列中搜尋成功時就立馬將物件插入. 對於相同的元素, 即使相等, 也要等到找到下一個比它更大的元素之後, 再在對應的位置插入. 這就使得在相等的元素之中, 最後插入的總是排列在最後, 從而保證了這個排序演算法的穩定性

現在, 我們考慮某一給定的序列. 一般來說, 我們針對某一序列的排序, 都是原地重排, 而並不是重新配置一塊新的空間. 因此, 我們需要考慮, 如何在給定的序列上使用插入排序法進行原地重排, 而不破壞序列中的元素

當給定的序列中沒有元素或著只有一個元素的時候, 這個序列就是有序的, 此時這個序列不需要進行排序. 接下來, 元素單個給出, 每一個元素通過比較之後, 都插入到對應的位置, 最終得到一個有序的序列 :

void insertion_sort(int arr[], int size) {

    for(auto i {1}; i < size; ++i) {

        auto j {i - 1};

        auto value {arr[i]};

        for(; j >= 0 and value < arr[j]; --j) {

            arr[j + 1] = arr[j];

        }

        arr[j + 1] = value;

    }

}

程式由兩個 for 迴圈組成. 第一個迴圈從 1 開始, 這是因為沒有元素的陣列或著只有一個元素的陣列本身就是有序的. 第二個 for 迴圈裡面有兩個條件, 最重要的就是 value < arr[j]. 除了使用 value 不斷遍歷, 找到第一個比 value 小的元素之外, 還保證了排序的穩定性. 如果使用 value <= arr[j], 排序的速度也許會快一些 (排序的元素不一定都是內建型別, 有些是用戶自訂型別. 對於用戶自訂型別來說, <= 的比較可能會慢得多), 但是這無法保證排序的穩定性. 每當第二個 for 迴圈的條件成立, 那麼讓元素向後移動一個位置. 最後, 在 j + 1 處插入原來在 arr[i] 的元素即可. 由於第二個 for 迴圈結束之前, --j 陳述式運作了一次, 因此得到的位置是在插入位置之前的那一個位置

對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達, 搜尋 insertion_sort