[[427990]]

本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。

一、是什么

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

其主要的實(shí)現(xiàn)思想是將數(shù)據(jù)按照一定的順序一個(gè)一個(gè)的插入到有序的表中，最終得到的序列就是已經(jīng)排序好的數(shù)據(jù)

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

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

例如一個(gè)無序數(shù)組 3、1、7、5、2、4、9、6，將其升序的結(jié)果則如下：

一開始有序表中無數(shù)據(jù)，直接插入3

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

向有序表插入記錄 7 時(shí)，同有序表中記錄 3 進(jìn)行比較，3<7，所以插入到記錄 3 的右側(cè)

向有序表中插入記錄 5 時(shí)，同有序表中記錄 7 進(jìn)行比較，5<7，同時(shí) 5>3，所以插入到 3 和 7 中間

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

二、如何實(shí)現(xiàn)

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置

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

用代碼表示則如下：

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; 
} 

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

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

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

三、應(yīng)用場景

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

參考文獻(xiàn)

• 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