【算法练习】29：插入排序学习笔记

一、插入排序的算法思想

        原理：将一个无序的数据序列逐步转化为有序序列。算法将待排序的数组分为两个部分已排序部分和未排序部分。

        时间复杂度：插入排序的时间复杂度在最坏、平均和最好情况下的表现相同，均为 ，其中 n 是待排序数组的长度。这是因为无论输入数组如何分布，插入排序都需要对每个元素进行一次遍历（寻找插入位置），并且在最坏情况下，每次插入可能都需要移动已排序部分的所有元素。因此，总的操作次数与数组长度的平方成正比。

        空间复杂度：插入排序是原地排序算法，它不需要额外的存储空间来保存数据副本。在进行元素插入时，只需要常数级别的临时空间用于交换元素或者存储中间值。因此，插入排序的空间复杂度为，即空间复杂度与输入数组的大小无关。

        稳定性：稳定，在插入排序过程中，当遇到相等键值的元素时，只会将待插入元素放置在已排序部分中相等元素的后面，不会改变相等元素之间的原有顺序，故保持了稳定性。

二、插入排序的算法步骤

1. 初始化阶段：一开始时已排序部分仅包含数组的第一个元素，被视为已排序。
2. 遍历数组：每次从未排序部分取出一个元素，将其按正确的顺序插入到已排序部分的适当位置。
3. 比较元素：从待插入元素开始，向前遍历已排序部分，比较待插入元素与当前元素的大小，若待插入元素较小，则将当前元素向后移动一位，直到找到合适的位置或到达已排序部分的起始处。然后将待插入元素插入到这个位置，保证插入后已排序部分依然保持有序。
4. 重复执行：随着每次迭代，已排序部分不断增长，未排序部分相应减小，直到整个数组变为已排序状态。

        本文是自己的算法学习笔记，这里超级推荐一个开源算法项目，链接我放在这里了！非常感谢开源大佬：《hello算法》插入排序

三、基于Python的插入排序实现

def insertion_sort(arr):
    # 遍历从第二个元素开始到最后一个元素
    for current in range(1, len(arr)):
        # 当前待插入元素
        key = arr[current]
        # 已排序部分的最后一个元素的索引
        sorted_end = current - 1
        
        # 将当前元素与已排序部分的元素进行比较并移动
        while sorted_end >= 0 and key < arr[sorted_end]:
            arr[sorted_end + 1] = arr[sorted_end]
            sorted_end -= 1
        
        # 在正确位置插入当前元素
        arr[sorted_end + 1] = key

# 示例
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print(arr)  # 输出: [1, 2, 3, 4, 5, 6]