什麼是插入排序演算法？

原標題 |Everything you need to know about Insertion Sort algorithm

作者 |Sanjula Madurapperuma

譯者 | david95（研發工程師）

介紹

大家好，我是Sanjula，在這個教程中，我希望告訴你一些關於插入排序演算法的知識，包括：

什麼是插入排序

為什麼插入排序很重要

插入排序的性能

插入排序的原理

Java代碼實現

讓我們開始吧！

什麼是插入排序？

它是一種簡單的排序演算法，只需遍歷一次數組即可完成排序。

為什麼插入排序很重要？

插入排序有幾個優勢：

演算法簡單好理解

相同的值不需要交換順序

數組可以一邊增加內容，一邊排序

對小數據集很高效，特別是和其他演算法相比，比如有些時間複雜度要到O(n2)

它帶來額外的內存開銷小，只有一個常數，時間複雜度是O(1)。

插入排序的性能

最差的性能是 O(n2)的比較和交換

最好的性能是O(n) 的比較和O(1)的交換

平均的性能是O(n2) 的比較和交換

插入排序的原理

在每次迭代中，它對比當前元素和下一個元素，檢查當前元素是否比它大。

如果大的話，就原地不動，進行下一個元素。如果小的話，它會一直向前比對，一直找到正確的位置。

Java代碼實現

提示：看代碼之前，你可以自己試著動手實現.

恭喜你，你現在應該了解插入排序演算法了。

如果上面的代碼你認為有問題，可以通過這個github聯繫我：

https://gist.github.com/sanjulamadurapperuma/25677635f216b9fa858d8051140e47f2

希望這篇文章能幫到你，感謝閱讀！

本文編輯：王立魚

英語原文：https://www.freecodecamp.org/news/everything-you-need-to-know-about-insertion-sort-algorithm/

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！