比較排序

比較排序（英語：Comparison sort）是排序算法的一種，通過一個抽象的內容比較操作（通常是「小於或等於」操作）來確定兩個元素中哪個應該放在序列前面。該算法的唯一要求就是操作數滿足全序關係：

• 如果${\displaystyle a\leq b}$並且${\displaystyle b\leq c}$那麼${\displaystyle a\leq c}$（傳遞性）。
• 對於${\displaystyle a}$或${\displaystyle b}$，要不${\displaystyle a\leq b}$，要不${\displaystyle b\leq a}$（完全性）。

將未貼標籤的砝碼用天平將按質量大小進行排序

對於${\displaystyle a\leq b}$並且${\displaystyle b\leq a}$這種情況，${\displaystyle a}$和${\displaystyle b}$都有可能被排在前面。這時輸入的順序就會決定最後的順序。

比較排序類似於將未貼標籤的砝碼用天平將按質量大小進行排序，並且除了用天平測量兩個砝碼的質量之外不能用其他方法。

算法特例

比較排序包括：

• 快速排序
• 堆排序
• 歸併排序
• 插入排序
• 選擇排序
• 冒泡排序

非比較排序包括：

• 基數排序
• 計數排序
• 桶排序

性能限制和優勢

比較排序有很多性能上的根本限制。在最差情況下，任何一種比較排序至少需要 Ω(n log n) 次比較操作^[1]。這是比較操作所獲的信息有限所導致的，或者說是全序集的模糊代數結構所導致的。從這個意義上講，歸併排序，堆排序在他們必須比較的次數上是漸進最優的，雖然這忽略了其他的操作。前面提到的三種非比較排序算法能在 O(n) 時間內完成，通過非比較操作使他們能夠迴避 Ω(n log n) 這個下界（假設元素為常數大小）。

不過，比較排序在控制比較函數方面有顯著優勢，因此比較排序能對各種數據類型進行排序，並且可以很好地控制一個序列如何被排序。例如，如果倒置比較函數的輸出結果可以讓排序結果倒置。或者可以構建一個按字典順序排序的比較函數，這樣排序的結果就是按字典順序的。

比較排序可以更好地適應複雜順序，例如浮點數。並且，一旦比較函數完成，任何比較算法都可以不經修改地使用；而非比較排序對數據類型的要求更嚴格。

這種靈活性和上述比較排序在現代計算機的執行效率一起導致了比較排序被更多地應用在了大多數實際工作中。

排序所需的比較次數

當${\displaystyle n}$是所需排序的元素個數時，比較排序所需的比較次數按${\displaystyle n\log n}$比例增加。

參閱

注釋

1. 存档副本. [2010-07-22]. （原始內容存檔於2011-10-12）.