Python插入排序算法详解：原理、时间复杂度、空间复杂度

Python插入排序算法详解

插入排序是一种简单直观的排序算法，其工作原理类似于整理扑克牌。

算法原理

插入排序的基本思想是将未排序的元素逐个插入到已排序序列的正确位置，从而逐步构建有序序列。

具体步骤如下：

从第二个元素开始，将其视为'待插入元素'。
将'待插入元素'与其左侧已排序的元素逐个比较。
如果'待插入元素'小于左侧元素，则将左侧元素右移一位，继续与之前的元素比较。
重复步骤3，直到找到'待插入元素'的正确位置。
将'待插入元素'插入到正确位置。
重复步骤1-5，直到所有元素都已排序。

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
    return arr

时间复杂度

插入排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。

**最坏情况：*待排序数组为逆序时，需要进行 n(n-1)/2 次比较和移动操作。
**最佳情况：**待排序数组已经有序时，只需要进行 n-1 次比较，无需移动元素，时间复杂度为 O(n)。
**平均情况：**时间复杂度为 O(n^2)。

空间复杂度

插入排序的空间复杂度为 O(1)，因为它只需要常数级别的额外空间用于交换元素。无论输入规模如何增加，所需的额外空间保持不变，因此插入排序是一种原地排序算法。

总结

插入排序是一种简单易懂的排序算法，适用于小规模数据的排序，但在处理大规模数据时效率较低。其优点是实现简单、空间复杂度低，缺点是时间复杂度较高。