【译】Swift算法俱乐部-插入排序

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Club 是raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+️:star:️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

:octopus: andyRon/swift-algorithm-club-cn 是我对Swift Algorithm Club，边学习边翻译的项目。欢迎有兴趣学习算法和数据结构，有时间的小伙伴一起参与翻译，欢迎issue，或者直接提交pull request。

本文的翻译原文和代码可以查看:octopus: swift-algorithm-club-cn/Insertion Sort

目标：把数组从低到高（或从高到低）排序

您将获得按正确的顺序排列一系列数字。插入 排序 算法的工作原理如下:

• 把一系列数字放在一个未排序的堆里。
• 从堆中挑选一个数字。 你选择哪一个并不重要，但从堆顶挑选是最容易。
• 把这个数插入一个新的数组。
• 从未排序堆中再选择一个数字，并将其插入之前的数组中。 这个数字在第一个数字之前或之后，所以现在这两个数字被排序。
• 再从堆中选择一个数字，并将其插入到数组中的正确排序位置。
• 继续这样做，直到堆里没有数字。 最终得到一个空堆和一个排序的数组。

这就是为什么这被称为“插入”排序，因为你从堆中取一个数字并将其插入数组中的正确排序位置。

例子

假设这边有需要排序的一些数字 [ 8, 3, 5, 4, 6 ] 。

选择第一个数字 8 ，然后将其插入新数组中。 新数组是空的，所以插入很容易。 排序的数组现在是 [8] ，堆是 [3,5,4,6] 。

从堆中选择下一个数字 3 ，然后将其插入到已排序的数组中。 3 应该在 8 之前，所以排序的数组现在是 [3,8] ，而堆被缩减为 [5,4,6] 。

从堆中选择下一个数字 5 ，然后将其插入到已排序的数组中。 5 介于 3 和 8 之间。 排序的数组是 [3,5,8] ，堆是 [4,6] 。

重复上面的过程直到堆为空。

原地排序

译注： 原地排序 就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。包括：希尔排序、冒泡排序、插入排序、选择排序、堆排序、快速排序。

上面的解释使你看起来需要两个数组：一个用于存放未排序的堆，另一个用于存放按次序排好的数字。

但您可以执行 原地 插入排序，而无需创建单独的数组。 您只需追踪数组的哪个部分已经排序，哪个部分是未排序。

最初，数组是 [8,3,5,4,6] 。 | 条显示已排序部分的结束位置和堆的开始位置：

[| 8, 3, 5, 4, 6 ]
复制代码

这表明排序的部分是空的，堆开始于 8 。

处理完第一个数字后，结果为：

[ 8 | 3, 5, 4, 6 ]
复制代码

排好序的部分是 [8] ，未排序的堆是 [ 3, 5, 4, 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 |]
复制代码

每一步， | 条向右移动一个位置。 如您所见，数组的开始到 | 部分总是排好序的。堆缩小一位置，排序部分增加一位置，直到堆变为空的，没有更多未排序的数字为止。

怎么插入

每一步，您从未排序堆中选择最顶部的数字，并将其插入到数组的已排序部分。 但必须将该数字插入适当的位置，以便数组的从头开始保持排序。 这是如何运作的？

假设我们已经完成了前几个元素，数组看起来像这样：

[ 3, 5, 8 | 4, 6 ]
复制代码

要排序的下一个数字是 4 。 我们需要将它插入到已经排好序的 [3,5,8] 中。

一种方法是：查看前一个元素 8 。

[ 3, 5, 8, 4 | 6 ]
        ^
复制代码

前一个元素比 4 大吗？ 是的，所以 4 应该在 8 之前。 我们交换这两个数字得到：

[ 3, 5, 4, 8 | 6 ]
        <-->
        交换
复制代码

还没有完成。 新的前一个元素 5 也大于 4 。 我们还需交换这两个数字：

[ 3, 4, 5, 8 | 6 ]
     <-->
     交换
复制代码

再看一下前面的元素。 3 大于 4 吗？ 不大于， 这意味着我们完成了数字 4 保持排序的插入。

下一节将对插入 排序算法 的内部循环的进行描述，通过交换数字将数字从堆的顶部插入到已排序的部分。

代码

下面插入排序的Swift实现：

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
            a.swapAt(y - 1, y)
            y -= 1
        }
    }
    return a
}


复制代码

代码在 playground 里测试：

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

代码工作原理：

1. 先创建一个数组的拷贝。因为我们不能直接修改参数 array 中的内容，所以这是非常必要的。 insertionSort() 会返回一个原始数组的拷贝，就像Swift已拥有的 sort() 方法一样。

2. 在函数里有两个循环，外循环依次查找数组中的每一个元素；这就是从数字堆中取最上面的数字的过程。变量 x 是有序部分结束和堆开始的索引（也就是 | 符号的位置）。要记住的是，在任何时候，从 0 到 x 的位置数组都是有序的，剩下的则是无序的。

3. 内循环则从 x 位置的元素开始查找。 x 是堆顶的元素，它有可能比前面的所有元素都小。内循环从有序数组的后面开始往前查找。每次找到一个大的元素，就交换它们的位置，直到内层循环结束，数组的前面部分依然是有序的，有序的元素也增加了一个。

注意：外层循环是从1开始，而不是0。从堆顶将第一个元素移动到有序数组没有任何意义，可以跳过。

不交换

上面的插入排序算法可以很好的完成任务，但是也可以通过移除对 swap() 的调用来提升速度。

通过交换两个数字来让下一个元素移动到合适的位置的：

[ 3, 5, 8, 4 | 6 ]
        <-->
        swap
        
[ 3, 5, 4, 8 | 6 ]
     <-->
     swap
复制代码

可以通过将前面的元素往右挪一个位置来代替元素的交换，然后将新的数字放到正确的位置。

[ 3, 5, 8, 4 | 6 ]   remember 4
           *

[ 3, 5, 8, 8 | 6 ]   shift 8 to the right
        --->
        
[ 3, 5, 5, 8 | 6 ]   shift 5 to the right
     --->
     
[ 3, 4, 5, 8 | 6 ]   copy 4 into place
     *
复制代码

代码：

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 这行代码就是将数字拷贝到正确的位置。

泛型化

如果能排序的类型不止数字就更好了。我们可以使数组的数据类型泛型化，然后使用一个用户提供的函数（或闭包）来执行比较操作。这只要改变两个地方。

函数签名变成：

译注： 函数签名 的英文原文是 function signature ，而我们常接触到是 函数声明 （function declaration），这两个概念都是有的，暂且不去追究它们的区别了，此处就译为函数签名，应该不影响对下面文章的理解。

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
复制代码

数组有一个类型 [T] ， [T] 是泛型化的一个占位类型。现在 insertionSort() 可以接收任何类型的数组，不管它是包含数字、字符串或者其它类型。

新的参数 isOrderedBefore: (T, T) -> Bool 是一个接收两个 T 对象然后返回一个 Bool 值的方法，如果第一个对象大于第二个，那么返回 true ，反之则返回 false 。这与 Swift 内置的 sort() 方法是一样的。

另外一个变化就是内循环，现在是这样的：

while y > 0 && isOrderedBefore(temp, a[y - 1]) {
复制代码

temp < a[y - 1] 被 isOrderedBefore() 替代，不仅可以比较数字，还可以比较各种对象了。

在 playground 中测试:

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

< 和 > 决定排序的顺序，分别代表低到高和高到低。

译注：参数 isOrderedBefore 可以使用 < 或 > ，是因为在Swift中运算符定义就类似 (T, T) -> Bool 。

在 Foundation 中可以看到不同类型定义了运算符，比如 Decimal 就定义了 < ： public static func < (lhs: Decimal, rhs: Decimal) -> Bool 。

Swift文档介绍了 Custom Operators 可以参考。

当然，我们也可以对其它数据类型排序如字符串：

let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)
复制代码

也可以是更复杂的对象：

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) 的性能糟糕多了，插入排序差很多。