插入排序动画
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+️⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙 andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。欢迎有兴趣学习算法和数据结构，有时间的小伙伴一起参与翻译，欢迎issue，或者直接提交pull request。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Insertion Sort
目标：把数组从低到高（或从高到低）排序
您将获得按正确的顺序排列一系列数字。插入排序算法的工作原理如下:
- 把一系列数字放在一个未排序的堆里。
- 从堆中挑选一个数字。 你选择哪一个并不重要，但从堆顶挑选是最容易。
- 把这个数插入一个新的数组。
- 从未排序堆中再选择一个数字，并将其插入之前的数组中。 这个数字在第一个数字之前或之后，所以现在这两个数字被排序。
- 再从堆中选择一个数字，并将其插入到数组中的正确排序位置。
- 继续这样做，直到堆里没有数字。 最终得到一个空堆和一个排序的数组。
这就是为什么这被称为“插入”排序，因为你从堆中取一个数字并将其插入数组中的正确排序位置。
例子
假设这边有需要排序的一些数字 [ 8, 3, 5, 4, 6 ]。
选择第一个数字8，然后将其插入新数组中。 新数组是空的，所以插入很容易。 排序的数组现在是[8]，堆是[3,5,4,6]。
从堆中选择下一个数字3，然后将其插入到已排序的数组中。 3应该在8之前，所以排序的数组现在是[3,8]，而堆被缩减为[5,4,6]。
从堆中选择下一个数字5，然后将其插入到已排序的数组中。 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]中。
Here's one way to do this: Look at the previous element, 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保持排序的插入。
下一节将对插入排序算法的内部循环的进行描述，通过交换数字将数字从堆的顶部插入到已排序的部分。
代码
下面插入排序的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中的内容，所以这是非常必要的。insertionSort()会返回一个原始数组的拷贝，就像Swift已拥有的sort()方法一样。 -
在函数里有两个循环，外循环依次查找数组中的每一个元素；这就是从数字堆中取最上面的数字的过程。变量
x是有序部分结束和堆开始的索引（也就是 | 符号的位置）。要记住的是，在任何时候，从0到x的位置数组都是有序的，剩下的则是无序的。 -
内循环则从
x位置的元素开始查找。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
*
代码：
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 这行代码就是将数字拷贝到正确的位置。
泛型化
如果能排序的类型不止数字就更好了。我们可以使数组的数据类型泛型化，然后使用一个用户提供的函数（或闭包）来执行比较操作。这只要改变两个地方。
函数签名变成：
译注：函数签名的英文原文是 function signature，而我们常接触到是 函数声明（function declaration），这两个概念都是有的，暂且不去追究它们的区别了，此处就译为函数签名，应该不影响对下面文章的理解。
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
数组有一个类型 [T]，[T] 是泛型化的一个占位类型。现在 insertionSort() 可以接收任何类型的数组，不管它是包含数字、字符串或者其它类型。
新的参数 isOrderedBefore: (T, T) -> Bool 是一个接收两个 T 对象然后返回一个 Bool 值的方法，如果第一个对象大于第二个，那么返回 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, >)
< 和 > 决定排序的顺序，分别代表低到高和高到低。
译注：参数
isOrderedBefore可以使用<或>，是因为在Swift中运算符定义就类似(T, T) -> Bool。
在Foundation中可以看到不同类型定义了运算符，比如Decimal就定义了<：public static func < (lhs: Decimal, rhs: Decimal) -> Bool。
Swift文档介绍了Custom Operators可以参考。
当然，我们也可以对其它数据类型排序如字符串：
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) 的性能糟糕多了，插入排序差很多。
网友评论