Python算法——插入排序

插入排序（Insertion Sort）是一种简单但有效的排序算法，它的基本思想是将数组分成已排序和未排序两部分，然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效，特别适用于对部分有序的数组进行排序。本文将详细介绍插入排序的工作原理和Python实现。

插入排序的工作原理

插入排序的基本思想是将数组分成两部分：已排序部分和未排序部分。在开始时，已排序部分只包含数组的第一个元素，而未排序部分包含剩余的元素。算法的工作过程如下：

1. 从未排序部分选择一个元素，将其插入到已排序部分的正确位置。
2. 重复上述步骤，直到未排序部分为空。
   插入排序的核心思想是每一步将一个元素插入到已排序部分，并确保已排序部分仍然保持有序。这一过程逐渐扩大已排序部分，缩小未排序部分，直到整个数组有序。

下面是一个示例，演示插入排序的过程。我们以升序排序为例：

原始数组：[12, 11, 13, 5, 6]

1. 第一步：已排序部分 [12]，未排序部分 [11, 13, 5, 6]，将 11 插入已排序部分。
2. 第二步：已排序部分 [11, 12]，未排序部分 [13, 5, 6]，将 13 插入已排序部分。
3. 第三步：已排序部分 [11, 12, 13]，未排序部分 [5, 6]，将 5 插入已排序部分。
4. c第四步：已排序部分 [5, 11, 12, 13]，未排序部分 [6]，将 6 插入已排序部分。

Python实现插入排序

下面是Python中的插入排序实现：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
1
2
3
4
5
6
7
8

• arr 是待排序的数组。
• 外层循环 for i in range(1, len(arr)) 用于遍历未排序部分的元素。
• 内层循环 while j >= 0 and key < arr[j] 用于找到元素的正确位置。
• key 是当前待插入的元素，将它插入到已排序部分的正确位置。

示例代码

下面是一个使用Python进行插入排序的示例代码：

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

# 测试排序
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("排序后的数组:", arr)
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度

插入排序的时间复杂度为 O(n^2)，其中 n 是数组的长度。尽管插入排序不如高级排序算法（如快速排序和归并排序）高效，但它在小型数据集上表现良好，尤其在数组部分有序的情况下。

总之，插入排序是一种简单但有效的排序算法，通过将元素逐一插入到已排序部分，实现了排序数组的目标。了解插入排序有助于理解排序算法的基本原理，并为选择适当的排序算法提供了基础。