Stan Blog

記錄學習到的東西

[Algorithm] Selection Sort (選擇排序法)

前言

因公司業務受疫情影響, 在 7 月中解散工程團隊

至今也休息了一個多月

最近開始複習一些經典演算法, 順便做個筆記

Selection Sort 說明

以下轉自維基 選擇排序

在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。

簡單說就是,將資料分成已排序、未排序

由未排序中找最小值(or 最大值),加入到已排序部份的末端

最後已排序結果會是由小到大(or 由大到小)的順序排序

範例程式碼

Ruby 範例

附上 Ruby 的 online sandbox,有興趣可以把 code 貼進去玩玩看

a = [9, 8, 6, 1, 2, 10, 5, 4, 3, 7]

def selection_sort(array)
  n = array.size - 1
  n.times do |index|
    temp_item, temp_index = array[index], index
      for i in index...array.size
        temp_item, temp_index = array[i], i if array[i] < temp_item
      end
    array[index], array[temp_index] = array[temp_index], array[index]
  end
  array
end

selection_sort(a)

結果如下

螢幕快照 2020-08-19 16 38 26

JavaScript 範例

JavaScript 的 online sandbox,有興趣可以把 code 貼進去玩玩看

const a = [9, 8, 6, 1, 2, 10, 5, 4, 3, 7]

const selectionSort = (array) => {
  const count = array.length;
  for (let i = 0; i < count; i++) {
      let min = i;
      for (let j = i + 1; j < count; j++) {
          if (array[j] < array[min]) {
              min = j;
          }
      }
      if (min !== i) {
          let temp = array[i];
          array[i] = array[min];
          array[min] = temp;
      }
  }
  return array;
}

console.log(selectionSort(a))

結果如下

螢幕快照 2020-08-19 17 18 30

Comments

comments powered by Disqus