iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 29
0
Software Development

One Punch 一拳搞定前後端面試系列 第 29

[One Punch 一拳搞定前後端面試] DAY-29 - Selection Sort

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
}

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

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

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

明天再來看看更有趣的吧!

本文同時發布於好讀整理版


上一篇
[One Punch 一拳搞定前後端面試] DAY-28 - Bubble Sort
下一篇
[One Punch 一拳搞定前後端面試] DAY-30 - Event System
系列文
One Punch 一拳搞定前後端面試30

尚未有邦友留言

立即登入留言