Swift Algorithm Club：插入排序

发表于

原文：Insertion sort

插入排序

目标：排序一个数组从底到高（或从高到底）。

给你一个数字数组并需要把它们排成正确的顺序。插入排序算法的工作步骤：

  • 把所有的数字放到堆中。这个堆是无序的；
  • 从堆中取出一个数字。取哪个数字都无所谓，但最简单的做法是从堆顶取；
  • 把这个数字插入到新的数组中；
  • 从无序堆中取出下一个数字并同样的插入到数组中。它在第一个被选出来的数字的前面或者后面，这样这两个数字排好序了；
  • 再次，从无序堆中取出数字插入到新数组相应的有序位置；
  • 不断重复直到无序堆中没有任何数字。堆为空时结束，并数组也排好序了。

这就是为什么被称为“插入”排序的原因，因为你从堆中取出一个数字然后把它插入到数组中相应的有序位置。

例子

比如说，这是一个需要排序的[8, 3, 5, 4, 6]。这是我们的无序堆。

取出第一个数字，8,并插入到新数组。这个数组中什么都没有，所以这步很简单。现在这个有序数组为[8]，堆为[3, 5, 4, 6]。

从堆中取出下一个数字，3，并且插入到有序数组中。它应该放在8前面，所以有序数组现为[3, 8]，堆为[5, 4, 6]。

从堆中取出下一个数字，5，并且插入到有序数组中。它应该放在3 与8之间。有序数组为[3, 5, 8]，堆为[4, 6]。

重复这个过程直到堆为空。

In-place（就地） 排序

上面的解释使它看起来好像你需要两个数组：一个是无序堆，另一个用来装排好序的数字。

不过你可以In-place（就地）排序，不需要额外的数组。你只要记录哪部分是已经排好序的数组和哪部分是未排序的堆。

开始时，这个数组是[8, 3, 5, 4, 6]。这|竖线显示在排好序部分的末端，在无序堆的首端：

1
[| 8, 3, 5, 4, 6]

上面显示了排序部分为空，而无序堆从8开始。

处理第一个数字后，变为：

1
[8 | 3, 5, 4, 6]

排序部分是[8]，无序堆为[ 3, 5, 4, 6 ]。|竖线向右挪了一位。

下面展示了在排序过程中数组内容的变化：

1
2
3
4
5
6
[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]

每一步，|都向后移动一步。正如你所看到的，数组起始到|之简的部分都排好序的。无序堆减一，而排序部分增一。直到无序堆为空，不再有无序数字可移动。

怎样插入

每一步，你取出无序堆最前面的数字，然后插入到排序数组部分中。你必须把这个数字放到排序部分的合适位置。这一步怎么做呢？

比如说，我们已经完成了前面几步，然后数组就像这样：

1
[ 3, 5, 8 | 4, 6 ]

下一个要排序的数字是4。我们需要把它插入到排序部分[ 3, 5, 8 ]数组的某位置。

这里有一个方法可以实现它：查看前一个元素，8。

1
2
[ 3, 5, 8, 4 | 6 ]
        ^

是否大于4？大于，所以4应该在8的前面。交换它们的位置得到：

1
2
3
[ 3, 5, 4, 8 | 6 ]
        <-->
        交换后

还没完。前面的新元素，5，又大于4。同样的，交换它们：

1
2
3
[ 3, 4, 5, 8 | 6 ]
     <-->
    交换后

再次，查看前面的元素。3大于4？不大于，这意味着4已经完成操作。开始部分的数组又变为有序了。

这是内循环插入排序算法的描述，你会在下一章看到。它采用数字交换的方法，把数字从截头部插入到有序部分。

代码

这里采用Swift实现插入排序：

1
2
3
4
5
6
7
8
9
10
11
func insertionSort(_ array: [Int]) -> [Int] {
  var a = array	//1
  for x in 1..<a.count {	//2
    var y = x							
    while y > 0 && a[y] < a[y-1] {	//3
      swap(&a[y-1], &a[y])
      y -= 1
    }
  }
  return a
}

使用Playground测试上面的代码，例如：

1
2
let list = [10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)

这里解释下，上面的代码怎么运行：

  1. 复制array。这一步是必须的，因为我们不能直接修改参数变量array。就像Swift自带的sort()，insertionSort()函数将返回原始数组复制后的排序数组。
  2. 这里有两个循环在这个函数中。外循环依次查询数组中的所有元素；用来从堆中取出最上面的数字。x变量用来标识排好序部分的结尾与堆起始位置（即|的位置）。记住，任何时刻，数组的起始 — 从0到x — 总是排好序的。剩余的，从x到最后一个元素，是无序堆。
  3. 内循环从x下标的元素开始。这是堆最顶端的数字，它可能小于前面所有元素。内循环一步步向后通过排序数组；每次查找前一个元素是否大于它，如果大于则交换位置。当内循环完成后，数组起始部分们又变成有序了，并且有序部分增加一个元素。

注意： 外循环从下标1开始而不是0。移动第一个元素从堆到排序部分，没有发生实质的变化，所以我们跳过了它。

去掉交换

上面的版本工作的很好，不过可以删除swap()来提升一些速度。

你已经知道，我们通过交换数字来移动下一个元素到排序位置：

1
2
3
4
5
6
7
[ 3, 5, 8, 4 | 6 ]
        <-->
        交换
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     交换

替代的做法是，我们只要向右挪动这些元素一个位置，然后复制一个新数字到目标位置即可：

1
2
3
4
5
6
7
8
9
10
11
[ 3, 5, 8, 4 | 6 ]   记住 4
           *
[ 3, 5, 8, 8 | 6 ]   把 8 向右挪动
        --->
        
[ 3, 5, 5, 8 | 6 ]   把 5 向右挪动
     --->
     
[ 3, 4, 5, 8 | 6 ]   复制 4 到这个位置
     *

在代码中，就像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
func insertionSort(_ array: [Int]) -> [Int] {
  var a = array
  for x in 1..<a.count {
    var y = x
    let temp = a[y]
    while y > 0 && temp < a[y - 1] {
      a[y] = a[y - 1]                // 1
      y -= 1
    }
    a[y] = temp                      // 2
  }
  return a
}

//1行的代码是挪动前一个元素一个位置。在内循环的最后，y是新元素插入到有序数组部分的目标位置，//2行表示复制这个数字到目标位置。

增加泛型

如果可以用来排序其他类型，那就更好了。我们可以给数组的数据类型添加泛型并使用用户提供（user-supplied）函数（或闭包）去执行小于号比较，这只需要改变函数中两个地方。

函数的参数签名变为：

1
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {

数组为类型[T],T表示通用的占位类型。现在insertionSort()函数可以接受任何类型的数组了，无论它包含数字，字符串，或者其他对象。

新参数isOrderedBefore: (T, T) -> Bool是一个函数，这个函数比较两个T对象，当第一个对象在第二个对象前面时返回true，相反时，返回false。这跟Swift内置函数sort()的做法一样。

其他只要改变的地方在内循环中，现在改为：

1
while y > 0 && isOrderedBefore(temp, a[y-1]) {}

我们调用isOrderedBefore()函数来替换temp < a[y-1]。这样是完全相同的，除了我们现在可以比较任何类型的对象，不仅仅只是数字。

在playground中做如下测试：

1
2
3
let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)

<与>决定排序顺序，相当于底-高，高-底。

当然，你也可以使用其他对象进行排序，比如字符串：

1
2
let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)

或者，较复杂的对象：

1
2
let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }

闭包告诉insertionSort()函数，使用对象的priority属性来排序。

插入排序是稳定排序。稳定排序是指当元素中有相同的元素，当排序完成后相同元素将保持原有的顺序。这不是很重要，对于简单值来说，比如：数字和字符串，不过对于较复杂的对象来说非常重要。在上面的例子中，如果两个对象有相同的priority，不管他们的属性的值是多少，他们都不会交换位置。

性能

如果是已经排好序的数组那么插入排序非常的快。这听起来显而易见，不过这对于所有的搜索算法来说不太正确。在实际情况中，大部分数据已经排好序了，所以在这种情况下，插入排序工作的不错。

插入排序的最坏和平均的时间复杂度为O(n^2)。因为函数中有两个嵌套循环。其他排序算法，比如快速排序与合并排序的时间复杂度为O(n log n)，它们输入数据很快。

在排好序的小数组使用插入排序是非常快的。有些标准库中，当数组分配粒度为10或更小时，使用插入排序代替快速排序。

我做过一个快速测试，来比较我们的insertionSort()与Swift内置的sort()。使用大小大约为100的数组，它们的时间花费差距非常小。然而，如果你输入一个比较大的数组，O(n^2)比O(n log n)开始有非常大的性能差距，并且插入排序不能工作。

参考阅读

Insertion sort on Wikipedia

Written for Swift Algorithm Club by Matthijs Hollemans