基於比較的排序技術的侷限性

比較排序在大多數需要排序數據的場景中選擇。諸如合併排序，快速排序，插入排序和其他比較排序等技術可以用O（nLog（n））的下限處理不同的數據類型和效率。基於比較的排序技術的侷限性

我的問題是

是否有基於排序技術比較沒有任何限制？
任何一種情況下，將使用非比較排序技術？

歡呼

來源

2009-04-26 Arnkrishn

你回答或多或少自己。基於比較的排序技術限於O（n Log（n））的下限。基於非比較的排序技術不受此限制。非排序算法的一般問題是該域必須更爲人知，因此它們不像基於比較的技術那樣多功能。

Pigeonhole sort是一個很好很簡單的例子，只要可能的鍵值數量接近元素數量，它就會非常快速。

來源

2009-04-26 22:57:29

顯然，比較排序的侷限性在於時間因素 - some are better than others，但是如果數據集足夠大，它們在某個點上會變得太慢。訣竅是根據您正在排序的數據的種類和組合來選擇正確的。

非比較排序是基於忽略數據的其他因素，例如counting sort將通過檢查每個元素來排序數據集合，而不是將其與集合中的任何其他值進行比較。如果您有一個整數集合，對排序進行排序是非常有用的，如果您有一個整數集合，它將通過將所有元素的值設爲1並將它們放入目標中，然後將所有元素的值爲2等等（好吧，它使用「稀疏」陣列快速縮放收集並重新排序值，留下空白，但這是基本原理）

來源

2009-04-26 22:59:43 gbjbaanb

很容易看出，爲什麼比較排序需要關於N log N比較。有N！如我們所知，ln（N！）大約是N ln N - N + O（ln N）。在大O符號中，我們可以忽略低於N ln N的項，並且因爲ln和log僅相差恆定，我們得到最終結果O（N log N）

來源

2012-07-29 04:14:05

基於比較的排序技術的侷限性

回答

相關問題