Python排序算法之插入排序及其优化方案详解

排序算法是程序员必须学习的基本算法之一，而插入排序算法是其中较为简单和实用的一种，本文将详细介绍插入排序算法的原理以及其常见优化方案。

插入排序算法

插入排序算法是一种简单直观的排序算法，其基本思想是将一个待排序的序列分解成两个子序列，其中一个序列比另一个序列要少一个元素，然后将元素一个一个地从未排序的子序列中取出并插入到已排序的子序列中，直到未排序的子序列为空。

具体的实现步骤如下：

1. 通过一个循环逐个取出未排序子序列中的元素；

for i in range(1, len(lst)):
    current = lst[i]

1. 把当前元素插入到已排序子序列的合适位置中，从后向前遍历已排序子序列，依次比较已排序子序列中的元素，如果当前元素比已排序子序列中的某个元素大，则将该元素后移一位，直到找到合适的位置插入当前元素；

j = i - 1
while j >= 0 and lst[j] > current:
    lst[j + 1] = lst[j]
    j -= 1
lst[j + 1] = current

1. 重复之前的步骤，直到未排序的子序列为空。

完整的插入排序算法的代码如下：

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

插入排序算法的优化方案

尽管插入排序算法的实现简单易懂，但是其时间复杂度为$O(n^2)$，对于大量数据的排序可能会耗费较长时间，因此有必要对插入排序算法进行一些优化。

1. 二分查找插入

在已排序子序列中查找插入位置时，可以使用二分查找算法来加快查找速度。相比于从尾到头遍历已排序子序列，二分查找可以把时间复杂度降低到$O(log n)$。

具体的实现方式是，在已排序子序列中进行二分查找，找到第一个比当前元素大的位置，然后将当前元素插入到该位置之前。代码如下：

def insertion_sort(lst):
    for i in range(1, len(lst)):
        current = lst[i]
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if lst[mid] <= current:
                left = mid + 1
            else:
                right = mid - 1
        for j in range(i - 1, left - 1, -1):
            lst[j + 1] = lst[j]
        lst[left] = current

2. 缩小比较次数

在插入排序算法中，比较的次数会随着待排序序列的长度增加而增加。因此，可以通过一些技巧来减少比较的次数，从而提高算法的效率。

具体的实现方式有：

• 使用赋值代替交换

交换两个元素的值需要进行3次赋值操作，因此可以考虑使用直接赋值的方式来实现。

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

• 双重循环

在已排序子序列中，如果找到了一个比当前元素小的值，则可以直接跳出循环，从而减少比较次数。

python
def insertion_sort(lst):
for i in range(1, len(lst)):
current = lst[i]
for j in range(i - 1, -1, -1):
if lst[j] <= current:
break
lst[j + 1] = lst[j]
else:
lst[0] = current
continue
lst[j + 1] = current

示例说明

下面我们给出一个使用插入排序算法的实例：

lst = [5, 2, 3, 1, 4]
insertion_sort(lst)
print(lst)

输出为：

[1, 2, 3, 4, 5]

另外，我们再来看一下使用二分查找插入的实例：

lst = [5, 2, 3, 1, 4]
binary_insertion_sort(lst)
print(lst)

输出为：

[1, 2, 3, 4, 5]

从运行结果可以看出，使用了优化方案的插入排序算法比传统的插入排序算法要快，并且在处理较大的数据集时效果更加明显。