© BEST-BACKGROUNDS/Shutterstock.com
在對數據數組進行排序時，您可以使用多種排序算法。最容易使用的算法之一是插入排序，因為它相對簡單和直觀。繼續閱讀以通過示例探索插入排序的確切含義、它的實現方式以及它的用途。
什麼是插入排序?
插入排序是一種排序算法，可用於對數組進行排序的方法之一。它的工作方式並不太難理解，可以在很大程度上與您對一副紙牌進行排序的方式進行比較。
在在這種情況下，我們首先假設牌組中的第一張牌已經排序。然後，我們選擇一張未排序的卡片並對其進行排序。這是通過將它與第一張卡片進行比較來完成的。如果所選卡片大於排序卡片，則將其放置在第一張卡片右側的位置。如果有問題的卡片小於排序的卡片，則將其放置在左側的位置。
這個過程一直持續到所有未分類的卡片都被放置在正確的位置。插入排序的功能非常相似。每個未排序的數據值都通過相同類型的迭代過程進行排序。
由於插入排序是一種非常簡單的算法，因此它最適用於相對較小的數據集，以及那些已經排序的數據集。這樣，它被稱為自適應且高效的算法。接下來，我們將介紹插入排序背後的理論。
插入排序背後的算法
插入排序方法可以用以下偽代碼簡潔地表示:
p> insertionSort(array) 標記第一個元素為每個未排序的元素 X’提取’j 的元素 X-lastSortedIndex 下降到 0 如果當前元素 j > X 將排序的元素向右移動 1 個中斷循環並在此處插入 X end insertionSort
簡單來說，這意味著假定第一個元素已排序。每個後續元素都與第一個元素進行比較。如果它小於已排序的元素，它將向下移動到第一個或第 0 個位置。如果它更大，它就向右移動一個位置。迭代一直持續到所有元素都已排序。
插入排序的內部工作原理
現在我們已經介紹了插入排序的工作原理及其背後的理論，是時候說明該過程了用合適的數組。如果我們考慮以下數據集:
我們可以假設第一個元素 10 已經排序。在此之後，我們將第二個元素 14 單獨存儲。比較 14 和 10，我們可以看到它更大，所以它保留了它作為第二個元素的位置。這是第一次迭代，稱為第一遍。第一個元素 10 存儲在子數組中。
其中 green=排序數組
對於第二遍，我們繼續處理第三個元素，即 5。這是與前面的元素相比。我們可以看出它比前一個元素 14 小，所以它與 14 交換位置。
然後算法將它與已排序子數組中的元素進行比較。 5 也小於 10，所以它被移動到子數組的開頭。排序後的數組現在有 2 個元素 — 5 和 10。
現在，我們繼續進行第三遍。在本例中，7 是所選元素。它小於 14，所以它向左移動了一個位置並進入排序數組。但是，這不是正確的位置，因為 7 小於 10 但大於 5。因此，它向左移動了另一個位置。
對於第四遍，我們正在查看第四遍元素，即 14。這已經排序，所以現在排序後的數組包括 5、7、10 和 14。
最終結果
最後，對於第五遍，我們取第五個元素，也就是 1。這顯然小於 14，所以交換了位置。也小於10，所以又調換了位置。這還會繼續兩次，因為 1 是數組中的最小元素。因此，我們最終得到一個排序數組如下:
插入排序的實現
插入排序可以用多種編程語言實現，從C、C#到C++到 Java、Python、PHP 和 Javascript。出於說明目的，我們將使用 Python。整個過程可以用下面的代碼表示:
def insertionSort(arr): if (n:=len(arr))=1: return for i in range(1, n): key=arr[i ] j=i-1 while j >=0 and key arr[j]: arr[j+1]=arr[j] j-=1 arr[j+1]=key arr=[10, 14, 5, 7, 1] insertionSort(arr) print(arr)
首先，我們將插入排序定義為數組 (arr) 的函數。然後，我們說，如果數組的長度為 1 或更小，則返回該數組。接下來，我們將長度為 n 的數組中第 i 個位置的元素定義為鍵。
我們對計算施加了約束，以便僅在 j 大於或等於索引 0 時對其進行操作。J 被認為是我們正在查看的任何項目左側的值，因為每 j=i-1。如果其值大於鍵，則其位置向右移動。
最後一行，arr[j+1]=key，指示這個 j 值右邊的值成為新的鍵。因此，必要時交換其餘數字。這個過程然後從頭開始繼續，直到所有數字都正確排序。
Python 中的插入排序:實現
讓我們看看它是如何在 Spyder 環境中用 Python 實現的。我們將使用與之前相同的數組來清楚地說明這一點。請參閱下面的實施代碼:
在 Python 中實現插入排序。
©”TNGD”.com
一個關鍵要點是縮進在使用 Python 時至關重要。如果縮進使用不當，您將收到如下所示的錯誤消息。
收到錯誤消息。
©”TNGD”.com
插入排序的最佳和最差用例
雖然插入排序有很多用途，但與任何算法一樣，它也有最好和最壞的情況。這主要歸結為時間和空間複雜度。
插入排序的時間複雜度
下表描述了每種情況下的時間複雜度:
可以看到，在最好的情況下，時間複雜度等於O(n)。這意味著不需要排序，因為數組已經排序。因為算法必須依次檢查每個值才能確定數組已排序，所以時間複雜度是線性的。也就是說，複雜度與輸入的大小成線性比例。
然而，在平均和最壞的情況下，複雜度等於 O(n2)。一般的情況是數組中的元素是混亂的，既不升序也不降序。在最壞的情況下，元素將需要反向排序。
這是因為它們已經按升序或降序排列，而您需要相反的順序。這種類型的複雜性稱為二次時間，因為它取決於 n2。例如，如果輸入的大小為 4，則操作數將為 16。
插入排序的空間複雜度
另一種複雜度是空間複雜度。這是指運行算法所需的內存空間量。 O(1) 的複雜性意味著所需的內存量是恆定的，與輸入大小無關。
這在插入排序的情況下是正確的，因為您在每個操作中只使用一個臨時變量。換句話說，一次只對一個值進行排序，因此內存使用是恆定的。
需要注意的是，插入排序被認為是一種穩定的算法，這意味著具有相同值的元素的相對順序是保存。如果您需要保留特定元素的順序，或者需要對已經部分排序的數組進行排序，這將很有幫助。這是因為如果元素與鍵等效，則它們不會與鍵交換。
總結
我們已經介紹了什麼是插入排序以及何時適合使用它。除此之外，我們還考慮了它的時間和空間複雜性，並展示了它在 Python 中的代碼表示和實現。如果您要對相對較小的數組進行排序，尤其是一些元素已經排序的數組，插入排序是最好的方法之一。
Up Next
什麼是插入排序，它是如何工作的? (With Examples) FAQs (Frequently Asked Questions)
什麼是插入排序?
插入排序是一種算法，可用於將數據集排序為升序或降序。這類似於您對手中的一副紙牌進行排序的方式，因為第一個元素被認為是已排序的。
然後將每個後續元素與第一個元素進行比較並放置在正確的位置，要么將其留在原處，要么將其向右移動一個位置。對每個元素重複這個過程，然後從頭開始繼續這個過程，直到所有元素都排序完畢。
什麼時候應該使用插入排序?
插入排序最適用於小數據集和值已經部分排序的數據集。
哪些編程語言可以實現插入排序?
很多C、C++、C#、Java、Javascript、PHP、Python 等編程語言可以實現插入排序。
插入排序有什麼優點?
插入排序的優點是簡單，鍵的相對順序不變，對小數據集效率高，而且可以邊接收邊排序。
插入排序是如何優化的?
插入排序是通過創建一個存儲子數組來優化的，其中臨時存儲排序後的值。這意味著不需要在每次迭代期間完全交換數組元素，因為一次交換一個元素。
插入排序有多少次迭代?
對於長度為 n 的數組，需要 n-1 次迭代才能對整個數組進行排序。
如何修改插入排序?
插入排序可以通過使用二進制插入排序進行修改。這類似於插入排序，因為它是一種穩定的算法，但它減少了需要進行的比較次數。
時間複雜度從 O(n) 降低到 O(log n)，因為它使用二進制搜索而不是線性搜索。將每個值與已排序子數組中的值進行比較，以確定哪個值剛好大於所選值。這減少了操作次數。
插入排序的缺點是什麼?
插入排序不適合特別大的數據集，因為平均和最壞情況下的時間複雜度是二次的。
插入排序的替代方案是什麼?
對於大型和混亂的數據集，更合適的替代方案是快速排序、歸併排序還是堆排序。
插入排序是穩定的算法嗎?
是的，插入排序算是穩定的排序算法，因為如果元素等於鍵，則元素保持不變。如果元素彼此等價，它們的順序也會被保留。