選擇或插入排序在學術環境之外有用嗎？

Question

這些排序算法在真實世界的應用程序中有什麼用處嗎？

或者它只是一個排序算法與n^2複雜性的基本例子？

任何人都可以舉一些它的用法的例子嗎？

Answer 1

插入排序是快速排序非常小的數組排序算法之一。

實際上，當排序的子陣列低於某個閾值時，許多quicksort/mergesort實現停止，然後對這些小陣列使用插入排序。

---

選擇排序在實踐中很少使用。

Answer 2

由於複雜度較小的隱藏常量，插入排序對於較小的輸入大小實際上非常快。獲得一定的大小，插入排序比合並排序更快。因此，對於許多流行的排序算法，當數組大小變得非常小時，採用插入排序。

底線：甲O（N 2 ）算法可以是更快的在實踐中比O（N * logN）的算法爲足夠小的尺寸的輸入，由於隱藏常數。

Answer 3

是的，插入排序廣泛用於工業應用。這主要是因爲一些流行的C++標準庫（例如libstdc++和libc++）將sort例程實施爲插入排序和深度受限快速排序的組合。

這個想法是插入排序在接近排序的數組上非常快，而對於快速排序排序的輸入的直接實現會導致最壞情況的行爲。因此，組合算法首先應用快速排序算法對輸入進行部分排序，然後通過調用插入排序完成。

libc++如果輸入大小足夠小（但大於五個元素，因爲尺寸< = 5作爲特殊情況處理），插入排序也用於缺省排序。

Answer 4

HP/Microsoft std :: sort（）是introsort，具有深度參數的快速排序，如果深度過深，則切換到堆排序。

HP/Microsoft std :: stable_sort（）是timsort的一種。它使用插入排序來創建32個排序元素的組，然後使用自下而上的合併排序來合併組。

在附註中，自頂向下合併排序不在我知道的任何公共庫中使用。相反，內部（內存）和外部（磁盤）合併排序的公共庫版本都是自底向上合併排序的各種變體（如timsort）。然而，在課堂環境或網站文章中，您會看到更多自頂向下合併排序的示例，而不是自下而上合併排序。