插入排序與泡沫排序vs選擇排序的效率？

Question

我已經寫下來，插入排序比選擇排序比Bubble Sort快，並且它們的所有3的運行時間都是O（n^2），但是我怎麼說才能比較它們呢？

Answer 1

您可以比較的排序算法根據以下標準：

1. 時間複雜度（大O符號）。您應該注意到，最佳情況，最壞情況和平均運行時間可能具有不同的時間複雜度。例如Bubble Sort的最好情況只有O（n），當原始列表大部分按順序排列（不是很多元素不合適）時，它比選擇排序更快。
2. 記憶複雜。隨着n增長對列表進行排序需要多少內存？
3. 穩定性。該排序是否保留了具有相同排序值的元素的相對順序？ （例如，如果您按照價格對目錄項目列表進行排序，則某些元素可能具有相同的價格，如果該目錄最初按項目名稱的字母順序排序，那麼所選擇的排序algortihm是否將每個等價組內的字母排序物品。）
4. 需要的最佳/最差/平均數量的比較。比較操作昂貴時很重要。 （例如：比較通過某些模擬或其他複雜計算計算效率的替代設計的效率）。
5. 所需交換操作的最佳/最差/平均數量。交換操作昂貴時很重要。 （例如：分揀必須物理移動到船上甲板上的集裝箱）
6. 代碼大小。 Bubble-sort以其小代碼佔用而聞名。

Answer 2

有幾種方法可以看到插入/選擇/冒泡排序都在n^2時間內運行。

• 他們使用嵌套循環：N外循環，並且每個與N/2內循環平均
• 他們比較元素的所有對：有n *（N-1）/ 2對

以下是關於insertion/selection/bubble sort的運行情況的一些詳細分析。