選擇排序算法的標準

Question

我很想知道如何根據輸入選擇排序算法，以便我可以獲得最佳效率。

它應該是在輸入大小或如何安排輸入（Asc/Desc）或數據結構使用等...？

Answer 1

的算法的重要性一般，和排序算法以及是如下：

（*）正確性 - 這是最重要的事情。如果你的算法速度快，效率高，但是錯誤，那麼它就毫無價值。在排序，即使你有2名候選人是正確排序，但你需要一個stable sort - 你會選擇穩定的排序算法，即使是低效率的 - 因爲它是正確的你的目的，另一種是沒有。

下一頁基本運行時間之間權衡，需要空間和實施時間（如果你需要從頭開始實現的東西而不是使用一個庫，爲未成年人提高性能 - 它可能不值得）

有些東西考慮上述關閉提到的貿易時要考慮到：

1. 輸入的尺寸（例如：對於小輸入，插入排序是憑經驗更快然後更先進的算法，thoug h需要O(n^2)）。
2. 輸入的位置（磁盤上的排序算法與RAM上的算法不同，因爲在不順序時磁盤讀取效率低得多，通常用於在磁盤上排序的算法是合併排序的變體） 。
3. 數據分佈如何？如果數據可能「幾乎排序」 - 也許通常可怕的泡沫排序可以在2-3次迭代中排序，並且與其他算法相比可以超快。
4. 什麼庫你已經執行？需要多少工作才能實現新的功能？它值得嗎？
5. 輸入的類型（和範圍） - 對於可枚舉的數據（例如整數） - 整數設計算法（如基數排序）可能比通用算法算法更有效。
6. 延遲時間要求 - 如果您設計的是導彈頭，並且結果必須在特定的時間內返回，快速排序可能衰減到最差情況下的二次運行時間 - 可能不是一個好選擇，您可能需要使用不同的算法，而不是嚴格的O(nlogn)代替。
7. 您的硬件 - 例如，如果您正在使用巨大的羣集和龐大的數據 - 分佈式排序算法可能會更好，然後嘗試在一臺機器上完成所有工作。

Answer 2

它應該基於所有這些東西。

• 你需要考慮到數據的賬戶規模爲插入排序可能速度比快速排序的小數據集等

• 你需要知道你的數據由於不同的排列最差/每個算法的平均/最佳情況漸近運行時間（以及一些最差/平均情況相同，而另一些可能具有明顯更差的最壞情況vs平均值）

• 並且您顯然需要知道用作如果你的數據已經存在，有一些非常專門的排序算法pecial格式或者即使你可以把它變成一個新的數據結構有效，它會自動做你的排序爲你（一拉BST或堆）

Answer 3

決定你的排序算法的選擇的2分主要的事情是時間複雜度和空間複雜度。根據您的場景以及可用的資源（時間和內存），您可能需要根據每種排序算法必須提供的排序算法進行選擇。

排序算法的實際性能取決於輸入數據量太大，而且它有助於如果我們知道輸入數據的某些特性事前，如輸入的大小，如何排序的數組已經是了。

例如， 如果您事先知道輸入數據只有1000個非負整數，則可以很好地使用counting sort以線性時間對這樣的數組進行排序。

排序算法的選擇取決於空間和時間的約束以及輸入數據的大小/特性。

Answer 4

在非常高的水平，您需要考慮插入的比例與每種算法的比較。

對於文件的整數，這不會是巨大的相關性，但如果說你排序基於內容的文件，你會很自然想要做的儘可能少的比較成爲可能。