<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

body > .ui-infobar {
display: none;
}

.ui-view-area > .ui-infobar {
display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>
# Selection Sort
###### tags: `Sort`,`Comparison Sort`
### 介紹
Selection Sort 可以將數列分成兩個區塊，**已排序**和**未排序**的兩個部分。每一輪比較時，遍歷**未排序**的區塊中的所有元素，將最小的元素取出放入**已排序**的區塊中。不斷重複這個過程，即可完成排序。

示意圖如下：
圖(一)

如上圖所示，在第一輪遍歷數列時，我們需要從所有元素中，選出最小的並將其記錄下來，那要如何將其放在對的位置上呢？有兩個方法可以進行解決：
1. 創建一個與原資料長度相等的數列做為已排序數列
2. 利用原數列的 index 來進行交換

第一點的話相對直觀，每當我遍歷一次原始數列時，可以找到一個最小值，將那個最小值取出，並添加進已排序數列。但是要記得**將取出的值從原始數列移除**。

第二點則是 in-place 操作，我們不額外創建數列，以圖(一)來說，起始數列為 **[9,4,3,5,1,7]**，此時遍歷數列可以得知 1 是未排序數列中最小的，需要將 1 放置該數列的最前面，與 9 進行交換，交換完的數列為 **[1,4,3,5,9,7]**。第二輪則是可以得知未排序的最小值為 3 ，需要放在已排序數列的第二個位置上，與 4 進行交換，依此類推。

每一輪的排序如下：

| 輪數 | 尋找未排序最小值 | 交換(已完成排序為粗斜體) |
|:---- |:---------------- |:------------------------ |
| 1 | [9,4,3,5,1,7] | [***1***,4,3,5,9,7] |
| 2 | [1,4,3,5,9,7] | [***1,3***,4,5,9,7] |
| 3 | [1,3,4,5,9,7] | [***1,3,4***,5,9,7] |
| 4 | [1,3,4,5,9,7] | [***1,3,4,5***,7,9] |
| 5 | [1,3,4,5,7,9] | [***1,3,4,5,7,9***] |

第一輪會完成第一個數的有序排列，依此類推，第 N-1 輪會完成第 N-1 個數的排列，剩下的數自然會是有序的，因此在有**N**筆資料時，只會需要進行**N-1**輪的比較。

### 程式碼

public static void selectionSort(int[] arr){
    if(arr.length < 2){
        return;
    }
    for(int i = 0; i < arr.length - 1;){
        //將未排序數列中的第一個元素定為最小值
        int minIndex = i; 
        for(int j = i + 1; j < arr.length; j++){
            //遍歷數列，並將暫定最小值與其他元素進行比較
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        //遍歷完畢，將arr[minIndex]放到對的位置
        swap(arr, i, minIndex);
    }
}

//元素交換
public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

### 參考資料
1. 圖(一)：[VisuAlgo](https://visualgo.net/zh/sorting)
2. [算法大神左神（左程云）带你一周刷爆LeetCode，数据结构算法-leetcode真题解析](https://www.bilibili.com/video/BV1kQ4y1h7ok?p=1)

<hr style="height:1px;border:none;border-top:1px dashed #0066CC;">

[資料結構與演算法](/FP0Vd0lqQM2gDIadctxk2Q)
[Sorting 簡介][0]

[0]:https://hackmd.io/7Mo3SJ1wQ5G8s9PIsu9u_w