【演算法】Java 實作插入排序法（Insertion Sort）

日期：


一、概述

插入排序法是一種類似整理撲克牌的排序方式。做法是將第一項資料視為已排序，接著從第二項資料開始，一一將其他資料插入到已排序資料中的適當位置，直到處理完畢為止。

所謂適當位置，是指小於（或等於）自己的最大資料的後一項。而插入這個動作，並非直接將該位置的資料給覆蓋掉。我們需要先把目標插入位置及後方的資料進行必要的移動，才能騰出空間，接著再放置資料。

二、排序過程

假設我們有一串數值資料：7、5、9、1、3，則排序過程如下。

在第一回合，已排序資料只有第一項的7，我們將第二項與之比較。由於沒有小於5的值，因此判斷出5應該放在7前面。此時把7往後移動一個位置，替5騰出空間後，再將其放置到第一項。

在第二回合，已排序資料包含5、7，我們將第三項的9，從第二項開始往前比較。由於遇到的第一個資料就小於自己了，因此9應該放在第二項的7後面，等同不變。

依此類推，在第四回合，已排序資料包含1、5、7、9。第五項的3在比較過程中，發現到了第一項的1才小於自己，因此3應該放在後面的第二項。於是我們需要將第二項到第四項的資料往後移動一個位置，再將3放到第二項。


三、程式實作

插入排序法包含了「尋找小於等於自己的最大資料」的動作，我們先準備對應的程式碼。由於要在已排序資料的區間內由後往前尋找，endIndex 參數就代表了該區間的最後一個位置。

private static int lastIndexOfLowerOrEqualData(int[] array, int endIndex, int value) {
    for (int i = endIndex; i >= 0; i--) {
        if (array[i] <= value) {
            return i;
        }
    }
    return -1;
}

接著開始撰寫排序程式。我們知道從第二項到最後一項資料是會被拿來插入的，於是使用 for 迴圈搭配 currentIndex 變數來取出這些陣列元素。

public static void sort(int[] data) {
    for (int currentIndex = 1; currentIndex < data.length; currentIndex++) {
        int currentValue = data[currentIndex];
        // TODO
    }
}

接著要尋找小於等於自己的最大元素的位置，藉此定位出該元素要插入到後面一項。但在放置元素前，必須將從該位置開始的已排序元素往後搬移一個位置。

public static void sort(int[] data) {
    for (int currentIndex = 1; currentIndex < data.length; currentIndex++) {
        int currentValue = data[currentIndex];
        int newIndex = lastIndexOfLowerOrEqualData(data, currentIndex - 1, currentValue) + 1;

        for (int i = currentIndex; i > newIndex; i--) {
            data[i] = data[i - 1];
        }

        data[newIndex] = currentValue;
    }
}

搬移完成後，原先 currentIndex 位置的元素會變成已排序元素的最後一個元素。而原先 newIndex 位置的元素被往後移，於是我們可以在該處放置 currentValue 的值。

以下為插入排序法的完整程式碼
https://gist.github.com/ntub46010/fb8b88453ec7f1a2a152c8005bf7398e


四、時間複雜度

從第二節的示意圖中，我們得知5個元素需要4個回合的排序過程。但每個回合尋找插入位置的元素比較次數及搬移次數卻不一定。最佳情況是遇到的第一個元素就小於等於自己，且不必搬移。最差情況是在已排序元素中並未找到，意即要插入到第一項，並搬移 currentIndex 次的元素。

針對已排序好的資料進行排序是屬於最佳情況，由於每回合的元素比較次數都是1次，共比較  n - 1 次，故最佳時間複雜度為 O(n)。

針對相反方向排序好的資料進行排序是屬於最差情況。第一回合比較1次、第二回合比較2次、第n回合比較n次，總比較次數為 1 + 2 + ... + (n - 1) 次。根據數學上等差級數的公式，計算得

   [1 + 2 + ... + (n - 1) + n] - n
= [n(1 + n) / 2] - n
= (n² - n) / 2。

至於元素搬移次數正好與比較次數相同，故最差時間複雜度為O(n²)。


五、穩定排序

插入排序法是從未排序的元素中按照順序處理。因此相同元素的相對位置不會被影響。舉例來說，下圖中的原始資料為：1、31、5、32、2。其中包含兩個「3」，我們以編號區別它們。32的處理過程如下。

在尋找插入位置時便會遇到31，隨即插入到它的後方。程式實作上並不需要故意插入到它的後方。由於最後相對位置不變，因此插入排序法屬於穩定排序。

留言

張貼留言