忙了一段時間

上一次說完了選擇排序，那么繼續(xù)往下走，本次我們來理解插入排序算法

廢話少說，進入正題

如有誤，辛苦指正

背景介紹

（Insertion Sort），一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到的有序表中，從而一個新的、記錄數(shù)增1的有序表。在其實現(xiàn)過程使用，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找，并進行。 ---插入排序算法

核心特點

1. 默認選出待排序數(shù)組第一個元素當做一個有序的序列
2. 其次依次從待排序數(shù)組中抽取元素，依次和有序數(shù)列從后往前想比較。
3. 當發(fā)現(xiàn)前面的元素比當前準備插入的元素大/小時，有序數(shù)列元素后移一位，再次比較直到當前插入元素比當前比較的元素小/大時，比較結(jié)束，插入此位置
4. 重復步驟3即可

舉個例子

[ 1, 5, 4, 3, 6, 2, 7 ]

1、先將第一個元素1抽離出來當做一個有序數(shù)組得到兩個數(shù)組

[1]
[ 5, 4, 3, 6, 2, 7 ]

2、再抽出第一個數(shù)和有序數(shù)組相比較，即5和1比較，發(fā)現(xiàn)5大于1，那么直接將5放在1的后面即可，得到

[ 1, 5 ]
[ 4, 3, 6, 2, 7 ]

3、再次取出4和有序數(shù)組比較，4 比5小，那么5后移一位數(shù)組變成[1, 待插入, 5],再次將4和1比較，發(fā)現(xiàn)4 大于 1 那么說明此時 4 插入到1 和 5 之間即可，得到

[ 1, 4 , 5 ]
[ 3, 6, 2, 7 ]

4、依次類推...

此時，我們已經(jīng)將元素一個一個以“插入”的形式將整個數(shù)組排序完成

老規(guī)矩，理論加實踐 go！

代碼示例

1、我們創(chuàng)建一個排序方法，并接受一個參數(shù)，就是我們需要排序的數(shù)組

function insertionSort( _array ){
    
}

2、然后我們開始先獲取數(shù)組的第一個元素，并將它當做有序數(shù)組

function insertionSort( _array ){
    //取出第一個元素，并當做有序數(shù)組
    var _sortArray = [ _arr.shift() ];
}

3、根據(jù)特點中的，依次取出待排序數(shù)組中的第一個元素，和有序數(shù)組作比較，直到待排序數(shù)組元素比較完畢，如果用面向過程的思路來理解，兩個依次 一聽就是兩個循環(huán)，我們來實現(xiàn)

function insertionSort( _array ){
    //取出第一個元素，并當做有序數(shù)組
    var _sortArray = [ _array.shift() ];
    
    //依次拿待排序的數(shù)組元素和有序作比較，那么他的循環(huán)結(jié)束條件就是待排序數(shù)組都比較完了
    while( _array.length ){

        //取出待排序數(shù)組的第一個元素
        var _first = _array.shift();
        
        //依次和有序數(shù)組從后往前的元素作比較，那么第一個數(shù)的索引就是
        var _i = _sortArray.length - 1; //這里_sortArray[i]就是最后一個元素了
        
    }
}

4、下一步呢我們就要依次循環(huán)去比較了，這里要弄清楚循環(huán)結(jié)束的條件，應該是當找到和當前比較的元素更大/小的時，或者所有元素都比較完畢時（此時肯定他就是最小的了) 。
所以我們繼續(xù)實現(xiàn)

function insertionSort( _array ){
    //取出第一個元素，并當做有序數(shù)組
    var _sortArray = [ _array.shift() ];
    
    //依次拿待排序的數(shù)組元素和有序作比較，那么他的循環(huán)結(jié)束條件就是待排序數(shù)組都比較完了
    while( _array.length ){

        //取出待排序數(shù)組的第一個元素
        var _first = _array.shift();
        
        //依次和有序數(shù)組從后往前的元素作比較，那么第一個數(shù)的索引就是
        var _i = _sortArray.length - 1; //這里_sortArray[i]就是最后一個元素了

        //當索引大于等于0 就是還沒有比較結(jié)束  而且  當前元素 仍然小于 比較元素時，循環(huán)繼續(xù)，否則找到位置，循環(huán)退出
        while( _i >= 0 && _first < _sortArray[_i]){
            
            //既然進入循環(huán)了，就說明滿足條件，那么當前的數(shù)就往后移一位
            _sortArray[ _i + 1 ] = _sortArray[_i];

            //同時比較的索引也要左移一位
            _i--;
        }
        
        //里面的小循環(huán)結(jié)束后，當前的i + 1的位置 就是元素要插入的位置
        _sortArray[ _i + 1 ] = _first;

    }

    return _sortArray;
}

ok
插入排序?qū)崿F(xiàn)完畢，這些基礎的排序思想還是很容易理解的，多看幾遍相信大家就懂了

引申

老規(guī)矩，系列完畢后，在進行優(yōu)化相關(guān)的知識討論

狗的拜！