Python 中的插入排序是什么?
pythonserver side programmingprogramming
插入排序是对数组进行排序的简单方法。在这种技术中，数组实际上被分成已排序和未排序部分。从未排序部分中挑选一个元素并将其放置在已排序部分的正确位置。
数组元素从 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
