插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入,直到整个数组有序。以下是插入排序的 Python 代码实现:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# 测试示例
arr = [12, 11, 13, 5, 6]
print("原始数组:", arr)
insertion_sort(arr)
print("排序后的数组:", arr)
在上述代码中,insertion_sort
函数接受一个数组arr
。它使用两层循环来进行插入排序。外层循环控制排序的轮数,从第二个元素开始。内层循环用于找到正确的插入位置。
在内层循环中,我们将当前元素key
与已排序部分的元素进行比较,并根据比较结果进行元素的移动,为key
找到合适的插入位置。最后,将key
插入到正确的位置。
通过这种方式,每次内层循环结束后,已排序部分都会增加一个元素,直到整个数组都被排序。
希望这个示例对你有帮助!如果你对插入排序还有其他问题,或者想了解更多关于排序算法的内容,随时可以问我。😄