目标：将数组从低到高（或从高到低）排序。
给你一些数字，并且需要把它们按正确的顺序排列。插入排序算法的工作原理如下：
·把数字放在一堆。这堆是未排序的。
·从堆中挑选一个数字。选择哪一个并不重要，但是从最上面挑选最容易。
·将这个数字插入一个新的数组中。
·从未排序的堆中选取下一个数字，并将其插入新数组中。它要么在你选择的第一个数字之前或之后，所以现在这两个数字是排序的。
·再次，从堆中选择下一个数字并将其插入到正确排序位置的数组中。
·继续这样做，直到堆中没有更多数字。你最终得到一个空的堆和一个排序的数组。
这就是为什么这被称为“插入”排序的原因，因为您从堆中取出一个数字并将其插入到阵列中正确的排序位置。
一个例子
假设要排序的数字是[ 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 ]
<-->
swapped
我们还没有完成。新的前一个元素，5也大于4。我们还交换了这两个数字：
[ 3, 4, 5, 8 | 6 ]
<-->
swapped
再次看看前一个元素。是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.制作数组的copy。这是必要的，因为我们不能直接修改array参数的内容。就像Swift自己的一样sort()，insertionSort()函数将返回原始数组的一个有序copy。
2.这个函数里有两个循环。外循环依次查看数组中的每个元素; 这是从堆中挑选最高的数字。该变量x是排序部分结束并开始堆的位置（条的位置|）的索引。请记住，在任何给定的时刻，数组的开始 -- 从索引0到最后x-- 总是被排序。剩下的，从索引x到最后一个元素，都是未排序的堆。
3.内循环查看位置处的元素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
*
在代码如下所示：
Swift:
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
}
Object-C:
-(NSArray *)insertionSort:(NSArray *)array {
NSMutableArray * tempArray = [NSMutableArray arrayWithArray:array];
for (int x=1; x<tempArray.count; x++) {
int y = x;
while (y>0 && ([tempArray[y] intValue] < [tempArray[y-1] intValue])) {
[tempArray exchangeObjectAtIndex:y-1 withObjectAtIndex:y];
y -= 1;
}
}
return tempArray;
}
这条线//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]) {
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的值，则无论其他属性的值如何，这两个对象都不会被交换。
性能
如果数组已经排序，插入排序非常快。这听起来很明显，但对于所有搜索算法而言并非如此。在实践中，大量的数据已经很大程度上 -- if not entirely --分类和插入排序在这种情况下效果很好。
插入排序的最差情况和平均情况表现为O(n^2)。这是因为这个函数中有两个嵌套循环。其他排序算法（如快速排序和合并排序）具有**O(n log n) **性能，这对于大型输入更快。
插入排序对于排序小数组实际上非常快。某些标准库具有排序功能，当分区大小为10或更小时，会从快速排序切换到插入排序。
我做了一个快速测试，将我们insertionSort()与Swift的内置进行比较sort()。在大约100个左右的数组上，速度差异很小。然而，随着你的输入变大， O(n^2) 很快开始比O(n log n)差很多，插入排序也跟不上。
网友评论