Basics Sorting - 基礎排序演算法

演算法複習——排序

  1. 時間複雜度-執行時間(比較和交換次數)
  2. 空間複雜度-所消耗的額外記憶體空間
    • 使用小堆疊、隊列或表
    • 使用鏈表或指針、數組索引來代表數據
    • 排序數據的副本

舉例來說，如果今天遇到一個題目，時間限制是1s，但僅有10^3筆輸入數據，此時即使使用O(n^2)的演算法也沒問題，但若有10^5筆輸入，則O(n^2)的演算法則非常可能超時，在實作前就要先思考是不是有O(n\log n)或更快的演算法。

穩定性：如果排序後文件中擁有相同鍵的項的相對位置不變，這種排序方式是穩定的。

  • Bucket Sort
  • Radix Sort

從穩定性角度考慮可分為如下兩類：

  • 穩定
  • 非穩定

Reference