插入排序是对数组进行排序的简单方法。在这种技术中,数组实际上分为已排序和未排序部分。未排序部分中的元素被拾取并放置在已排序部分中的正确位置。
数组元素从 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] #获取每个元素 j = i-1 while j >= 0 and key &lit; arr[j] : #继续移动直到到达索引 0 或获得小于键的元素 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