ETH官方钱包

切換
舊版
前往
大廳
主題

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

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

    這次來講解的排序法,是一個概念上比泡沫排序可能還要簡單一點的排序法,叫做-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;
    }
}

創作回應

更多創作