table.sort使用什麼算法？

我很好奇Lua的默認table.sort使用的算法，只是因爲它比我遇到的其他排序算法慢。我也很好奇，如果Lua的table.sort是用C語言編寫的引擎，或者它在Lua的庫中。table.sort使用什麼算法？

2013-08-04 jocopa3

table.sort使用什麼算法？

的comment in tablib.c（滾動了一下）指出

/* 
** {====================================================== 
** Quicksort 
** (based on `Algorithms in MODULA-3', Robert Sedgewick; 
** Addison-Wesley, 1993.) 
** ======================================================= 
*/

您可以在我提供的鏈接閱讀源代碼。

我也很好奇，如果Lua的table.sort是用C語言編寫的引擎，或者它是在Lua的庫中。

此時，直接和Lua是來全庫（io，table，math，...）是用C寫

來源

2013-08-04 14:17:57 Oberon

請注意，LuaJIT正在考慮切換到[smoothsort]（http://en.wikipedia.org/wiki/Smoothsort），其幾個庫函數現在在Lua字節碼中實現（這實際上是有益的，因爲它可以更好地編譯JIT） –

內部，table.sort使用快速排序，它的用C寫的筆記該快速排序不穩定。有一點讓我感到意外的是，Lua沒有直接使用C的qsort()。

至於性能，很難說，因爲存在各種因素，例如，您正在比較哪種語言和哪種算法，以及正在測試哪種數據。

來源

2013-08-04 14:18:27

使用Lua，我發現有幾個算法比默認的算法快一點。如果尺寸相對較小，雞尾酒排序和氣泡排序實際上比默認快。如果體積很大，那麼LSD Radix排序和其他兩個我說的更快。我正在用不同類型的數據進行測試，比如反轉數組，隨機數組，甚至大多數排序數組，但是對於每個測試，默認排序仍然比較慢。 – jocopa3

@ jocopa3據我所知，這不是Lua的問題，而是快速的。例如，快排在排序數組和反轉數組上表現不佳。如果您需要對特定問題進行排序，並且Lua的默認排序功能不夠好，那麼在C語言中編寫特定的排序算法是一個好主意。 –

@YuHao從查看鏈接的源代碼，Lua的qsort每次都選擇middle作爲關鍵點。這應該接近qsort的理想情況，它不應該表現不佳。我懷疑所有這些lua API調用可能會導致速度變慢，但除非進行配置，否則無法確定。 – greatwolf

table.sort使用什麼算法？

回答

相關問題