插入排序
目标：将一个数组按照从低到高（或从高到低）来排序。
现有一个数字类型的数组需要进行排序，插入排序的工作方式如下：
- 首先，将这些待排序的数字放在一个数组中，成为未排序的原始数组。
- 从其中取出一个数字，具体取哪个无所谓。为简单起见，每次都直接取出第一个元素。
- 将这个数字插入到一个新的已排序数组中。
- 然后再次从未排序数组中取出一个数字，将其插入到已排序数组中。它要么插在第一个元素的前面，要么插在后面，来保证这两个数字是有序的。
- 再一次从未排序数组中取出一个元素，安插在新数组的合适位置，以求新数组依然有序。
- 一直这样做下去，直到未排序数组中没有数字了为止。这样就可以达到排序的目的了。
这就是算法叫“插入”排序的原因，因为排序过程中不断地从未排序数组中取出元素插入到已排序的目标数组。
译者注：类似于打牌的时候抓牌的过程！
举例
例如，待排序的数组为 [ 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 ]
^
它比 4 大吗？是的，所以 4 应该放到 8 的前面去。我们将两个数字交换位置来达到目的：
[ 3, 5, 4, 8 | 6 ]
<-->
已交换
至此还没有结束。交换之后，新的排在前面的元素 5 也比 4 大。我们如法炮制，也将这两个数字交换位置：
[ 3, 4, 5, 8 | 6 ]
<-->
已交换
继续，再次检查排在前面的新元素 3，它比 4 大吗？不，它必 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)
下面介绍代码是如何工作的。
-
由于参数
array无法直接修改，我们需要先复制一下数组，类似 Swift 自己sort()函数，insertionSort()会返回的排序后的新数组。 -
这个函数中有两层循环。外层循环数组中的每一个元素，就是从 数组中取最顶层的，x变量是排序部分最后位置和管道符开始的位置（ |的位置），请记住在任何时候，数组开始部分从0至x是已经排好的，从x到最后是没有排序的部分。 - 内层循环获取
x位置的数字，就是未排序数组的头部，它可能比之前的数字都笑，内层循环会反向遍历已经排序的数字，每次比较发现之前排序中的数字较大后就交换一下位置，当内层循环结束后，数组头部就完成一次排序，已经排序的部分增加一个数字。
注意 外层循环不是从0开始而是从1开始。把开始位置的数字移动到已排序区没有什么意义，因此我们直接跳过。
不用 swap
之前版本插入排序已经工作的很好了，但是可以通过省略 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] , T 是泛型模板。现在 insertionSort() 可以接受任意的类型数组， 无论是数字，字符或者什么。。
这个新参数 isOrderedBefore: (T, T) -> Bool 是一个函数，函数定义为比较两个 T 类型的对象并返回比较结果， 如果第一个对象比第二个对象在前，返回 true, 否则返回 false。 Swift 内置的 sort() 函数也正是如此。
只需要改变内层循环，修改如下：
while y > 0 && isOrderedBefore(temp, a[y - 1]) {
通过 isOrderedBefore () 代替 ``temp < a[y - 1] `, 功能不变，但是我们现在可以比较任意类型对象，不只是数字。
在 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, 忽略他们其他的属性，这两个对象不会交换位置。
性能
插入排序在数组已经排序好的情况下非常快。听起来有些荒唐，但是不是所有的搜索算法都是能这样。 实际情况下，对于非常大的数据集的一部分进行排序，插入排序还是很不错的。
最坏和平均排序的时间复杂度为 O(n^2) 。这是因为有两层循环，其他的算法如快速排序和归并排序为 O(n log n) ，在数据集很大时也很快。
插入排序在很小的数组时排序很快。一些标准库在排序区小于等于10的时候把快速排序换成插入排序。
我做了简单比较了insertionSort() 和 Swift 内置的 sort() 。在100个左右的数据的数组时，二者差距非常小，但是当你输入变得更大时，O(n^2) 很快比 O(n log n) 性能差很多，插入排序已经跟不上班了。。
其他
作者 Matthijs Hollemans， 翻译 ksco，keithMorning