主題

最好懂的排序法選擇排序法(Selection sort)

魔化鬼鬼 | 2020-05-24 12:13:04 | 巴幣 2 | 人氣 684

這次來講解的排序法，是一個概念上比泡沫排序可能還要簡單一點的排序法，叫做-Selection sort，中文叫選擇排序法，說文解字，這個演算法就是以選擇為特色，什麼意思？其工作原理非常簡單，就是在一整串數字裡面搜尋最大值或最小值，將他放到陣列的最頭和最尾，下面的gif很清楚的說明原理了

不懂嗎？沒關係，我們實際操作一次：

如果我們要把陣列由小排到大

假設一個長度為8的陣列

arr[8] = {58,4,52,4,87,1,23,9}

並宣告另一個變數minValueIndex來儲存最小值的索引值

接著開始

第一輪

58 4 52 4 87 1 23 9

一開始先設定minValueIndex為陣列的第一個索引值 0
接著一輪掃過去會發現arr[5]是最小的
所以minValueIndex = 5
arr[0]和arr[minValueIndex]的值對調

1 4 52 4 87 58 23 9

第二輪

再來設定minValueIndex = 1，也就是陣列的第二個元素

掃一輪過去會發現自己就是最小的，所以不用變

第三輪

再來設定minValueIndex = 2，也就是陣列的第三個元素

掃一輪過去會發現arr[3]是最小的

所以minValueIndex = 3

arr[2]和arr[minValueIndex]的值對調

1 4 4 52 87 58 23 9

第四輪

再來設定minValueIndex = 3，也就是陣列的第四個元素
掃一輪過去會發現arr[7]是最小的
所以minValueIndex = 7
arr[3]和arr[minValueIndex]的值對調

1 4 4 9 87 58 23 52

第五輪

再來設定minValueIndex = 4，也就是陣列的第五個元素
掃一輪過去會發現arr[6]是最小的
所以minValueIndex = 6
arr[4]和arr[minValueIndex]的值對調

1 4 4 9 23 58 87 52

第六輪

再來設定minValueIndex = 5，也就是陣列的第六個元素
掃一輪過去會發現arr[7]是最小的
所以minValueIndex = 7
arr[5]和arr[minValueIndex]的值對調

1 4 4 9 23 52 87 58

第七輪

再來設定minValueIndex = 6，也就是陣列的第七個元素
掃一輪過去會發現arr[7]是最小的
所以minValueIndex = 7
arr[6]和arr[minValueIndex]的值對調

1 4 4 9 23 52 58 87

這樣就完成了！是不是比泡沫排序還要簡單呢？看到這邊可以開始嘗試寫看看了！

有沒有發現選擇排序和泡沫排序有點相似的味道，實際上泡沫排序是每次比較後就做互換，但選擇排序是在掃過一輪才做互換，所以正常來說，選擇排序在多數情況可能會比泡沫排序還快一點點。下面是我隨機生成一個長度為10萬的整數陣列，分別的排序耗時。

（其實演算法的效率比較不能這樣比，只是我想表示的是「互換很吃時間的！」）

不過由於他們的平均時間複雜度是一樣的 O(n^2)，所以不是很常被採用，但是對於初學者依舊是一個很好的練習題目！

下面是我自己練習的Java版code

理論上c和c++是可以幾乎copy過去的

只要把一些java的語法去掉就可以了

有興趣的人自己看看

public static void selectionSort(int[] arr, int beginI, int endI){
    int minValueIndex;
    int temp;
    if(endI-beginI+1 == 1){
        return;
    }
    for(int i = beginI ; i < endI+1 ; i++){
        minValueIndex = i;
        for(int j = i + 1 ; j < endI+1 ; j++){
            if(arr[j] < arr[minValueIndex]){
                minValueIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minValueIndex];
        arr[minValueIndex] = temp;
    }
}