[[427990]]

本文轉載自微信公眾號「JS每日一題」，作者灰灰。轉載本文請聯系JS每日一題公眾號。

一、是什么

插入排序(Insertion Sort)，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效、簡單的算法

其主要的實現思想是將數據按照一定的順序一個一個的插入到有序的表中，最終得到的序列就是已經排序好的數據

插入排序的工作方式像許多人排序一手撲克牌，開始時，我們的左手為空并且桌子上的牌面向下

然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置，該正確位置需要從右到左將它與已在手中的每張牌進行比較

例如一個無序數組 3、1、7、5、2、4、9、6，將其升序的結果則如下：

一開始有序表中無數據，直接插入3

從第二個數開始，插入一個元素1，然后和有序表中記錄3比較，1<3，所以插入到記錄 3 的左側

向有序表插入記錄 7 時，同有序表中記錄 3 進行比較，3<7，所以插入到記錄 3 的右側

向有序表中插入記錄 5 時，同有序表中記錄 7 進行比較，5<7，同時 5>3，所以插入到 3 和 7 中間

照此規律，依次將無序表中的記錄 4，9 和 6插入到有序表中

二、如何實現

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置

如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面

用代碼表示則如下：

function insertionSort(arr) { 
    const len = arr.length; 
    let preIndex, current; 
    for (let i = 1; i < len; i++) { 
        preIndex = i - 1; 
        current = arr[i]; 
        while(preIndex >= 0 && arr[preIndex] > current) { 
            arr[preIndex+1] = arr[preIndex]; 
            preIndex--; 
        } 
        arr[preIndex+1] = current; 
    } 
    return arr; 
} 

在插入排序中，當待排序數組是有序時，是最優的情況，只需當前數跟前一個數比較一下就可以了，這時一共需要比較N- 1次，時間復雜度為O(n)

最壞的情況是待排序數組是逆序的，此時需要比較次數最多，總次數記為：1+2+3+…+N-1，所以，插入排序最壞情況下的時間復雜度為O(n^2)

通過上面了解，可以看到插入排序是一種穩定的排序方式

三、應用場景

插入排序時間復雜度是 O(n2)，適用于數據量不大，算法穩定性要求高，且數據局部或整體有序的數列排序

參考文獻

• https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/7214992
• http://data.biancheng.net/view/65.html