簡介

排序(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 發表在 痞客邦 PIXNET 留言(0) 人氣()