插入排序比泡泡排序更好？

我正在修改考試。插入排序比泡泡排序更好？

想知道在什麼情況下插入排序比O（N^2）具有相同的平均複雜度情況下的氣泡排序更好。

我確實發現了一些相關的文章，但我無法理解它們。

有人會介意以簡單的方式解釋它嗎？

來源

2012-05-03 Jonathan

我猜你正在尋找的答案是here：

冒泡排序，也就是已經分類，除了極少數的元素列表上有效地使用。例如，如果只有一個元素沒有排序，則冒泡排序只需要2n個時間。如果兩個元素，爲了不，冒泡排序將只需要最多 3N時間...

和

插入排序是一個簡單的排序算法，對於小列表相對高效且多爲排序的列表，並且通常被用來作爲的更復雜的算法

來源

2012-05-03 09:30:47 MarcoS

所以例如一個主要排序的列表：例如[2,3,4,5,1] 冒泡排序需要4次交換和4次比較插入排序也需要4次交換和4次比較。所以有什麼區別？ – Jonathan

在這個特定的例子中沒有區別:) – MarcoS

冒泡的優點是在檢測出已經sorte速度部分d列表：

冒泡最佳設想：爲O（n）

然而，即使在這種情況下，插入排序好轉/相同的性能。

冒泡是，或多或少，只有理解和/或教學sortalgorithm的機制很好，但不會找到編程這幾天正確使用，因爲它的複雜性

O（N²）

意味着其效率在超過少數元素的列表上顯着降低。

來源

2012-05-03 09:40:57

「bubblesort只有理解和/或教授排序算法的機制」 - 甚至沒有，我會說。插入排序不是很難理解，編碼也不困難。泡泡排序有一個非常明確的優勢，那就是它對於沒有隨機訪問的特定存儲類型來說是最有效的排序。我認爲，鼓的存放位置只能在一個方向上以恆定速度轉動。然後它跳動插入排序，因爲插入排序需要「向後看」，這是非常緩慢的。這些優勢現在很少用於實際應用！ –

以下的事情來到我的腦海：

冒泡排序總是需要一個更傳過來陣列，以確定它是否排序。另一方面，插入排序不需要這個 - 一旦插入最後一個元素，算法就保證數組排序。
泡沫排序確實是n每次通過比較。插入排序確實少於n比較：一旦算法找到插入當前元素的位置，就停止進行比較並取下一個元素。
最後，從wikipedia文章報價：

冒泡排序也與不良的現代CPU的硬件交互。它需要至少兩倍於插入排序的寫入次數，兩倍於緩存未命中次數和漸近更多分支預測失誤。實驗由阿斯特拉罕在Java的字符串進行排序顯示冒泡排序比插入排序慢約5倍，比選擇慢40％排序

你可以找到鏈接到原始的研究論文在那裏。

來源

2012-05-03 10:16:52

謝謝Victor。我發現前兩個點非常有用。我現在明白這兩種算法之間的一個根本區別在於所需比較的數量。乾杯 – Jonathan

第二點似乎不正確。是的，有些算法可以做到但我認爲在正確的冒泡排序算法中，內循環在外循環的每次迭代中運行n-1，n-2，n-3 ....次。 –

您能否提供指向您不明白的相關文章的鏈接？我不確定他們可能會處理哪些方面。除此之外，理論上的區別可能在於，冒泡排序更適合於表示爲數組的集合（比表示爲鏈表的集合），而插入排序適合於鏈表。

的推理將是冒泡排序總是在一個時間，該時間在兩個瑣碎交換兩個項，陣列和鏈表（在陣列上更有效的），而插入排序插入在一個給定的列表，它是微不足道的一個地方鏈表，但涉及將數組中的所有後續元素向右移動。

這就是說，帶上一粒鹽。首先，排序數組在實踐中幾乎總是比排序鏈表更快。簡單地說，由於掃描列表已經有了巨大的差異。除此之外，將數組中的n個元素向右移動比執行n（甚至n/2）交換要快得多。這就是爲什麼其他答案正確地聲稱插入排序在一般情況下更爲優越，以及爲什麼我真的很想知道你閱讀的文章，因爲我沒有想到在情況A中說這種情況更好的簡單方法，而且情況更好B.

來源

2012-05-03 10:17:55

氣泡排序可能比氣泡排序更適合鏈接列表，但氣泡排序不適合數組，而不是插入排序對數組。 –

是的，也許我在最後一段中還不夠清楚。事情是，氣泡排序在數組上是概念上微不足道的，而插入排序不是（「將所有內容從x移動到右邊」）。儘管如此，這並不能使氣泡排序更快。 –

插入排序比泡泡排序更好？

回答

相關問題