目标：从小到大（或从大到小）对数组进行排序。
给你一组数组，将他们排序。插入排序算法的步骤如下：
-
把未排序的数字放在一堆。
-
从这堆数字里面挑一个。选哪个并不重要，但从顶部拿最容易。
-
将选出来的数字插入新数组中。
-
从未排序的数字堆中挑一个数字，并将其插入新数组。 在您选择的第一个数字之前或之后，将这两个数字排序。
-
再选择一个数字，并按顺序插入到数组中适当的位置。
-
重复这样做，直到堆里没有数字。 你最终得到一个空堆和一个排序的数组。
这就是为什么这被称为“插入”排序，因为你从堆中取一个数字，并将其插入在数组里正确的排序位置。
我们摸扑克牌就是插入排序！
举个栗子
未排序的数字堆是 [ 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
网友评论