單元 3:選擇排序
3-1 排序
📒 什麼是排序
排序是將資料依照規則進行排列。例如:身高、成績等屬於數值型的資料,可以依照數值的大小進行排列;例如:時間資料可以依照時間前後進行排列;例如:文字資料可以依照編碼值進行排列。
📒 排序演算法
當電腦在處理資料時,根據排序的規則,有不同的方式進行排序。例如:選擇排序法、插入排序法與氣泡排序法。
📒 選擇排序法
選擇排序法是一種符合人類直覺的演算法。依照排序的規則,選擇最小(最大)項目,放置在資料的最前面,再從剩餘未排序元素中繼續尋找最小(最大)項目,然後放到已排序序列的末尾。以此類推,直到所有項目均排序完畢。
1. 適用時機
選擇排序演算法適用於資料量較小的情況下,因為其時間複雜度為 O(n^2),隨著資料量增加,排序所需的時間會快速增加,不適合用於大規模資料的排序。另外,由於選擇排序是透過不斷地選擇最小值進行排序,所以當資料分布不均時,其排序效率會明顯受到影響。
2. 優點
簡單易懂:選擇排序演算法的概念相對簡單,易於理解和實現。
原地排序:選擇排序演算法是一種原地排序演算法,不需要額外的儲存空間,節省內存使用。
適用於部分排序:當資料集中部分已經有序時,選擇排序演算法的效率會比較高,因為其只需要進行少量的比較操作。
3. 缺點
效率較低:由於其時間複雜度為 O(n^2),因此在大規模資料排序時,效率比較低。
不穩定排序:當資料中存在相同的元素時,排序前後它們的相對位置可能會改變,因此是一種不穩定排序演算法。
比較次數多:在資料量較大時,選擇排序演算法需要進行較多次的比較操作,比較耗時。
📒 補充說明
時間複雜度:指的是一個演算法所需的時間量隨著輸入資料量的增加而增加的速度。在這裡,O(n^2)表示演算法的時間複雜度與輸入資料的規模 n 的平方成正比,即當輸入資料量增加一倍時,演算法執行所需時間會增加至少四倍。這是由於選擇排序演算法採用了兩重巢狀迴圈,使得排序時間與資料量呈平方關係。當資料量非常大時,這種複雜度會讓演算法的執行時間變得非常長,因此對於大型資料的排序,更高效的排序演算法,例如快速排序和合併排序等,更適合使用。