【演算法】選擇排序法 (Selection Sort)

如果大家沒有學習過任何演算法, 又想要對一個序列進行重新排序, 大家最容易想到的方法, 就是首先找到序列中最大或著最小的元素, 然後再找到次大或著次小的元素, 不斷重複上述步驟, 最後就得到了標準排列. 這種排序方法, 我們稱為選擇排序法

首先, 對於任意序列, 要想找到最大的元素, 我們可以採用順序搜尋的方式 :

int index_max(const int arr[], int size) {

    auto max {0};

    for(auto i {1}; i < size; ++i) {

        if(arr[i] > arr[max]) {

            max = i;

        }

    }

    return max;

}

接著要解決的是, 找到了這個最大的元素應該把它存在何處? 我們非常簡單地想到希望有一個額外的一個序列給予我們存儲元素的空間. 但是, 對於排序演算法來說, 通常不會給你額外的空間, 就像我們在名次排序中看到的那樣, 給定額外的空間來存儲的情況幾乎不可能出現 (而且是無用且無意義的), 通常的做法都是原地重排. 由於我們找到的是最大的元素, 因此我們可以考慮把它存儲在陣列的最後一個位置, 也就是將它和陣列的最後一個位置交換 :

交換完成之後 :

此時我們發現, 陣列的最後部分已經有序, 因此函式 index_max 呼叫時傳入的第二個引數的大小應該為 4

完成了第二次交換之後, 接下來只要簡單地重複這些步驟就可以完成排序 :

在上述交換完成之後, 就得到了有序的排列

根據上述思想, 我們實作除選擇排序法的程式碼 :

void selection_sort(int arr[], int size) {

    for(auto i {size - 1}; i > 0; --i) {

        swap(arr[index_max(arr, i + 1)], arr[i]);

    }

}

程式碼的核心思想非常簡單, 選擇出陣列中餘下元素中最大的那一個, 然後和餘下元素的最後一個進行交換. i 從最後一個位置開始, i + 1 表示陣列中還有多少元素需要被排序, i 表示餘下的最後一個位置

接下來我們需要探討選擇排序的穩定性. 函式 index_max 是從第一個往最後一個進行搜尋的, 因此即使是相同的元素, 也是排在前面的優先被找到, 但是它是被放入餘下元素中的最後一個位置, 於是穩定性就被打破了

換一種思路, 我們從前到後尋找最小的元素 (如果之後再次尋找到相同的元素, 最小元素的定位不能被改變, 否則就破壞了穩定性), 然後再將最小的元素從前至後放置. 這樣的選擇排序就是穩定的

回到原來的程式, 我們發現如果 for 迴圈沒有完成, 但是此時陣列已經有序, 然而此時 for 迴圈還會繼續下去, 所以當序列已經有序, 我們希望即時終止選擇排序. 若要實現這樣的需求, 那麼我們需要合併兩個函式, 並且使用一個布林變數檢測陣列是否有序 :

void selection_sort(int arr[], int size) {

    bool is_sorted {};

    for(auto i {size}; not is_sorted and i > 1; --i) {

        auto max {0};

        is_sorted = true;

        for(auto j {1}; j < i; ++j) {

            if(arr[j] > arr[max]) {

                max = j;

                continue;

            }

            if(is_sorted) {

                is_sorted = false;

            }

        }

        swap(arr[i - 1], arr[max]);

    }

}

在上述程式中, 多了一個 is_sorted 變數, 這個變數在內部的 for 迴圈中起作用, 如果序列是不斷增加的, 那麼每一次 arr[j] > arr[max] 這個條件回傳的結果都是 true, 否則的話, 序列就不是有序的