# 選擇排序法(Selection sort)

假設我們要使用選擇排序法進行陣列元素由小到大的排序，我們需要從未排序的元素中找到最小值將之與前面的值做交換，下面我直接舉例說明可能會比較容易理解。

## 舉例說明

假設使用選擇排序法將陣列中的值由小到大排序。

初始陣列為：[8,3,2,1,7,4,6,5]

那麼第一次排序時會由左至右在陣列中找到最小的值，並將之與第一個位置的值做交換，因此第一輪結束後的陣列為：[1,3,2,8,7,4,6,5]。

完整的排序結果如下圖所示：


### 說明
1. 選擇排序一共有 `陣列大小-1` 輪排序。
2. 每一輪排序又是一個循環。

### 循環的規則
1. 先假定當前這個數是最小數，然後和後面的每個數進行比較。
2. 如果發現有比當前數更小的數，就重新確定最小數，並得到索引值。
3. 當遍歷到陣列的最後時，就得到本輪的最小值和對應的索引。
4. 將目前的數與最小值交換。

## 程式碼實現

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {

        int arr[] = {8,3,2,1,7,4,6,5};
        int min; //紀錄本輪最小值
        int index = 0; //紀錄最小值位置索引

        for(int i = 0; i < arr.length - 1; i++) { //總共比 陣列大小-1 輪
            min = arr[i]; //將當前數設為最小
            for(int j = i+1; j <= arr.length - 1; j++) {//對剩下的元素進行比較
                if(arr[j] < min) { //若有比當前數還小的元素
                    min = arr[j]; //紀錄最小值
                    index = j; //紀錄最小值索引
                }
            }
            if(index != i) {
                arr[index] = arr[i]; //將當前值放到最小值位置完成交換
                arr[i] = min; //把最小值與當前值做交換
            }
            System.out.println("第"+(i+1)+" 輪結果為: "+Arrays.toString(arr));
        }
    }
}

output

第1 輪結果為: [1, 3, 2, 8, 7, 4, 6, 5]
第2 輪結果為: [1, 2, 3, 8, 7, 4, 6, 5]
第3 輪結果為: [1, 2, 3, 8, 7, 4, 6, 5]
第4 輪結果為: [1, 2, 3, 4, 7, 8, 6, 5]
第5 輪結果為: [1, 2, 3, 4, 5, 8, 6, 7]
第6 輪結果為: [1, 2, 3, 4, 5, 6, 8, 7]
第7 輪結果為: [1, 2, 3, 4, 5, 6, 7, 8]

## 速度測試

public static void main(String[] args) {
    // int arr[] = {8,3,2,1,7,4,6,5};
    int arr[] = new int[80000];
    for(int i = 0; i < 80000; i++) {
        arr[i] = (int)(Math.random() * 80000);
    }
    Instant startTime = Instant.now();
    selectionSort(arr);
    Instant endTime = Instant.now();
    System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}

output

共耗時：642 毫秒
共耗時：630 毫秒
共耗時：632 毫秒
共耗時：632 毫秒

八萬筆隨機數陣列做選擇排序法在我的電腦上跑僅需 634 ms，比泡沫排序法的 7 秒還快很多，因此我們可以得出結論：同樣大小的資料進行泡沫和選擇排序，選擇排序的速度會比泡沫排序來的快。

其實光是看程式碼就能知道，因為泡沫排序法兩個for迴圈都是由0開始，而選擇排序法第二層for迴圈是從 i+1 開始，所以需要比對的資料沒有那麼多，速度會比較快。

## 時間複雜度
假設今天要對一陣列使用選擇排序法由小到大排序。

### 最佳：O(n^2^)

### 平均：O(n^2^)

### 最差：O(n^2^)

無論資料順序如何，都會執行兩個迴圈。