Simple Sorting Algorithms

這個 Algorithm 是將目標數字和已排序的數字進行比較和重新排序。首先把一個 Array 分為兩個部分,一個是已經排序的(黃色),另一個是未排序的(白色) 。在進行排序時先將第一個數字設定為已排序的,因為原本已排序部分是空的,之後會由第二個數字開始。第二個數字 (5) 和黃色方格的數字 (4) 進行比較,由於 4 < 5 ,所以不用改變位置同時加入已排序的黃色方格。現時黃色方格有 (4, 5),之後到第三個數字 (2) 和黃色方格內的數字進行比較 。

(2) 先和 (5) 做比較,(2) 較小,(5) 移去原本 (2) 的位置。

(2) 會和第一個數字 (4) 作比較,(2) 較小,(4) 移去原本 (2) 的位置。

(2) 則放進第一格。

剩下的也是按照此方式進行比較和轉換。

Code:

時間複雜度:

  • Best Case: N (當順序的時候)
  • Worst Case: (當倒序的時候)
  • Average Case:

Reference

Selection Sort

Selection Sort Mechanism

這個 Algorithm 是找出目前位置到最尾之間最小的數字並把它和目前位置的數字進行交換。首先將第一個數字 (4) 抽出來,然後將它和之後每一個數字作比較。當發現最小的數字 (2) 然後和它交換位置。這個 (2) 則被視為已排序 (黃色) 的。下一個被抽出來的是第二個數字 (5),它將與之後剩下的數字作比較找出最小的數字,再和那數字 (3) 交換位置。

Code:

時間複雜度: N² (怎樣都會有兩個 loop)

Reference

Bubble Sort

這個 Algorithm 的原理是把最大的數字推到最右面。它最少會有 N (Array 的長度) 個回合,在每一個回合內,將最大的數字推到最右,如果目前的測試目標數字比它的下一個數字大這兩個數字就交換 (swap)位置,反之測試目標則變為下一個數字,例如上圖第一回合的數字 9。在下一個回合因為 9 已被排序 (黃色),Array 的長度會減一。在剩下的 Array 裏,最大的數字也會被推去最右 (上圖數字 5 )。之後也是如此類推。

時間複雜度:

  • Best Case: N (當順序的時候)
  • Worst Case: (當倒序的時候)
  • Average Case:

Code

Reference

--

--

A Programmer, Data Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store