TA貢獻1784條經(jīng)驗 獲得超9個贊
正如許多人所指出的，Quicksort的平均案例性能比mergesort更快。 但這只有在假設(shè)您有恒定的時間按需訪問任何內(nèi)存時才是正確的。
在RAM中，此假設(shè)通常不太差（由于高速緩存，它并不總是正確的，但也不太糟）。但是，如果您的數(shù)據(jù)結(jié)構(gòu)足夠大，可以存儲在磁盤上，那么快速排序就會因您的平均磁盤每秒執(zhí)行200次隨機尋道而被殺死。但是，同一張磁盤沒有順序順序讀取或?qū)懭朊棵胝鬃止?jié)數(shù)據(jù)的麻煩。mergesort正是這樣做的。
因此，如果必須在磁盤上對數(shù)據(jù)進行排序，那么您真的很想在mergesort上使用一些變體。（通常，您先對子列表進行快速排序，然后在某個大小閾值以上開始將它們合并在一起。）
此外，如果您必須對如此大小的數(shù)據(jù)集執(zhí)行任何操作，請認真考慮如何避免尋找磁盤。例如，這就是為什么這樣的建議，即在數(shù)據(jù)庫中進行大量數(shù)據(jù)加載之前先刪除索引，然后再重建索引，這是標準建議。在加載期間保持索引意味著不斷尋找磁盤。相反，如果刪除索引，則數(shù)據(jù)庫可以通過以下方式重建索引：首先對要處理的信息進行排序（當(dāng)然使用mergesort?。?，然后將其加載到該索引的BTREE數(shù)據(jù)結(jié)構(gòu)中。（BTREE本質(zhì)上是保持順序的，因此您可以從排序的數(shù)據(jù)集中加載一個，而很少有磁盤尋道。）
在很多情況下，了解如何避免磁盤尋道使我使數(shù)據(jù)處理作業(yè)花費數(shù)小時而不是數(shù)天或數(shù)周。
TA貢獻1811條經(jīng)驗 獲得超4個贊
實際上，QuickSort是O（n 2）。它的平均運行時間為O（nlog（n）），但最差的運行時間為O（n 2），當(dāng)您在包含很少的唯一項目的列表上運行它時，會發(fā)生這種情況。隨機化為O（n）。當(dāng)然，這不會改變最壞的情況，它只是防止惡意用戶使您的排序花費很長時間。
QuickSort之所以受歡迎，是因為它：
就地（MergeSort要求額外的內(nèi)存與要排序的元素數(shù)量成線性關(guān)系）。
有一個小的隱藏常數(shù)。
舉報