我在哪些情況下使用這些排序算法？

Question

我知道大多數的這些算法的實現，但我不知道自己適合什麼尺寸的數據集使用它們（和數據在內）：

1. 合併排序
2. 冒泡排序（我知道，不是很經常）
3. 快速排序
4. 插入排序
5. 選擇排序
6. 基數排序

Answer 1

首先，您將所有具有複雜度的排序算法丟棄。

然後，你必須研究你的排序算法的幾個屬性，並決定它們中的每一個是否更適合你想要解決的問題。最重要的是：

算法是否就地？這意味着排序算法不會使用任何（O(1)實際）額外的內存。在運行內存關鍵型應用程序時，這個規則非常重要。

冒泡排序，插入排序和選擇排序使用常量內存。 還有一個適用於Merge-sort的就地變體。

該算法是否穩定？這意味着，如果兩個元件x和y相等給出的比較方法，並在輸入xy之前被發現，則在輸出x將y之前找到。

合併排序，冒泡排序和插入排序是穩定的。

該算法是否可以並行化？如果您正在構建的應用程序可以使用並行計算，則可能需要選擇可並行化的排序算法。

更多信息here。

Answer 2

1. 當使用額外的空間等於數組的大小不是問題
2. 只有在非常小的數據集
3. 當你想就地排序和穩定排序不需要
4. 僅在非常小的數據集，或者如果陣列具有高概率已經被排序
5. 僅在非常小的數據集
6. 當值項的數的範圍比小（實驗建議的）

請注意，通常合併或快速排序實現使用插入排序子部分非常小的子例程部分。

Answer 3

使用氣泡僅當要排序的數據存儲在旋轉鼓內存上時才進行排序。這是最佳的，但不適用於隨機存取存儲器。這些日子，這相當於「不使用泡沫排序」。

使用插入排序或選擇根據您可用的其他種類對其進行測試，按照您確定的大小排序。這通常是約20-30項，但YMMV。特別是，當實施合併排序和快速排序等分而治之的排序時，當您當前的數據塊足夠小時，您應該「分解」爲插入排序或選擇排序。

還可以使用插入對接近排序的數據進行排序，例如，如果您以某種方式知道您的數據曾經被排序，並且自那以後沒有多大改變。

使用合併排序當你需要一個穩定的排序（對鏈表進行排序也是很好的）時，要注意對於數組，它需要大量額外的內存。

一般而言，您根本不使用「普通」快速排序，因爲即使智能選擇樞軸，它仍然有最壞情況Omega(n^2)，但與插入排序不同，它沒有任何有用的最佳情況。 「殺手」案件可以系統地構建，所以如果你排序「不可信」的數據，那麼一些用戶可能故意殺死你的表現，無論如何，可能存在一些特定領域的原因，爲什麼你的數據接近殺手案件。如果您選擇隨機樞紐，那麼殺手案件的可能性可以忽略不計，所以這是一種選擇，但通常的方法是「IntroSort」 - 一種QuickSort，可檢測不良情況並切換到HeapSort。

基數排序有點古怪。很難找到最適合的常見問題，但對於固定寬度數據（O(n)，其中比較排序爲Omega(n log n)）具有良好的漸近限制。如果您的數據是固定寬度的，並且輸入大於可能值的數量（例如，超過40億32位整數），那麼開始有可能各種基數排序表現良好。