![](https://csdnimg.cn/release/download_crawler_static/89339917/bg1.jpg)
直接插入排序(Insertion Sort)是一种简单的排序算法,它的工作原理是通过构建有序序列,对于未排序
数据,在已排序序列中从后向前扫描,找到相应位置并插入。以下是一个使用 Python 实现的直接插入排
序算法:
python 复制代码
def insertion_sort(arr):
# 遍历从 1 到数组长度的元素
for i in range(1, len(arr)):
# 当前元素
key = arr[i]
# 将比 key 大的元素向后移动
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# 找到 key 的插入位置并插入
arr[j + 1] = key
return arr
# 测试代码
arr = [12, 11, 13, 5, 6]
print("原始数组:", arr)
insertion_sort(arr)
print("排序后的数组:", arr)
这个代码示例中,insertion_sort 函数接收一个数组 arr 作为参数,然后使用两个嵌套的循环来对数组进行
排序。外部循环从数组的第二个元素开始(索引为 1),因为数组的第一个元素可以认为已经是有序的(或
者说,它自身就是一个长度为 1 的有序数组)。内部循环从当前外部循环索引的前一个位置开始,向前比
较元素,如果当前元素(key)小于比较的元素,就将比较的元素向后移动一位。这个过程一直持续到找到
key 应该插入的位置,或者已经比较到数组的起始位置。最后,将 key 插入到正确的位置。
这个算法的时间复杂度在最坏情况下是 O(n^2)(当输入数组是逆序的时候),最好的情况下是 O(n)(当
输入数组已经是有序的时候),平均时间复杂度也是 O(n^2)。然而,对于小规模或几乎有序的数据,插
入排序通常比其他 O(n log n) 复杂度的排序算法(如快速排序、归并排序、堆排序等)更快。