[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10

重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 Selection Sort 選擇排序

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/572/lectures/29806

本篇範圍:Chapter 5

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

Selection Sort 以由小到大排序為例

1. 從第一個元素開始,找出最小的元素。最後一個元素會是最大的,所以只要取到倒數第二個元素
2. 將最小的元素 Index 給保留下來,因為你得跑完整個陣列才能確定最小元素 Index
3. 將最小的元素和第 i 項元素交換位置
無論是最差、最優或是平均解的時間複雜度都是 O(n^2)。這點跟冒泡排序、插入排序就不同 (這兩個的最優排序都是 O(n) )。因為 Selection Sort 就算你原始陣列已經是由小到大排序了,但你依舊要透過「遍歷整個陣列」才能確定它是剩餘陣列中的最小值。

程式碼

https://github.com/andy922200/hiskio-the-idea-of-algorithm/commit/d4f3b487099749dd6ed2427af3fa276707e2610e


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀