【演算法】Java 實作選擇排序法（Selection Sort）

日期：


一、概述

選擇排序法是最簡單的排序方式之一。以遞增排序為例，做法是從一堆未排序的資料中，直接指定最小值與第一項交換。接著再將範圍縮小為從第二項到最後一項，指定下一個最小值與第二項交換。反覆操作後，整堆資料就排序完成了。

 二、排序過程

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

在第一回合，範圍是從第一項到最後一項，其中最小值為1。經過交換後，最小值已經已經移動到第一個位置。

在第二回合，範圍縮小為第二項到最後一項，該範圍的最小值為3。於是將它與該範圍的第一項，也就是整串資料的第二項進行交換。此時第二小的資料移動到第二個位置。

依此類推，在第四回合結束後，範圍變為只有第五項。由於它就是最大值，因此排序結束。


三、程式實作

選擇排序法的實作並不複雜。由於它有交換元素和找出最小值的動作，我們先分別準備對應的程式碼。

private static void swap(int[] array, int index1, int index2) {
    int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

找出最小值元素的位置的做法，是先假設第一個元素為最小值。接著往後面尋找，若有更小值的話，再將新的位置記錄起來。當全部的元素都走過，結果也就出來了。

private static int indexOfMin(int[] array, int startIndex) {
    int result = startIndex;
    for (int i = startIndex + 1; i < array.length; i++) {
        if (array[i] < array[result]) {
            result = i;
        }
    }

    return result;
}

接著開始撰寫排序程式。我們使用 for 迴圈來執行每個回合的排序，其中 startIndex 變數代表未排序元素的起始位置。而要執行的回合數，則是元素數量減一，因為當未排序元素的數量超過一個時，才有進行排序的必要。

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

在迴圈內部，每回合都先從未排序元素的位置範圍找出最小值，再與該範圍的第一個元素做交換即可。

public static void sort(int[] data) {
    for (int startIndex = 0; startIndex < data.length - 1; startIndex++) {
        int indexOfMin = indexOfMin(data, startIndex);
        swap(data, startIndex, indexOfMin);
    }
}

以下為選擇排序法的完整程式碼
https://gist.github.com/ntub46010/efd083762b0c5d34d7eb2b7f4f638a6c


四、時間複雜度

 從第二節的示意圖中，我們得知5個元素需要4個回合的排序過程。在尋找最小值的過程中，第一回合比較5次、第二回合比較4次，直到到四回合比較2次。總比較次數為 5 + 4 + 3 + 2 = 14 次。
我們歸納出，n個元素的總比較次數為 n + (n - 1) + ... + 2 次。根據數學上等差級數的公式，計算得

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

因此選擇排序法的時間複雜度為 O(n²)。


 五、不穩定排序

假設數值資料中有相同的值，在排序時可能會有較小的數值與那些相同元素的其中一個交換的情況，這時就會導致它們的相對位置發生改變。如果在後續的排序過程中，都沒有再交換回來，最後結果將失去穩定。

比方說下圖中的原始資料包含三個「5」，我們以編號區別它們，則排序過程如下。

由於最後各個「5」的相對位置改變了，因此選擇排序法是不穩定排序。

留言

張貼留言