插入排序

发表于 | 分类于

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

算法描述

插入排序在实现上，通常采用 in-place 排序（即只需用到 $O(1)$ 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤 2~5。

以列表 [54, 26, 93, 17, 77, 31, 44, 55, 20] 为例，插入排序的示例图如下：

  • 第一个元素 54 认为已排序。
  • 第二个元素 26 插入到 [54] 中， 得到排序 [26, 54]。
  • 第三个元素 93 插入到 [26， 54] 中，得到排序 [26, 54, 93]。
    …
  • 最后一个元素 20 插入到 [17, 26, 31, 44, 54, 55, 77, 93] 中，得到排序 [17, 22, 26, 31, 44, 54, 55, 77, 93]。
  • 排序完成。

Python 实现

算法的 Python 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
def insertion_sort(var):
    for index in range(1, len(var)):
        val_to_insert = var[index]
        pos = index
        while pos > 0 and var[pos - 1] > val_to_insert:
            var[pos] = var[pos - 1]
            pos = pos - 1
        var[pos] = val_to_insert


a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertion_sort(a)
print(a)  # output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 平均时间复杂度：$O(n^2)$
  • 最坏时间复杂度：$O(n^2)$