簡介

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

穩定排序

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

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

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

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

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

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

分類

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

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

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

常見排序法