[演算法]選擇排序(selection sort)

選擇排序(selection sort)」演算法,假設有 10 個學生考試,要將考試的分類由高排至低,第一次查找 10 個分數,找出最低的;第二次查找 9 個分數,找出最低的,依此類推,則可以得到分數由高至低的排列。那麼執行次數及時間又該如何表達呢

 選擇排序(selection sort)

查找的規則如下

一、第一次找:從 10 個學生裡的分數中,先假設第一個分數最高,然後拿第2個分數與第1個分數來比較,若第2個分數沒有比較高,則繼續拿第3個分數來比較;反之,若第2個的分數比第1個的分數高,則拿第2個的分數與第3個分數比較。以此類推,則在第一次找完畢時,可以得到1個最高的分數。

二、第二次找,與上述同,只是變成剩下 9 個學生的分數中去找。

總共要找 10 次,而每一次的查找中,又要去逐一比較,如下圖:

平均每次要查找 n/2 個分數,執行時間則為 O(n*n/2)。但 大O 依據規則,會忽略像 1/2 這樣的常數,所以執行時間寫成 O(n * n) 即可。

 

選擇排序速度上並不是很快,後面將介紹「快速排序」,是此類問題較快的排序方式。

其它演算法:「二進位搜尋」演算法

您可在此處留言

搶先留言!

avatar
  Subscribe  
Notify of