iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 18
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 18

Day18-排序法系列(二)-選擇排序法

選擇排序法 Selection Sort會在未排序的資料列中尋找資料值最小(大)的元素,和原本資料列的第一個元素交換位置,再從剩下未排序的資料列中尋找資料值最小(大)的元素,和原本資料列的第二個元素交換位置,以此類推。

此網頁有小動畫可以參考看看,非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Selection/1.php

接著我們來實作吧!完成後會討論其時間複雜度~

首先建立一個 selectionSort() 的函式,接著建立兩層迴圈,第一層迴圈針對整個資料列進行遍歷,並將當前遍歷到的索引值設為 min

第二層迴圈負責找出要交換的索引值,因此在迴圈設定:
假如當前要排序的值 data[min] 大於 目前找到可能要交換的值,就將該值索引指定給 min。

內層 for 迴圈結束後,min 記錄著要交換值的索引,透過 if 判斷如果要交換值的索引和當前外層 for 迴圈遍歷到的索引值不同的話,代表必須交換數字。

function selectionSort(data) {
  const length = data.length;
  for (let i = 0; i < length; i++) {
    let min = i;
    for (let j = i + 1; j < length; j++) {
      if(data[min] > data[j]) {
        min = j;
      }
    }
    if( i != min) {
      let temp = data[i];
      data[i] = data[min];
      data[min] = temp;
    }
    console.log(data);
  }
}

selectionSort([1, 234, -5, 78, -182, 45]);

透過 console.log(data); 可以看到排序過程:

時間複雜度:

  • 最佳/平均/最差的情況下,時間複雜度都是: O(n^2)
    原因: 無論資料順序如何,都會執行兩個迴圈

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day18-selection-sort.js

明天將會介紹第三種排序法,插入排序法!


上一篇
Day17-排序法系列(一)-氣泡排序法
下一篇
Day19-排序法系列(三)-插入排序法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言