跳到主要内容

插入排序

什么是插入排序？​

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理类似于我们整理扑克牌的方式：每次从未排序的部分中取出一个元素，将其插入到已排序部分的适当位置，直到所有元素都被排序。

插入排序的时间复杂度为 O(n²)，在数据量较小或部分有序的情况下表现较好。尽管它的效率不如快速排序或归并排序，但由于其实现简单，插入排序在某些场景下仍然非常有用。

插入排序的工作原理​

插入排序的核心思想是将数组分为两部分：已排序部分和未排序部分。初始时，已排序部分只包含数组的第一个元素，而未排序部分包含剩余的元素。然后，算法逐步从未排序部分取出元素，并将其插入到已排序部分的正确位置。

逐步讲解​

  1. 初始状态：假设我们有一个数组 [5, 3, 8, 4, 6]。初始时，已排序部分为 [5]，未排序部分为 [3, 8, 4, 6]。
  2. 第一次迭代：取出未排序部分的第一个元素 3，将其插入到已排序部分 [5] 中。由于 3 < 5，我们将 3 插入到 5 的前面，得到已排序部分 [3, 5]，未排序部分为 [8, 4, 6]。
  3. 第二次迭代：取出未排序部分的第一个元素 8，将其插入到已排序部分 [3, 5] 中。由于 8 > 5，我们将 8 插入到 5 的后面，得到已排序部分 [3, 5, 8]，未排序部分为 [4, 6]。
  4. 第三次迭代：取出未排序部分的第一个元素 4，将其插入到已排序部分 [3, 5, 8] 中。由于 4 介于 3 和 5 之间，我们将 4 插入到 3 和 5 之间，得到已排序部分 [3, 4, 5, 8]，未排序部分为 [6]。
  5. 第四次迭代：取出未排序部分的第一个元素 6，将其插入到已排序部分 [3, 4, 5, 8] 中。由于 6 介于 5 和 8 之间，我们将 6 插入到 5 和 8 之间，得到已排序部分 [3, 4, 5, 6, 8]，未排序部分为空。

最终，数组 [5, 3, 8, 4, 6] 被排序为 [3, 4, 5, 6, 8]。

代码示例​

以下是用 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
    return arr

# 示例
arr = [5, 3, 8, 4, 6]
sorted_arr = insertion_sort(arr)
print(sorted_arr)  # 输出: [3, 4, 5, 6, 8]

输入和输出​

  • 输入：[5, 3, 8, 4, 6]
  • 输出：[3, 4, 5, 6, 8]

实际应用场景​

插入排序在以下场景中非常有用：

  1. 小规模数据：当数据量较小时，插入排序的效率较高，且实现简单。
  2. 部分有序数据：如果数据已经部分有序，插入排序的效率会显著提高。
  3. 在线算法：插入排序是一种在线算法，即它可以逐步处理输入数据，而不需要一次性加载所有数据。
提示

在实际应用中，插入排序常用于对小型数据集进行排序，例如在嵌入式系统中处理传感器数据。

总结​

插入排序是一种简单且易于实现的排序算法，特别适用于小规模数据或部分有序的数据集。尽管它的时间复杂度为 O(n²)，但在某些特定场景下，插入排序仍然是一个不错的选择。

附加资源与练习​

  • 练习：尝试用你喜欢的编程语言实现插入排序，并测试其对不同数据集的排序效果。
  • 进一步学习：了解其他排序算法，如快速排序、归并排序和堆排序，并比较它们与插入排序的优缺点。
警告

虽然插入排序在某些场景下表现良好，但在处理大规模数据时，建议使用更高效的排序算法。