簡介

排序(Sorting)演算法是常用到的一種演算法,顧名思義他是用來將資料依據特定的規則做排序後輸出;既然稱為排序就會有一個比較順序的依據,例如數字就比較數值大小、字串則依ASCII字母順序或者物件會有自定義的規則。一般沒有特別指定的話,輸出是以遞增排序為準。

穩定排序

排序演算法分為穩定(Stable)不穩定(Unstable)兩種,是指當資料中有相等數值的兩元素,經過排序之後是否能夠保持原有的相對位置,例如:

(猴子, 智商60) (丁丁, 智商20) (拉拉, 智商20) (路人甲, 智商90)

將這些資料依據智商來排序,會發現智商20的有兩位,因此我們可能得到以下兩種情況

(丁丁, 智商20) (拉拉, 智商20) (猴子, 智商60) (路人甲, 智商90)
(拉拉, 智商20) (丁丁, 智商20) (猴子, 智商60) (路人甲, 智商90)

第一種情況丁丁和拉拉與原始的相對位置一致(丁丁在前),能夠總是維持相對位置的排序法我們稱之為穩定排序,反之則稱為不穩定排序,不能確保相對位置與原來一樣(但是也有可能一樣)。

如果是純數字的排序基本上是沒有差異,但在像這種物件資料就會有影響。

分類

排序演算法依據特性大致分為兩類

  1. 穩定與不穩定,即為上文所描述的特性。
  2. 比較與非比較,是否利用比較元素的數值來做排序,大部分的排序法都屬於比較類別。

除此之外還有現實生活中才存在的排序法,例如珠排序法(Bead Sort),單靠程式無法達到理論的效率。

常見排序法

氣泡排序法(Bubble Sort)

插入排序法(Insertion Sort)

合併排序法(Merge Sort)

選擇排序法(Selection Sort)

快速排序法(Quick Sort)

堆排序法(Heap Sort)

...

文章標籤
創作者介紹
創作者 emn178 的頭像
emn178

小殘的程式光廊

emn178 發表在 痞客邦 留言(0) 人氣()