開(kāi)篇

聊完選擇排序，這篇我們來(lái)聊聊插入排序。

設(shè)想下你現(xiàn)在要安排一隊(duì)人按照身高從低到高排序站立，你的排序方法很可能是一個(gè)人一個(gè)人來(lái)，將每一個(gè)人插入到當(dāng)前已經(jīng)有序的隊(duì)列中去，為了給要插入的人（元素）騰出空間，我們需要將當(dāng)前隊(duì)列中所有比待插入人長(zhǎng)得高的人向右移動(dòng)一個(gè)人的位置，以給待插入的人騰出空間。

這就叫插入排序。

正文

這次我們直接上圖來(lái)具象化展示插入排序的過(guò)程：

插入排序過(guò)程，圖源維基百科

下面我們直接上嵌套循環(huán)版本的代碼，遞歸版本的代碼且略過(guò)不寫(xiě)，還是以 Java 為例：

/**
     * @see: 插入排序的 Java 實(shí)現(xiàn)，使用快慢指針?biāo)悸?     * @param array: 待排序數(shù)組，我們采用原地排序
     */
    public static void sortInsert(int[] array){
        //外層我們先假定數(shù)組第一個(gè)元素已部分有序，
        //即第一個(gè)元素已在它該在的位置，
        //從數(shù)組第二個(gè)元素開(kāi)始遍歷，當(dāng)然數(shù)組長(zhǎng)度可能小于2
        for (int slow = 1; slow < array.length; slow ++){
            //待插入元素 array[slow]
            int insertion = array[slow];
            //內(nèi)循環(huán)遍歷，主要為確定待插入元素array[slow]的待插入位置
            int fast = slow - 1;//內(nèi)循環(huán)快指針
            for (; fast >= 0; fast --){
                if (array[fast] > insertion){
                    array[fast + 1] = array[fast];
                }else {
                    //待插入元素的待插入位置，總是從后往前看，最后一個(gè)值比它大的那個(gè)位置，
                    //值比它大的那些值整體往后移動(dòng)一個(gè)位置
                    break;
                }
            }
            //插入待插入元素，即最后一個(gè)值比它大的那個(gè)位置
            array[fast + 1] = insertion;
        }
    }

上篇聊選擇排序我們說(shuō)到其是一種運(yùn)行時(shí)間和輸入無(wú)關(guān)的算法，而插入排序是典型的運(yùn)行時(shí)間嚴(yán)重依賴(lài)輸入的算法，插入排序運(yùn)行的平均和最壞時(shí)間復(fù)雜度都是平方級(jí)別的 О(n2)，但如果待排序數(shù)組是一個(gè)已經(jīng)整體有序的數(shù)組，則只需要線性級(jí)別的時(shí)間復(fù)雜度 О(n) 即可運(yùn)行完算法。

尾巴

下篇，我們聊希爾排序。