Python 插入排序

1. 简介

插入排序是一种简单直观的排序算法，它的基本操作是将一个元素插入到已排好序的部分列表中，从而得到一个新的、元素更多的已排好序的列表。插入排序的时间复杂度为O(n^2)，而且它是一种稳定的排序算法。

2. 算法思想

插入排序的算法思想很简单，它是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置将其插入。

具体步骤如下：
1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

以示例列表 [5, 2, 8, 6, 1, 3] 进行演示，初始时，我们认为第一个元素5已经被排序，然后我们取出下一个元素2，因为2小于5，所以将5移到下一位置，将2放在第一个位置。然后继续对剩下的元素进行插入排序，依次得到有序序列 [2, 5, 8, 6, 1, 3]。

3. Python 实现

下面是使用Python实现插入排序的示例代码：

def insertion_sort(lst):
    for i in range(1, len(lst)):
        current = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > current:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = current

# 测试代码
lst = [5, 2, 8, 6, 1, 3]
insertion_sort(lst)
print(lst)

运行结果为：

[1, 2, 3, 5, 6, 8]

4. 时间复杂度与稳定性分析

插入排序的时间复杂度是O(n^2)，其中n表示待排序序列的长度。具体分析如下：
– 最好情况下（即已经有序），插入排序只需要比较n-1次，时间复杂度为O(n)；
– 最坏情况下（即序列逆序），插入排序需要比较和交换n(n-1)/2次，时间复杂度为O(n^2)；
– 平均情况下，插入排序需要比较和交换约n(n-1)/4次，时间复杂度为O(n^2)。

插入排序是一种稳定的排序算法，即在排序过程中，相等元素的相对位置不会发生改变。