每日一练：插入排序

1. 概念及原理

??插入排序是一种简单直观的排序算法，其基本思想是将一个元素插入到已经排序好的部分，然后不断地重复这个过程，直到整个数组有序。下面是插入排序的算法原理：

• 初始状态： 数组被分为已排序和未排序两个部分，初始时已排序部分只包含第一个元素，未排序部分包含其余元素。
• 迭代过程： 从未排序部分选择一个元素，将其与已排序部分的元素依次比较，找到合适的位置插入。插入过程中，已排序部分中的元素不断向右移动，为新元素腾出位置。
• 重复： 重复上述过程，直到未排序部分为空，整个数组有序。

??下面是一个简单的例子，演示了插入排序的过程：
??初始数组：[12, 11, 13, 5, 6]

1. 第一次迭代：已排序部分[12]，未排序部分[11, 13, 5,
   6]。选择11，与12比较，交换位置，得到已排序部分[11, 12]，未排序部分[13, 5, 6]。
2. 第二次迭代：已排序部分[11, 12]，未排序部分[13, 5, 6]。选择13，与12比较，不需要交换位置，得到已排序部分[11, 12, 13]，未排序部分[5, 6]。
3. 以此类推，最终得到已排序的数组[5, 6, 11, 12, 13]。
   ??插入排序的时间复杂度为O(n^2)，其中n是数组的长度。这是因为对于每个元素，它需要与已排序部分的元素依次比较，最坏情况下，需要比较n次。在最优情况下，即数组已经有序时，时间复杂度为O(n)，因为不需要移动已排序部分的元素。插入排序是一种稳定的排序算法，适用于小型数组或基本有序的数组。

2. 示意图

3. 代码实现

def insertion_sort(arr):
    # 遍历数组，从第二个元素开始
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # 将比当前元素大的元素向右移动
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        # 将当前元素插入到正确的位置
        arr[j + 1] = key

# 示例用法
my_array = [12, 11, 13, 5, 6]
insertion_sort(my_array)

print("排序后的数组:", my_array)