插入排序算法（Python版）

1、什么是插入排序算法

插入排序算法是一种简单直观的排序算法，它的基本思想是将一个元素逐个插入到已排序的序列中，从而构建出完整的有序序列。

插入排序算法的时间复杂度为O(n^2)，其中n为待排序序列的长度。虽然插入排序在大规模数据上可能不如快速排序或归并排序等算法快速，但对于小规模或部分有序的数据，插入排序具有稳定性和简单性的优势。

2、具体步骤

1. 从第二个元素开始，将当前元素视为已排序部分，将它与已排序的部分依次比较。
2. 如果当前元素小于已排序部分的某个元素，则将这个元素后移一位，为当前元素腾出插入的位置。
3. 将当前元素插入到正确的位置，使得插入后的序列仍然保持有序。
4. 重复以上步骤，直到所有元素都被插入到正确的位置，完成排序。

3、代码示例

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 示例用法
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("排序后的数组:", arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这段代码定义了一个名为insertion_sort的函数，用于对输入的数组进行插入排序。排序过程中，从第二个元素开始（索引为1），将当前元素与已排序的部分进行比较并插入正确的位置，直到整个数组排序完成。