本文是对 Swift Algorithm Club 翻译的一篇文章.
Swift Algorithm Club 是 https://www.raywenderlich.com 网站出品的用 Swift 实现算法和数据结构的开源项目, 目前在 GitHub 上有 18000+, 我初略统计了一下, 大概有一百左右个的算法和数据结构, 基本上常见的都包含了, 是 iOSer 学习算法和数据结构不错的资源.
https://github.com/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] 中.
一种方法是: 查看前一个元素 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) 的性能糟糕多了, 插入排序差很多.
来源: https://juejin.im/post/5c2767a56fb9a049b82a8ba6