反饋

插入排序

插入排序，一般也被稱為直接插入排序。對於少量元素的排序，它是一個有效的算法^[1] 。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增1的有序表。在其實現過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，內層循環對當前元素前面有序表進行待插入位置查找，並進行移動^[2] 。

中文名: 插入排序
外文名: Insertion sort
別名: 直接插入排序

分類: 排序方法
時間複雜度: O(N^(1-2))
空間複雜度: O(1)
穩定性: 穩定

插入排序基本思想

插入排序的工作方式像許多人排序一手撲克牌。開始時，我們的左手為空並且桌子上的牌面向下。然後，我們每次從桌子上拿走一張牌並將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌^[1] 。

插入排序是指在待排序的元素中，假設前面n-1(其中n>=2)個數已經是排好順序的，現將第n個數插到前面已經排好的序列中，然後找到合適自己的位置，使得插入第n個數的這個序列也是排好順序的。按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序^[3] 。

插入排序偽代碼

用插入排序對長度為n的待排序數組A進行排序的偽代碼（在代碼中，A中元素的數目n用A.length來表示）^[1] ：

INSERTION-SORT(A)
for j=2 to A.length:
    key=A[j]
    //將A[j]插入已排序序列A[1..j-1]
    i=j-1
    while i>0 and A[i]>key
        A[i+1]= A[i]
        i=i-1
    A[i+1]=key

插入排序示例

圖示

在數組A=（5,2,4,6,1,3）上插入排序的操作。數組下標出現在長方形的上方，數組位置中存儲的值出現在長方形中。(a)~(e)第(1)~(8)行for循環的迭代。每次迭代中，黑色的長方形保存取自A[j]的關鍵字，在第5行的測試中將它與其左邊的加陰影的長方形中的值進行比較。加陰影的箭頭指出數組值在第6行向右移動一個位置，黑色的箭頭指出在第8行關鍵字被移到的地方。(f)最終排序好的數組^[1] 。

插入排序實現

下面是對數組a進行插入排序的JAVA代碼，排序後數組a按升序排列^[4] 。

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        //將a[]按升序排列
        int N=a.length;
        for (int i=1;i<N;i++)
        {
        //將a[i]插入到a[i-1]，a[i-2]，a[i-3]……之中
            for(int j=i;j>0&&(a[j].compareTo(a[j-1])<0);j--)
            {
                Comparable temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
}

插入排序時間複雜度

在插入排序中，當待排序數組是有序時，是最優的情況，只需當前數跟前一個數比較一下就可以了，這時一共需要比較N- 1次，時間複雜度為

^[3] 。

最壞的情況是待排序數組是逆序的，此時需要比較次數最多，總次數記為：1+2+3+…+N-1，所以，插入排序最壞情況下的時間複雜度為

^[3] 。

平均來説，A[1..j-1]中的一半元素小於A[j]，一半元素大於A[j]。插入排序在平均情況運行時間與最壞情況運行時間一樣，是輸入規模的二次函數^[1] 。

插入排序空間複雜度

插入排序的空間複雜度為常數階

^[5] 。

插入排序穩定性分析

如果待排序的序列中存在兩個或兩個以上具有相同關鍵詞的數據，排序後這些數據的相對次序保持不變，即它們的位置保持不變，通俗地講，就是兩個相同的數的相對順序不會發生改變，則該算法是穩定的；如果排序後，數據的相對次序發生了變化，則該算法是不穩定的。關鍵詞相同的數據元素將保持原有位置不變，所以該算法是穩定的^[5] 。