可以合理地預(yù)期，在運行時您不能做得比O（N log N）好。

但是，有趣的部分是研究您是否可以就地，穩(wěn)定地對其進(jìn)行排序，其最壞情況下的行為等等。

Putty名氣的Simon Tatham解釋了如何使用merge sort對鏈表進(jìn)行排序。他總結(jié)了以下評論：

像任何自重排序算法一樣，它的運行時間為O（N log N）。因為這是Mergesort，所以最壞情況下的運行時間仍然是O（N log N）。沒有病理病例。

輔助存儲需求小且恒定（即排序例程中的一些變量）。由于數(shù)組中鏈表的本質(zhì)不同，Mergesort實現(xiàn)避免了通常與算法相關(guān)的O（N）輔助存儲成本。

C語言中還有一個示例實現(xiàn)，可用于單鏈表和雙鏈表。

就像@J?rgenFogh在下面提到的那樣，big-O表示法可能會隱藏一些恒定因素，這些因素可能會導(dǎo)致一種算法由于內(nèi)存局部性，項目數(shù)量少等原因而表現(xiàn)更好。

根據(jù)許多因素，將列表復(fù)制到數(shù)組然后使用Quicksort實際上可能更快。

之所以會更快，是因為數(shù)組的緩存性能要比鏈表好得多。如果列表中的節(jié)點分散在內(nèi)存中，則可能是整個地方都生成高速緩存未命中。再說一次，如果數(shù)組很大，無論如何都會遇到緩存未命中的情況。

Mergesort可以更好地并行化，因此如果您要這樣做，可能是更好的選擇。如果直接在鏈接列表上執(zhí)行它，則速度也更快。

由于這兩種算法都在O（n * log n）中運行，因此要做出明智的決定，就需要在要運行它們的計算機上對它們進(jìn)行性能分析。

-編輯

我決定檢驗我的假設(shè)，并編寫了一個C程序，該程序測量（使用clock()）對一個int鏈接列表進(jìn)行排序所花費的時間。我嘗試了一個分配有每個節(jié)點malloc()的鏈表和一個將節(jié)點線性排列在一個數(shù)組中的鏈表，因此緩存性能會更好。我將它們與內(nèi)置的qsort進(jìn)行了比較，后者包括將所有內(nèi)容從碎片列表復(fù)制到數(shù)組，然后將結(jié)果再次復(fù)制回去。每種算法都在相同的10個數(shù)據(jù)集上運行，并對結(jié)果取平均值。

結(jié)果如下：

N = 1000：

帶有合并排序的片段列表：0.000000秒

qsort數(shù)組：0.000000秒

合并排序的裝箱單：0.000000秒

N = 100000：

具有合并排序的片段列表：0.039000秒

帶qsort的數(shù)組：0.025000秒

合并排序的裝箱單：0.009000秒

N = 1000000：

帶有合并排序的片段列表：1.162000秒

帶qsort的數(shù)組：0.420000秒

合并排序的裝箱單：0.112000秒

N = 100000000：

具有合并排序的片段列表：364.797000秒

帶qsort的數(shù)組：61.166000秒

帶合并排序的裝箱清單：16.525000秒

結(jié)論：

至少在我的機器上，復(fù)制到數(shù)組中以提高緩存性能非常值得，因為在現(xiàn)實生活中很少有完全打包的鏈表。應(yīng)該注意的是，我的機器有一個2.8GHz的Phenom II，但是只有0.6GHz的RAM，因此緩存非常重要。

如許多次所述，一般數(shù)據(jù)的基于比較的排序的下限將為O（n log n）。為了簡要地概括這些參數(shù)，有n！列表的不同排序方式。任何具有n的比較樹！（位于O（n ^ n）中）可能的最終排序?qū)⒅辽傩枰猯og（n?。┳鳛槠涓叨龋哼@為您提供了O（log（n ^ n））下限，即O（n登錄n）。

因此，對于鏈表上的常規(guī)數(shù)據(jù)，將對所有可以比較兩個對象的數(shù)據(jù)進(jìn)行處理的最佳排序?qū)⑹荗（n log n）。但是，如果您要處理的工作域更有限，則可以縮短所需時間（至少與n成正比）。例如，如果您使用的整數(shù)不大于某個值，則可以使用Counting Sort或Radix Sort，因為它們使用要排序的特定對象來降低與n成正比的復(fù)雜度。不過請注意，這些會增加您可能不會考慮的復(fù)雜性（例如，Counting Sort和Radix sort都添加基于您要排序的數(shù)字的大小的因子O（n + k） ），其中k是例如“計數(shù)排序”的最大數(shù)字的大?。?。

另外，如果碰巧具有完美散列的對象（或至少具有不同映射所有值的散列），則可以嘗試在其散列函數(shù)上使用計數(shù)或基數(shù)排序。