Chapter 13 排序法 - Ian-Liu-1990/Data-Structure GitHub Wiki

Ｉ. 按資料量與記憶體分類

  1. 內部排序 : 將資料(量不大)全部載入主記憶體，全部在記憶體中進行排序

  2. 外部排序 : 資料量太大，無法全部載入主記憶體，將資料存於輔助記憶體空間內，在分段載入主記憶體以進行排序

  3. 穩定 : 排序完後，相同值仍維持原來先後次序

  4. 不穩定 : 反之，排序完後，相同值仍維持原來先後次序

  5. 比較排序 : 依照大小值進行比較做排序

  6. 分佈式排序 : 依照數值統計與分佈範圍進行排序

ＩＩ. 排序 - 快 速 複 習

  1. 比較排序
名 稱 穩 定 最 佳 最 差 平 均 適 性 額 外 空 間
插入 Stable Ｏ(N) Ｏ(N^2) Ｏ(N^2) 幾乎已排好 無
氣泡 Stable Ｏ(N) Ｏ(N^2) Ｏ(N^2) 幾乎已排好 無
選擇 沒有額外空間則Unstable Ｏ(N^2) Ｏ(N^2) Ｏ(N^2) 記錄較長，關鍵值較短，需搬動次數少 無
Shell UnStable Ｏ(Nｌｏｇ*ｌｏｇ) Ｏ Ｏ 記錄較長，關鍵值較短，需搬動次數少 無
快速 Unstable Ｏ(ＮｌｏｇＮ) Ｏ(Ｎ^2) Ｏ(ＮｌｏｇＮ) 不適合有大量已排序 Ｏ(logＮ)~Ｏ(Ｎ)
快速延伸 - 尋找第K小或中位數 Ｏ(Ｎ) Ｏ(Ｎ^2) Ｏ(Ｎ) - - -
合併 Stable Ｏ(ＮｌｏｇＮ) - - 允許有額外空間 Ｏ(Ｎ)
堆積 Unstable Ｏ(ＮｌｏｇＮ) - - 無
  1. 分佈式排序
名 稱 穩 定 最 佳 最 差 平 均 適 性 額 外 空 間
MSD - 桶子排序 Stable Ｏ(ＮｌｏｇＮ)平均分佈資料 Ｏ(nk)資料分佈不均 Ｏ(nk) 允許有額外空間 Ｏ(n)
LSD - 桶子排序 Stable Ｏ(k(n+b)) Ｏ(k(n+b)) Ｏ(k(n+b)) 允許有額外空間 Ｏ(n+b)
計數排序 Stable Ｏ(m+n) Ｏ(m+n) Ｏ(m+n) 允許有額外空間，關鍵值範圍小，鍵值重複性高 Ｏ(m+n)

ＩＩＩ. 程式排序說明

１. 插入

２. 氣泡

３. 選擇

４. 快速