插入排序 Insertion Sort

将一个数组从高到低或者从低到高排序。

插入排序算法的工作原理：

将若干数字放在一个数组里，数组是乱序的。
从数组中挑选一个数字，它是哪个并不重要，但是为了方便我们挑选数组头部的这个。
将这个数字插入到一个新的数组里。
从乱序数组里挑选下一个数字也将它放到新数组里。这个数字要么在第一个数字前或者后，所以这个两个数字是被排序的。
再次重从乱序数组里挑选下一个数字也将它放到新数组里，并将数字放在正确的位置。
一直如此进行直到乱序数组中没有数字。这时也将等到一个排序好的新数组。

自己的一个实现：

let array = [2, 1, 3, 8, 3, 5, 4]

var newArray = [Int]()
for (k, v) in array.enumerated() {
    for (nK, nV) in newArray.enumerated() {
        // 本次的数 小于 存在的数的第一个(nv)
        if v < nV {
            newArray.insert(v, at: nK)
            break
        }
    }
    // 没有插入成功 放在末尾
    if newArray.count < k + 1 {
        newArray.append(v)
    }
}

In-place sort

上面的排序需要两个数组，一个原始的，一个排好顺序的。但是我们也可以 就地排序 无需创建一个额外的数组。我们只需要跟踪记录原始数组中哪里部分排好顺序了，哪一部分还没有排序。

举例：[ 8, 3, 5, 4, 6 ] 使用 | 分割是否排好顺序的部分。

// 开始时 | 在最前
[| 8, 3, 5, 4, 6 ]

// 开始向左移动，左侧只有个 8 无论什么顺序都是正确的，右侧是未排序的部分
[ 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 |]

每次 | 移动，都对左侧进行排序，未排序的部分逐渐减少，排序部分增加。直到未排序部分为零。

How to insert

将未排序的头部元素放在已排部分的正确位置，如何这到这点的？

// 从此状态开始。下个说的 4，我们需要将 4 插入到 [ 3, 5, 8 ] 这个已经排好的数组里
[ 3, 5, 8 | 4, 6 ]

// 移动 |，这时我们注意 8 这个元素
[ 3, 5, 8, 4 | 6 ]
        ^

// 8 大于 4，所有 8 应该在 4 的右边，8 与 4 进行位置调换
[ 3, 5, 4, 8 | 6 ]
        <-->
      swapped

// 将 4 与现在的前面的元素 5 进行比较，5 大于 4，所以 5 与 4 进行位置调换
[ 3, 4, 5, 8 | 6 ]
     <-->
    swapped

// 3 小于 4 这个数，所以我们完成了对 4 的排序，这时从头到 |，是排好顺序的
[ 3, 4, 5, 8 | 6 ]

这就是对插入排序算法的内循环的描述。

The code

func insertionSort(_ array: [Int]) -> [Int] {
    // 1
    var a = array
    // 2
    for x in 1..<a.count {
        var y = x
        // 3
        while y > 0 && a[y] < a[y - 1] {
            a.swapAt(y - 1, y)
            y -= 1
        }
    }
    return a
}

将 array 复制一个副本。因为我们无法直接修改参数中的 array，就想 Swift 自身的 sort()，insertionSort() 将返回一个排序顺序的副本数组。
两个循环在方法中。外层循环遍历轮到排序的元素，也就是从待排数组中挑选出头部的元素。x 索引为排好顺序的结尾索引同时也是待排数组的开头。记住，如何时间从开头到 x 永远都是排好顺序的，从 x 到最后的元素都是未排序的。
内层循环查询 x 索引位置的元素。这个元素可能小于之前排序顺序数组中的每一个元素。内层循环从后倒序遍历每一个已排序的元素，每次发现这个元素之前的元素比它大，则交互位置。当内层循环完成时，数组从开头到 x 将又是已排序的。

tip：外层循环从索引 1 开始，而不是 0。将第一个元素从堆移动到排序部分实际上并没有改变任何东西，所以我们不妨跳过它。

No more swaps

上面的插入排序可以正常的工作了。我们还可以通过移除调用 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]
        // tip
        while y > 0 && temp < a[y - 1] {
            // 1
            a[y] = a[y - 1]
            y -= 1
        }
        // 2
        a[y] = temp
    }
    return a
}

原本需要换位置的元素右移一个位置。
当内层结束时，y 的索引位置就是新元素的排序后的位置，将元素放在此。

tip：这里我自己写成了 while y > 0 && a[y] < a[y - 1] 这是不对的，因为我要找的是原本的 a[y] 的位置，但是循环一次后 a[y] 将发生变化。

Making it generic

func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
    var a = array
    for x in 1..<a.count {
        var y = x
        let temp = a[y]
        while y > 0, isOrderedBefore(temp, a[y - 1])  {
            a[y] = a[y - 1]
            y -= 1
        }
        a[y] = temp
    }

    return a
}

通过闭包来执行大小比较。

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

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

插入排序是一种稳定 stable 的排序。当排序后具有相同排序键的元素保持相同的相对顺序时，排序是稳定的。这对于诸如数字或字符串之类的简单值并不重要，但在排序更复杂的对象时这很重要。在上面的示例中，如果两个对象具有相同的优先级，则无论其他属性的值如何，这两个对象都不会被交换。

Performance

最差的插入排序是 O(n^2) 因为俩个相近的循环嵌套。其他排序算法（如快速排序和合并排序）具有 O(n log n) 性能，在大输入时速度更快。

插入排序实际上对于排序小数组非常快。某些标准库具有排序功能，当分区大小为 10 或更小时，可以从快速排序切换到插入排序。

将 insertSort() 与 Swift 的内置 sort() 进行比较。在大约 100 元素左右的阵列上，速度差异很小。但是，随着输入变大，O(n^2) 快速开始执行比 O(n log n) 差很多，并且插入排序无法跟上。

文章代码：GitHub - imzyf/data-structure-and-algorithm/003-Insertion Sort/。

References

raywenderlich/swift-algorithm-club/Insertion Sort