Selection Sort 選擇排序法#

選擇排序法,又稱為「證明我是錯的」排序法。

證明我是錯的排序法#

為什麼叫證明我是錯的排序法呢?

那是因為此排序法假定從第一個元素是最小的開始鎖定,然後檢查每個後面的元素是否小於該元素,

若小於則交換(swap)。遍歷完就鎖定下個元素,直到每個元素鎖定完畢

實作#

鎖定的位置(index):indexOfMin

Java 實作 Selection Sort#

private static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int indexOfMin = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[indexOfMin]){
indexOfMin = j;
}
}
int smallerNumber = arr[indexOfMin];
arr[indexOfMin] = arr[i];
arr[i] = smallerNumber;
}

JavaScript 實作 Selection Sort#

function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let indexOfMin = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[indexOfMin]) {
indexOfMin = j
}
}
if (indexOfMin !== i) {
let lesser = arr[indexOfMin]
arr[indexOfMin] = arr[i]
arr[i] = lesser
}
}
return arr
}

在最糟的情況下,選擇排序法會比上一個氣泡排序法來的快速。

因為氣泡排序法交換的次數會比較多。

雖然都是兩層迴圈,但時間複雜度卻不同,是不是很有趣呢!

本文同時發布於鐵人賽