資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中的插入排序是什麼？
插入排序是一種對陣列進行排序的簡單方法。在這種技術中，陣列被虛擬地分成已排序和未排序的部分。從未排序的部分中選擇一個元素，並將其放置在已排序部分的正確位置。
陣列元素從 1 到 n 遍歷。
如果位置 i 處的陣列元素大於其前驅元素，則不需要移動它。
如果位置 i 處的陣列元素小於其前驅元素，則需要將其向左移動，直到找到一個小於它的前驅元素，或者到達陣列的最左端位置。
示例
我們可以藉助一個示例更清楚地理解上述想法。假設我們有以下陣列：
| 4 | 6 | 1 | 7 | 2 | 5 |
我們需要從索引 1 開始遍歷陣列（因為索引 0 沒有前驅元素）。
**在索引 1 處** −
6 大於其前驅元素，因此無需執行任何操作。
| 4 | 6 | 1 | 7 | 2 | 5 |
**在索引 2 處** −
| 4 | 6 | 1 | 7 | 2 | 5 |
1 小於其前驅元素，因此我們需要將其向左移動，直到找到一個小於它的前驅元素，或者到達索引 0。在本例中，我們將到達索引 0。
| 4 | 6 | 1 | 7 | 2 | 5 |
**在索引 3 處** −
| 1 | 4 | 6 | 7 | 2 | 5 |
**在索引 4 處** −
| 1 | 4 | 6 | 7 | 2 | 5 |
將 2 向左移動，直到找到一個小於 2 的前驅元素。
| 1 | 2 | 4 | 6 | 7 | 5 |
**在索引 5 處** −
| 1 | 2 | 4 | 6 | 7 | 5 |
將 5 向左移動，直到找到一個小於 5 的前驅元素。
| 1 | 2 | 4 | 5 | 6 | 7 |
因此，我們得到了排序後的陣列。
插入排序是一種原地排序演算法，其時間複雜度為 O(n^2)，空間複雜度為 O(1)。
示例
def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] #get each element j = i-1 while j >= 0 and key &lit; arr[j] : #keep shifting until reaching index 0 or getting an element smaller than key arr[j + 1] = arr[j] j=j-1 arr[j + 1] = key arr = [4,6,1,7,2,5] insertionSort(arr) for i in range(len(arr)): print (arr[i],end=" ")
輸出
1 2 4 5 6 7
更新於: 2021-06-11
5K+ 次瀏覽
廣告