普林斯頓大學算法公開課筆記——插入排序

@(算法)[排序, Algorithms-part1插入排序]

插入排序(Insertion Sort)的基本思想是：每次将一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子檔案中的适當位置，直到全部記錄插入完成為止。——極客學院

算法描述

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大于新元素，将該元素移到下一位置
4. 重複步驟 3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到該位置後
6. 重複步驟 2~5

複雜度分析

1. 時間複雜度：1/4 N^2的交換次數和比較次數

• 在最壞情況下，數組完全逆序，插入第2個元素時要考察前1個元素，插入第3個元素時，要考慮前2個元素，……，插入第N個元素，要考慮前 N - 1 個元素。是以，最壞情況下的比較次數是 1 + 2 + 3 + ... + (N - 1)，等差數列求和，結果為 N^2 / 2，是以最壞情況下的複雜度為 O(N^2)。
• 最好情況下，數組已經是有序的，每插入一個元素，隻需要考查前一個元素，是以最好情況下，時間是線性的，時間複雜度為O(N)。
• 插入排序的速度大約是選擇排序的兩倍

排序算法的穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序後的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

1. 空間複雜度分析

   算法所需的輔助空間是一個監視哨，輔助空間複雜度 S(n)=O(1)。是一個就地排序。

2. 直接插入排序的穩定性

   直接插入排序是穩定的排序方法。

執行個體分析

現有一組數組 arr = [5, 6, 3, 1, 8, 7, 2, 4]，共有八個記錄，排序過程如下：

[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘
[5, 6]   3   1   8   7   2   4
↑        │
└────────┘
[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘
[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘
[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘
[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘
[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘
 
[1, 2, 3, 4, 5, 6, 7, 8]
           

源代碼

public class Insertion
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        for(int i=1; i<N; i++)
            for(int j=i; j>0;j--)
                if(less(a[j],a[j-1]))
                    exch(a,j,j-1)
                else break;
    }
    private static boolean less(Comparable v, Comparable w)
    {
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a, int i, int j)
    {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
}
           

參考文獻

常見排序算法 - 插入排序 (Insertion Sort) 直接插入排序