排序演算法 | 選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優點與資料移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

使用選擇排序為一列數字進行排序的過程：

選擇排序的範例動畫。紅色表示目前最小值，黃色表示已排序序列，藍色表示目前位置。

實作範例(Java)

@Test
public void SelectionSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    for (int i = 0; i < arr.length - 1; i++) {
        int index = i;
        for (int j = 1 + i; j < arr.length; j++) {
            if (arr[j] < arr[index]) {
                index = j;// 保存最小元素的下標
            }
        }
        // 此時已經找到最小元素的下標
        // 將最小元素與前面的元素交換
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

結果：

1	[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

實現也非常的簡單，首先在外循環裡定義了一個index變量儲存i的值，這是為了避免重複地比較，因為在每一輪的比較結束後，前i個元素是已經排好序的，所以無需再次比較，只需從i開始即可。後面的比較都是基於index位置的元素進行比較，倘若比較完後index位置的元素是最小值，那就無需交換，不動即可。而如果找到了比index位置的元素更小的元素，那就將該元素的索引賦值給index，然後繼續比較，直到比較完成，比較完成之後得到的index即為數組中的最小值，那此時只需要將index位置的元素和i位置的元素交換即可。