插入排序(Insertion Sort)

介紹

插入排序是從數列最左邊開始，往右依序排序下去，在過程中，由左至右，先將最左邊的數值設定成已排序，再往右取一個未排序數值，插入已排序中的適當位置，依此類推完成排序。在最糟的情況下，數列從大排到小，每 n 回合就必須進行 n-1 次比較和對調，在第一回合需要一次，第二回合兩次….到第 n 回合發生 n - 1 次，大約等於n^2/2，所以時間複雜度跟氣泡排序還有選擇排序一樣是O(n^2)。

優點:

只需要固定數量的 O(1) 內存空間
在實踐中比大多數其他簡單的二次方算法（如選擇排序或冒泡排序）更有效

(圖片來源)

虛擬碼

為甚麼迴圈從 1 開始 ?

因為最左邊的數列一開始會被當作是已排序的

function insertion_sort (array) {
    for(j from 1 to length-1){
        key = array[j]
        i = j - 1
        while i >= 0 and array[i] > key:
            array[i + 1] = array[i]
            i = i - 1
        array[i + 1] = key
    }
}

複雜度

時間複雜度

$O(n^2)$

空間複雜度

$O(1)$

實戰

75. Sort Colors

題目說明

給定一個數組 nums，其中有 n 個對象，顏色為紅色、白色或藍色，並對它們進行排序，顏色按紅色、白色和藍色的順序排列。將使用整數 0、1 和 2 分別表示紅色、白色和藍色。必須在不使用library的排序功能的情況下解決此問題。

解法

Javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    for(let i = 1; i <= nums.length - 1; i++){
        key = nums[i];
        j = i - 1;
        while(j >= 0 && nums[j] > key){
            nums[j + 1] = nums[j];
            j = j - 1;
        }
        nums[j + 1] = key
    }
    return nums
};