討厭算法的程序員系列入口

什么是算法

在說插入排序之前，我們了解下《算法導(dǎo)論》對算法的從兩種不同角度的定義。

一般性解釋：

算法是定義良好的計算過程，它取一個或一組值作為輸入，并產(chǎn)生出一個或一組值作為輸出。

基于應(yīng)用的解釋：

算法是一種工具，用來解決一個具有良好規(guī)格說明的計算問題。該問題的描述可以用通用的語言，來規(guī)定所需的輸入/輸出關(guān)系。與之對應(yīng)的算法則描述了一個特定的計算過程，用于實現(xiàn)這一輸入/輸出關(guān)系。

后一種解釋在告訴我們，我們不必對于每個問題都去重新設(shè)計、證明和實現(xiàn)算法，而是有能力將實際問題轉(zhuǎn)換成已知算法問題，然后選取合適的解法。而這種能力就是學(xué)習(xí)算法的目的所在。這要求我們不僅要積累算法知識，還要在更高的抽象層次上理解算法的方法論。

排序問題的形式定義

排序問題是算法要解決的一個基本問題。它的形式化定義如下：

輸入：n個數(shù)的一個序列[a₁, a₂, ..., a_n]。

輸出：輸出序列的一個排列[a₁', a₂', ..., a_n'], 滿足a₁' ≤ a₂' ≤ ... ≤ a_n'。

插入排序算法

插入排序算法，對于少量元素的排序問題，是一個有效的算法。

經(jīng)典應(yīng)用

撲克

即便是玩過撲克牌的小孩子，其實都對插入排序算法了然于胸。

• 摸牌之前，所有將會被你摸到的牌，此時是一種亂序的狀態(tài)。
• 你開始摸牌，并將新摸到的牌插入到合適的位置，以保證你手中的牌總是有序的。
• 直到摸到最后一張，將其插入到合適的位置，此時你手中所有的牌就已經(jīng)排好序了。

算法的抽象表達

想讓計算機聽懂上述的算法，需要將其進行翻譯。

INSERTION-SORT(A)
1 for j = 2 to A.length
2   key = A[j]
3   // Insert A[j] into the sorted sequence A[1..j-1].
4   i = j - 1
5   while i > 0 and A[i] > key
6       A[i + 1] = A[i]
7       i = i - 1
8   A[i + 1] = key

原著中的偽碼無可挑剔，就沿用了。做一些說明：

• 算法名稱INSERT-SORT；
• A是一個長度為n的要排序的數(shù)組，用A.length表示n；
• 把待排序數(shù)組A邏輯上分為兩個數(shù)組，排好序的（手中的牌），未排序的（桌上待摸的牌）；
• 排好序的數(shù)組起始只有一個元素，就是原數(shù)組A的第一個元素（摸出的第一張牌無需排序），循環(huán)變量用i表示；
• 未排序的數(shù)組起始，從原數(shù)組A的第二個元素一直到最后一個元素，所以外層的遍歷是“2 to A.length”，循環(huán)變量用j表示；
• 外層遍歷過程中，每個當(dāng)前元素A[j]都暫存至key變量中；
• key要加入排序好的數(shù)組，會從該排序好數(shù)組的最末i(j-1)開始進行比較，如果A[i]大于key，A[i]移動到A[i+1]，i自減，繼續(xù)與key比較，如果此時i ≤ 0 或者 A[i] ≤ key，循環(huán)條件不成立跳出，將key存入A[i+1]。

算法工作例子

插入算法如何工作

說明：

• (a)~(e)是循環(huán)迭代，(f)是最終排好的數(shù)組；
• 數(shù)組上方是數(shù)組的下標；
• 黑色塊表示每次外層迭代，待插入左側(cè)數(shù)組的數(shù)A[j]；
• 灰色塊表示參與和A[j]比較的數(shù)；
• 黃色箭頭是偽碼第6行表達的移動；
• 藍色大箭頭是偽碼第8行表達的移動；

Java實現(xiàn)

public class InsertionSort {
    public static void sortInASC(int[] numbers){
        for(int j = 1; j < numbers.length; j++){
            int key = numbers[j];
            int i = j - 1;
            while(i >= 0 && numbers[i] > key){
                numbers[i + 1] = numbers[i];
                i = i - 1;
            }
            numbers[i + 1] = key;
        }
    }
}

InsertSort.java下載。

上一篇 0 前言
下一篇 2 證明算法的正確性

共享協(xié)議：署名-非商業(yè)性使用-禁止演繹（CC BY-NC-ND 3.0 CN）
轉(zhuǎn)載請注明：作者黑猿大叔（簡書）