如何配置排序算法？

Question

我已經在C語言中編寫了一些排序方法，我希望找到程序最優化（即）分析每個算法的輸入大小。但我該怎麼做？我知道每個方法的時間，但我不知道我怎麼能找到它是'最佳'的大小。

Answer 1

排序算法沒有一個最佳的單個數字。

對於純粹的執行時間，幾乎每種排序算法都會在一組2個數字上最快，但在大多數情況下它並不有用。

某些排序算法可能在更小的數據集上更有效地工作，但這並不意味着它們在該大小下是「最優」的。

某些種類也可能對數據的其他特徵更好地工作。如果數據幾乎已經排序，那麼排序可能非常有效，但如果不是這樣，則可能非常緩慢。其他人將在任何一套給定的尺寸上運行相同。

查看排序的大O（如O（n^2），O（n log n）等）以及排序所具有的任何特殊屬性（例如對近乎排序的數據進行操作）會更有用。

Answer 2

要找到程序最優化的輸入大小（我假設您的意思是最快的，或者排序算法需要最少的比較），您將不得不針對各種輸入進行測試並繪製獨立軸（輸入大小）與從屬軸（運行時）相比較並找到最小值。

Answer 3

這取決於幾個因素：

• 數據行爲：在您的數據已經部分排序？或者它是非常隨機的？

• 數據大小：一個大的輸入（例如1千元以上），你可以保證O（N^2）排序方法就失去了O（N *日誌（N））方法..

• 數據的數據結構：是數組還是列表？非順序訪問數據的排序方法會比列表更慢

所以答案是通過用實際運行程序的一些真實數據來處理輸入大小的變化。

當輸入大小爲> X時，一個較慢的方法（如O（N^2））被某種更快的方法（如O（N * log（N））打敗），則可以說較慢的方法是'經驗最優'輸入大小爲<= X（該值取決於輸入數據的特徵）。