Python 插入排序：原理、使用场景与实现方法

引言

插入排序（Insertion Sort）是一种简单直观且易于理解的排序算法，其工作原理类似于我们手动整理扑克牌的过程。通过构建一个有序序列，每次从未排序部分中取出一个元素并将其插入到已排序序列的正确位置，直到整个序列有序。尽管在处理大规模数据时效率较低，但对于小规模数据或部分有序的数据集，插入排序表现出了较好的性能。

一、插入排序原理

1. 构建初始有序序列：首先将数组的第一个元素视为已排序序列。
2. 逐个插入：从第二个元素开始，依次与已排序序列中的元素进行比较，找到合适的插入位置，并将其插入。
3. 重复上述过程：继续对剩余未排序元素执行相同的操作，直至所有元素都已排序到位。

二、插入排序步骤详解

假设有一个无序数组[5, 3, 8, 6, 7, 2]，按照插入排序的过程：

1. 第一轮：

   • 数组的第一个元素默认为已排序部分，即[5]
   • 将第二个元素3与5进行比较，发现3小于5，所以将3插入到5之前，得到[3, 5]

2. 第二轮：

   • 已排序部分为[3, 5]
   • 将第三个元素8与已排序部分的元素依次比较，无需移动，得到[3, 5, 8]

3. 继续这个过程，直到所有元素都已排序。

三、插入排序代码实现

以下是一个简单的插入排序实现：

def insertion_sort(arr):
    n = len(arr)

    # 遍历数组中的每个元素
    for i in range(1, n):
        current = arr[i]
        j = i - 1

        # 将当前元素与其左侧的已排序元素进行比较和交换
        while j >= 0 and arr[j] > current:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = current

    return arr

四、插入排序的使用场景

• 小规模数据集：对于数据量较小的情况，插入排序可以快速完成排序任务，尤其是当数据近乎有序时，其时间复杂度接近O(n)。
• 在部分场景下的优化：例如，当待排序数据基本有序时，插入排序能有效减少元素之间的比较次数，从而提高排序效率。

插入排序的时间复杂度达到O(n²)，因此插入排序也并非首选方案。