iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
0

選擇排序法,主要精神在迴圈找尋選擇最小值,然後將最小值與第一個值交換。

假設有一陣列[7,5,1,20,8],並假設最小值是第一個數值(7),第一個數值就與陣列所有值比較大小,如果發現有更小的值,就與其交換位子。

作法:7與[7,5,1,20,8]比較,發現1更小,所以7與1交換位子。
數字(7)車輪戰比較完為[1,5,7,20,8]
作法:5與[5,7,20,8]比較,未發現有更小的值,不交換位子。
數字(5)車輪戰比較完為[1,5,7,20,8]
作法:7與[7,20,8]比較,未發現有更小的值,不交換位子。
數字(7)車輪戰比較完為[1,5,7,20,8]
作法:20與[20,8]比較,發現8更小,所以20與8交換位子。
數字(20)車輪戰比較完為[1,5,7,8,20]
作法:20與[20]比較,未發現有更小的值,不交換位子。
數字(20)車輪戰比較完為[1,5,7,8,20]

可以看出這是一個雙重迴圈比較最小值的演算法。

function selectionSort(arr){
  for(let i=0;i<arr.length;i++){
    //suppose the min value is the each value of the array.
    let min=arr[i];
    //suppose the min index is i.
    let minIndex=i;
    for(let j=i;j<arr.length;j++){
      //find the min value and min index of the others
      if(arr[j]<min){
        min=arr[j];
        minIndex=j;
      }
    }
    //change the value after looping searching min value
    [arr[minIndex],arr[i]]=[arr[i],arr[minIndex]];
  }
  return arr;
};

const arr=[7,5,1,20,8];
console.log(selectionSort(arr));

return [ 1, 5, 7, 8, 20 ]

完整程式碼


上一篇
氣泡排序法(Bubble Sort)
下一篇
插入排序(Insertion Sort)
系列文
透過JavaScript學習演算法與資料結構30

尚未有邦友留言

立即登入留言