比較排序是一種排序算法，它只通過單個抽象比較操作（通常是“小於或等於”運算符或三向比較）讀取列表元素，該操作確定兩個元素中的哪一個應首先出現在 最終排序清單。 唯一的要求是操作員遵守總訂單的兩個屬性：
如果a≤b且b≤c則a≤c（傳遞性）
對於所有a和b，a≤b或b≤a（總和或三分法）。
a≤b和b≤a都可能; 在這種情況下，要么可以在排序列表中排在第一位。 在穩定排序中，輸入順序確定此情況下的排序順序。
基本介紹
- 中文名：比較計數排序
- 外文名：Comparison count sort
不同分揀技術的性能限制和優勢,備擇方案,
不同分揀技術的性能限制和優勢
比較種類的性能存在基本限制。比較排序必須具有Ω（n log n）比較運算的平均值下界，[1]稱為線性時間。這是僅通過比較獲得的有限信息的結果 - 或者換句話說，是完全有序集合的模糊代數結構。從這個意義上講，mergesort，heapsort和introsort在它們必須執行的比較次數方面是漸近最優的，儘管這個度量忽略了其他操作。非比較排序（例如下面討論的示例）可以通過使用除比較之外的操作來實現O（n）性能，允許它們迴避該下限（假設元素是恆定大小的）。
請注意，比較排序可能會在某些列表上運行得更快;許多自適應排序，例如插入排序在O（n）時間內在已排序或接近排序的列表上運行。 Ω（n log n）下限僅適用於輸入列表可以按任何可能順序排列的情況。
另請注意，排序速度的實際測量可能需要考慮某些算法最佳地使用相對快速的快取計算機記憶體的能力，或者應用程式可能受益於排序數據開始向用戶快速顯示的排序方法（和那么用戶的閱讀速度將是限制因素，而不是在整個列表被排序之前沒有輸出可用於顯示的排序方法。
儘管存在這些限制，但比較排序提供了顯著的實際優勢，即對比較功能的控制允許對許多不同數據類型進行排序並對列表的排序方式進行精細控制。例如，反轉比較函式的結果允許列表反向排序;只需創建一個比較函式，按順序比較每個部分，就可以按字典順序對元組列表進行排序：
function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
if lefta ≠ righta
return compare(lefta, righta)
else if leftb ≠ rightb
return compare(leftb, rightb)
else return compare(leftc, rightc)
平衡的三元符號允許在一步中進行比較，其結果將是“小於”，“大於”或“等於”之一。
比較排序通常更容易適應複雜的訂單，例如浮點數的順序。另外，一旦編寫了比較函式，就可以使用任何比較排序而無需修改;非比較排序通常需要每種數據類型的專用版本。
這種靈活性以及現代計算機上的上述比較分類算法的效率已經導致在大多數實際工作中廣泛偏愛比較分類。
備擇方案
一些排序問題允許比用於比較排序的Ω（n log n）綁定嚴格更快的解決方案;一個例子是整數排序，其中所有鍵都是整數。當鍵形成一個小的（與n相比）範圍時，計數排序是一個線上性時間內運行的示例算法。其他整數排序算法，例如基數排序，並不比比較排序漸近快，但在實踐中可以更快。
按數字對數字對進行排序的問題不受Ω（nlogn）約束（由配對產生的正方形）;最著名的算法仍然需要O（nlogn）時間，但只有O（n）比較。
