選擇排序 (Selection Sort)

程式資結演算法

Written by:

選擇排序的原理是每次都在剩下的資料中找出最小的資料,將該資料丟到當前的正確位置。

歡迎參考 edX 上開授的 CS 50 課程示範影片:

也就是說將第 i 筆到第 n 筆資料中排出最小值,與第 i 筆資料做交換。

  • 從 i = 1 到 n-1 ,作 n-1 回合
  • 每回合自第 i 筆到第 n 筆中排出最小值,與第 i 筆資料做交換

虛擬碼

 

程式碼

時間複雜度

無論 Average/Worst/Best Case 皆為 O(n2)

比較次數= (n-1) + (n-2) + … +1 = n(n-1)/2 次

 

空間複雜度: O(1)

需要一個額外的空間儲存暫存變數 temp 用來做資料交換用。

 

穩定性: UNSTABLE

選擇排序屬於不穩定排序──第 i 回合會將第 i 小的資料與第 i 個位置做交換。即使資料大小相同也會被交換。

可以發現在第一回合過後,5* 從原本在 5 後面,跑到了 5 前面。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *