插入排序

一、引言

插入排序（Insertion Sort）是一种简单直观的排序算法。通过构建有序序列，对未排序数据在已排序序列中从后向前扫描，找到相应位置并插入，直到整个数组有序。

二、算法思想

从第一个元素开始，视为已排序部分。
取出下一个元素，与已排序部分的元素进行比较。
如果该元素小于已排序部分的最后一个元素，则将其插入到已排序部分的适当位置。

重复上述步骤，直到整个数组排序完毕。

三、动图演示

首先将「第二个元素」和「第一个元素」进行「比较」，如果前者小于等于后者，则将后者进行向后「移动」，前者则执行插入；然后进行第二轮「比较」，即「第三个元素」和「第二个元素」、「第一个元素」进行「比较」，直到「前三个元素」保持有序。经过多轮「比较」和「移动」后，所有元素将按「升序」排列。

四、算法分析

时间复杂度：
- 假设「比较」和「移动」的时间复杂度为 O(1)。
- 插入排序有两个嵌套循环，外循环运行 n−1 次迭代，内部循环运行变得越来越短：
  - 当 i = 1 时，内层循环 1 次「比较」操作。
  - 当 i = 2 时，内层循环 2 次「比较」操作。
  - …
  - 当 i = n − 1 时，内层循环 n − 1 次「比较」操作。
- 总「比较」次数：1 + 2 + … + (n − 1) = n(n-1)/2。总时间复杂度为 O(n^2)。
空间复杂度：
- 算法执行过程中只有在「移动」变量时需要将变量存入临时变量 x，没有采用额外的空间，因此空间复杂度为 O(1)。

五、算法的优点

简单易懂，易于实现。
适用于小型数组或基本有序的数组。
稳定性好，不会改变相等元素的相对顺序。

六、算法的缺点

对于大型无序数组，效率较低。
不适合大规模数据排序。

七、优化方案

插入排序在众多排序算法中效率较低，时间复杂度为 O(n^2)。在进行插入操作之前，可以利用「二分查找」找到对应的位置。然而，插入过程的时间复杂度仍为 O(n)，所以优化的只是常数时间，最坏时间复杂度不变。

改进思路：在执行插入操作之前，利用「二分查找」找到需要插入的位置。
改进插入排序的思路是在执行插入操作之前，利用「二分查找」找到需要插入的位置。以下是详细的步骤：

改进思路

二分查找：
在已排序的部分数组中使用二分查找找到需要插入的位置。二分查找可以在 O(log n) 时间内找到插入位置。
元素移动：
找到插入位置后，将插入位置之后的元素向后移动一个位置，为插入元素腾出空间。
插入元素：
将当前元素插入到找到的位置。

实现步骤

遍历未排序部分：
对数组的每个未排序元素，从第二个元素开始，进行插入排序。
使用二分查找找到插入位置：
在已排序部分使用二分查找找到插入位置。
移动元素：
将插入位置之后的元素向后移动一个位置。
插入元素：
将当前元素插入到找到的位置。

代码示例

以下是一个使用二分查找优化的插入排序的 Python 实现：

import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        j = bisect.bisect_left(arr[:i], key)
        # 将插入位置之后的元素向后移动一个位置
        arr = arr[:j] + [key] + arr[j:i] + arr[i+1:]
    return arr

# 示例列表
list1 = [1, 2, 3, 5, 4, 6, 8, 7, 9, 5, 4, 1, 2, 3, 6, 0, 1, 5, 8]

# 调用二分查找优化的插入排序函数
sorted_list = binary_insertion_sort(list1)

# 打印排序后的列表
print("排序后的列表:", sorted_list)

解释

二分查找：
使用 bisect_left 方法在已排序部分查找插入位置，该方法返回应插入元素的位置，使得数组仍保持有序。
元素移动：
将插入位置之后的元素向后移动一个位置，为插入元素腾出空间。通过切片操作，将数组分为三部分：插入位置之前的部分、插入元素、插入位置之后的部分。
插入元素：
将当前元素插入到找到的位置。

这种改进将查找插入位置的时间复杂度从 O(n) 降低到 O(log n)，从而在一定程度上提高了插入排序的效率，尽管整体时间复杂度仍然是 O(n^2)，但在实际应用中可能会有性能提升。