Skip to main content

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
}

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

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

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

本文同時發布於鐵人賽