Swift算法俱乐部中文版 -- 插入排序

目标：从小到大（或从大到小）对数组进行排序。

给你一组数组，将他们排序。插入排序算法的步骤如下：

把未排序的数字放在一堆。
从这堆数字里面挑一个。选哪个并不重要，但从顶部拿最容易。
将选出来的数字插入新数组中。
从未排序的数字堆中挑一个数字，并将其插入新数组。在您选择的第一个数字之前或之后，将这两个数字排序。
再选择一个数字，并按顺序插入到数组中适当的位置。
重复这样做，直到堆里没有数字。你最终得到一个空堆和一个排序的数组。

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

我们摸扑克牌就是插入排序！

举个栗子

未排序的数字堆是 [ 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 ] 。

重复此过程，直到堆是空的。

在一个数组中排序

上面的解释会你看起来需要两个数组：一个用于未排序的数组，一个排序好的数组。

但是你可以在一个数组里执行插入排序，而无需创建新的数组。你只需知道数组的哪个部分已经排序，哪个部分是未排序的堆。

最初，数组是 [ 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 ]
        ^

8 是否大于 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
            swap(&a[y - 1], &a[y])
            y -= 1
        }
    }
    return a
}

把这段代码放到 playground 里测试：

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

注释对应的代码分析：

创建数组的副本。这是必要的，因为我们不能直接修改参数 array 的内容。像Swift 中的 sort()一样，insertionSort() 函数将返回原始数组的副本，并将它排序。
这个函数里有两个循环：外部循环遍历数组中的每个元素，从数字堆的最顶端挑选数字；变量 x 是排序区分排序不分与数字堆的索引（相当于 | 的作用）。请记住，任何时候，array[0] 到 array[x] 都是排序完成的。从 array[x] 到结束，是未排序的数字堆。
循环查看 array[x] ，这是在数字堆中顶部的数组，它可能小于排序数组的任何元素。循环排序好的数组，每次往前找一个，如果前面的更大，就交换它们。当循环完成时，排序好的数组就增长了一个元素。

注意：外循环从（注释2处）索引从1开始，将第一个元素从数字堆中移动到排序部分并不会改变任何内容，所以我们可以跳过它。

减少交换

上面的插入排序虽然能使用，但是如果能删除 swap() 方法会运行的更快。

您已经看到，我们交换数字，将下一个元素根据排序移动到合适的位置：

[ 3, 5, 8, 4 | 6 ]
        <-->
        swap

[ 3, 5, 4, 8 | 6 ]
     <-->
     swap

我们可以不交换，将数字向右移动，然后把新数字放到合适的位置就可以了。

[ 3, 5, 8, 4 | 6 ]  复制 4
           *

[ 3, 5, 8, 8 | 6 ]  将 8 向右移动
        --->

[ 3, 5, 5, 8 | 6 ]  将 5 向右移动
     --->

[ 3, 4, 5, 8 | 6 ]  把 4 粘贴到合适的位置
     *

代码：

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 处是将新数字复制到对应的位置。

给其他类型排序

我们可以给其他类型排序，添加泛型并提供比较函数即可。只需要修改两处代码。

方法定义变为：

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

数组具有泛型 [T]，现在 isOrderedBefore() 方法将接受任何类型，无论是数组，字符串，或是其他类型。

新的参数 isOrderedBefore: (T, T) -> Bool 是一个方法，接受两个 T 类型的对象，如果两个参数比较厚满足这个表达式，返回 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, >)

< 和 > 决定排序顺序，分别是从小到大和从大到小。

当然，你也可以排序其他类型，如字符串：

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) 差很多，并且插入排序不能跟上。

作者：Matthijs Hollemans -- Swift 算法俱乐部

英文链接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Insertion%20Sort