從排序學演算法( 1 ) — Selection Sort

Photo by Andre Taissin on Unsplash

寫程式的時候，遇到排序問題常常都是直接呼叫built-in function來用，卻沒有真正去思考過它背後的演算法為何，這陣子面試剛好有被問到遇到排序的演算法，這才知道原來排序有這麼多種方法，決定用筆記的方式紀錄每個方法的差異。

首先從最直覺好懂的 Selection Sort 開始介紹。

Selection Sort

💡 不斷從未排序陣列中找出最小的元素並放到陣列最左側

步驟：

1. 找出未排序陣列中最小的元素
2. 將最小的元素和最左邊的元素交換位置，並回到步驟1，直到整個陣列都完成排序

圖示解說：

🟦 未排序元素 🟩 已排序元素 🟧 該次排序時位置有變動的元素

首先將整個陣列視為已排序過(sorted subarray)以及未排序過(unsorted subarray)的陣列。

陣列初始化為 const array = [50, 2, 31, 10, 67]，此時整個陣列都未排序。首先找出陣列中最小的元素並和未排序陣列(藍色)最左元素交換位置

未排序陣列

從陣列中找出最小的元素並和未排序陣列最左元素交換位置

以本例來說就是元素 2 和元素 50 互換位置

元素2和元素50互換位置

換完後元素 2 就變成已排序陣列(綠色)的一員，接著未排序陣列中最小的元素是 10，和元素 50 互換位置後如下圖：

元素10和元素50互換位置後

接著未排序陣列中元素 31 最小，也剛好位於未分類陣列中最左側，故維持不動

元素31保持不動

跟元素 31 一樣，元素 50 也維持不動

元素50不動

元素 67 也不動

元素67不動

此時整個陣列都變成綠色了，代表排序完成

排序完成

程式碼：

Selection Sort

時間複雜度：O(n²)

空間複雜度：O(1)

以上就是 Selection Sort 的介紹，有任何問題或心得歡迎留言告訴我，也可以接著往下看 Bubble Sort 的講解！