寫在前面：博主是一只經過實戰開發歷練后投身培訓事業的“小山豬”，昵稱取自影片片《獅子王》中的“彭彭”，總是以樂觀、積極的心態對待周邊的事物，本人的技術路線從Java全堆疊工程師一路奔向大資料開發、資料挖掘領域，如今終有小成，愿將昔日所獲與大家交流一二，希望對學習路上的你有所助益，同時，博主也想通過此次嘗試打造一個完善的技術圖書館，任何與文章技術點有關的例外、錯誤、注意事項均會在末尾列出，歡迎大家通過各種方式提供素材，

• 對于文章中出現的任何錯誤請大家批評指出，一定及時修改，
• 有任何想要討論和學習的問題可聯系我：zhuyc@vip.163.com，
• 發布文章的風格因專欄而異，均自成體系，不足之處請大家指正，

插入排序 - 直接插入排序

本文關鍵字：演算法導論、插入排序、直接插入排序、演算法實踐

一、什么是演算法

本專欄為《手撕演算法》欄目的子專欄：《演算法導論》，會講述一些經典演算法，并進行分析，在此之前我們要先了解什么是演算法，能夠解決什么樣的問題，

1. 演算法的定義

以下為經典教材《Introduction.to.Algorithms》開篇中的內容，

Informally, an algorithm is any well-de?ned computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

可以看到，任何被明確定義的計算程序都可以稱作演算法，它將某個值或一組值作為輸入，并產生某個值或一組值作為輸出，所以演算法可以被稱作將輸入轉為輸出的一系列的計算步驟，
這樣的概括是比較標準和抽象的，其實說白了就是步驟明確的解決問題的方法，由于是在計算機中執行，所以通常先用偽代碼來表示，清晰的表達出思路和步驟，這樣在真正執行的時候，就可以使用不同的語言來實作出相同的效果，
概括的說，演算法就是解決問題的工具，在描述一個演算法時，我們關注的是輸入與輸出，也就是說只要把原始資料和結果資料描述清楚了，那么演算法所做的事情也就清楚了，我們在設計一個演算法時也是需要先明確我們有什么和我們要什么，這一點相信大家在后面的文章中會慢慢體會到，

2. 補充的概念

• 資料結構

演算法經常會和資料結構一起出現，這是因為對于同一個問題（如：排序），使用不同的資料結構來存盤資料，對應的演算法可能千差萬別，所以在整個學習程序中，也會涉及到各種資料結構的使用，
常見的資料結構包括：陣列、堆、堆疊、佇列、鏈表、樹等等，

• 演算法的效率

在一個演算法設計完成后，還需要對演算法的執行情況做一個評估，一個好的演算法，可以大幅度的節省運行的資源消耗和時間，在進行評估時不需要太具體，畢竟資料量是不確定的，通常是以資料量為基準來確定一個量級，通常會使用到時間復雜度和空間復雜度這兩個概念，

• 時間復雜度

通常把演算法中的基本操作重復執行的頻度稱為演算法的時間復雜度，演算法中的基本操作一般是指演算法中最深層回圈內的陳述句（賦值、判斷、四則運算等基礎操作），我們可以把時間頻度記為T(n)，它與演算法中陳述句的執行次數成正比，其中的n被稱為問題的規模，大多數情況下為輸入的資料量，
對于每一段代碼，都可以轉化為常數或與n相關的函式運算式，記做f(n)，如果我們把每一段代碼的花費的時間加起來就能夠得到一個刻畫時間復雜度的運算式，在合并后保留量級最大的部分即可確定時間復雜度，記做O(f(n))，其中的O就是代表數量級，
常見的時間復雜度有（由低到高）：O(1)、O( log ? 2 n \log _{2} n log2?n)、O(n)、O( n log ? 2 n n\log _{2} n nlog2?n)、O( n 2 n^{2} n2)、O( n 3 n^{3} n3)、O( 2 n 2^{n} 2n)、O(n!)，

• 空間復雜度

程式從開始執行到結束所需要的記憶體容量，也就是整個程序中最大需要占用多少的空間，為了評估演算法本身，輸入資料所占用的空間不會考慮，通常更關注演算法運行時需要額外定義多少臨時變數或多少存盤結構，如：如果需要借助一個臨時變數來進行兩個元素的交換，則空間復雜度為O(1)，

• 偽代碼約定

偽代碼是用來描述演算法執行的步驟，不會具體到某一種語言，為了表達清晰和標準化，會有一些約定的含義：
縮進：表示塊結構，如回圈結構或選擇結構，使用縮進來表示這一部分都在該結構中，
回圈計數器：對于回圈結構，在回圈終止時，計數器的值應該為第一個超出界限的值，
to：表示回圈計數器的值增加，
downto：表示回圈計數器的值減少，
by：回圈計數器的值默認變化量為1，當大于1時可以使用by，
變數默認是區域定義的，
陣列元素訪問：通過"陣列名[下標]"形式，在偽代碼中，下標從1開始（"A[1]“代表陣列A的第一個元素），
子陣列：使用”…"來代表陣列中的一個范圍，如"A[i…j]"代表從第i個到第j個元素組成的子陣列，
物件與屬性：復合的資料會被組織成物件，如鏈表包含后繼（next）和存盤的資料（data）,使用“物件名 + 點 + 屬性名”，
特殊值NIL：表示指標不指向任何物件，如二叉樹節點無子孩子可認為左右子節點資訊為NIL，
return：回傳到呼叫程序的呼叫點，在偽代碼中允許回傳多個值，
and和or：與運算和或運算默認短路，即如果已經能夠確定運算式結果時，其他條件不會去判斷或執行，

二、插入排序

1. 插入排序介紹

插入排序的基本思路是每次插入一個元素，每一趟完成對一個待排元素的放置，直到全部插入完成，

• 直接插入排序

直接插入排序是一種最簡單的排序方法，程序就是將每個待排元素逐個插入到已經排好的有序序列中，

• 折半插入排序

由于在插入排序的程序中，已經生成了一個（排好的元素組成的）有序數列，所以在插入待排元素時可以使用折半查找的方式更快速的確定新元素的位置，當元素個數較多時，折半插入排序優于直接插入排序，

• 希爾排序

希爾排序可以看做是分組插入的排序方法，把全部元素分成幾組（等距元素分到一組），在每一組內進行直接插入排序，然后繼續減少間距，形成新的分組，進行排序，直到間距為1時停止，

2. 直接插入排序

• 輸入

n個數的序列，通常直接存放在陣列中，可能是任何順序，

• 輸出

輸入序列的一個新排列，滿足從小到大的順序（默認討論升序，簡單的修改就可以實作降序排列），

• 演算法說明

每次從原有資料中取出一個數，插入到之前已經排好的序列中，直到所有的數全部取完，那么新的有序排列也就完成了，
通俗一點的解釋就是好比我們在打撲克抓牌，所有的牌扣在桌面上，我們一張一張的抓，抓起一張就在手里把它排好，那么等我們把所有的牌都抓起來之后，手里的牌也都是有序的了，

• 演算法流程

對于計算機來說，我們必須要詳細的告訴它如何比較大小，以及如何確定位置，畢竟它不能像我們一樣，“一眼”就看出位置，試想一下，當資料量比較多的時候，我們也是需要一個一個的看過來，然后才能確定新插入元素的位置，整個程序如下：

1. 第一個元素：放在第一個位置，直接排好
2. 第二個元素：與第一個元素比較，如果更大，放在第二個位置，如果更小，放在第一個位置
3. 第三個元素：順次從后向前比較，如果更小，將已排好元素向后串位，最后插入第三個元素
4. 剩余其他元素：順次從后向前比較，如果更小，將已排好元素向后串位，直到找到合適的位置插入
5. 如果待排元素是已排好的元素中最大的，只需要比較一次，然后直接追加到已排好的序列后面

3. 偽代碼

直接插入排序是一個比較好理解的演算法，大家直接用抓牌就可以完美刻畫：每次摸起一張牌，從右至左（從大到小）的與手中的牌比較，如果摸起來的這張是手牌里最大的，就直接放在最右邊，如果不是最大的，就順次滑過比它大的牌（相當于串位），直到遇見一個比剛摸起這張牌小的手牌，插入到這張牌的后面，
按照這樣的步驟重復操作，當所有的牌都被抓完時，手里的牌就都是有序的了，理解了演算法的思路后，我們用偽代碼來進行表示：

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

初始計數器為2，代表第一個元素默認排好，從第二個元素開始操作，直到最后一個元素，
每次用key記錄新操作的元素，i的初始值代表當前操作元素的前一個元素，也就是第一個要與之比較的元素，
while回圈為內層回圈，作用是在已排好的元素中找到合適的位置，來將key插入，
如果進入到回圈體中執行，代表key相對較小，還要再向前尋找，同時，與之比對的元素要向后串位，因為此時可以確定，key一定在這個元素的前面，在進入下一次回圈時，使用再前面一位的元素進行比對，
for回圈的最后一行是將key插入到對應的位置，外層回圈結束（每次回圈插入一個數），

三、演算法實踐

1. 演算法實作

• 輸入資料（input）：11，34，20，10，12，35，41，32，43，14
• java源代碼

這里需要注意源代碼與偽代碼的區別，請查看文章開頭補充的概念部分，這里不做過多說明，

public class DirectInsert {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 陣列下標從0開始，j初始為1，指向第二個元素
        for (int j = 1;j < a.length;j++){
            // 使用key記錄當前元素的值
            int key = a[j];
            // 初始化i，為j的前一個元素
            int i = j - 1;
            // while回圈作用：在已經排好的有序數列中確定key的位置，并串出對應的位置
            while(i > 0 && a[i] > key){
                // 串位覆寫，不需要使用交換，值已經被記錄在key中
                a[i + 1] = a[i];
                // 逐漸前移
                i = i - 1;
            }
            // 將待排元素放在對應的位置
            a[i + 1] = key;
        }
        // 查看排序結果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

}

• 執行效果

• 輸出資料（output）：11，10，12，14，20，32 ，34，35，41，43

2. 時間復雜度

• 最壞的情況

最壞的情況就是指每一行代碼都被執行了，回圈也是被完全拉滿的情況，一次都沒有少，確實很充實很悲催了，
對于直接插入排序來說，如果輸入的元素剛好是反向有序的，那么每次取出一個元素，都要和已經排好的每一個元素進行比較，直到比較到第一個元素，然后把自己放在最前面，沒辦法，每次拿到的都是比之前小的元素，好氣哦，
在這種情況下，內層while回圈中的代碼一共執行了 ∑ i = 1 n ? 1 i = n ( n ? 1 ) 2 = O ( n 2 ) \sum_{i=1}^{n-1} i=\frac{n(n-1)}{2}=O\left(n^{2}\right) ∑i=1n?1?i=2n(n?1)?=O(n2)，其中n為輸入的資料個數，
在計算時間復雜度時，我們只關心最后的量級就好，比如for回圈中代碼以及while回圈中的代碼都有多行，最后的結果一定比 n 2 n^{2} n2大，但都是屬于O( n 2 n^{2} n2)，

• 最好的情況

最好的情況就是指能不被執行的步驟都沒有被執行，來的資料剛剛好，并且每個資料都是這樣，簡直就是天選之人，
對于直接插入排序來說，如果輸入的元素已經是正向有序的，那么每次取出一個元素，在和已經排好的序列中的最后一個元素比較之后，就可以直接放到后面，回圈都不用進，因為已經找到了它應該在的位置，
在這種情況下，內層的while回圈可以只看成一個判斷陳述句了，嗯，就是這樣，所以代碼執行的次數主要看外層for回圈就好了，一共是n-1次，屬于O(n)，

• 平均情況

綜合兩種情況，插入排序的時間復雜度為O( n 2 n^{2} n2)，有關于平均時間復雜度的計算大家可以自己去了解一下，

3. 空間復雜度

除計數器以外，演算法執行程序中需要使用臨時變數key來記錄一下當前元素的值，除此之外的其他操作都可以在原資料結構（陣列）上完成，所以空間復雜度為O(1)，