一个日常 Swift 数组排序引发的 思考
序
在 Swift 的日常开发中，或多或少会遇到数组排序
笔者最近遇到了一个排序的问题
群里提问之后
一个小总结
你别嫌我菜， 不菜没人爱
Sort
一般的排序 比如：
根据 Person 的 age 进行 升序/降序，一般我们通过 Swift 内置排序 sorted 去解决
image
sorted 会产生新的结果，不影响原有的序列； 而 sort() 会将结果保存在原有的数组中
我不知道你没有思考过这样一个问题
就是
sort 排序的原理是什么？
image
TimSort
Swift 的内置排序算法 sort() 在 Swift5 之后采用了 TimSort，相较于之前的 Introsort 更 stability
什么是 stability？
一种排序后维持相等元素的原始顺序的能力
比如
[1, 2, 2', 3] 在排序后变成了 [3, 2', 2, 1]
在真实数据下可能会影响到 排序的先后稳定性
音乐 app 按照 热门度 去排列 hit song
如果不够 stability，那么相同热门度的歌曲，可能每次的排序结果就会有差别
而 TimSort 也是一种混合算法 ，插入排序O(n^2) + 归并排序O(nlogn)， 因为 插入 和 归并都是 stability， 所以 TimSort 也是
TimSort 核心原理是 切割 + 合并
if 元素个数 < 64 {
插入排序
} else {
切割成不同的小数组 + 归并排序
}
具体实现可参考 TimSort
所以以此看来，sort 算法的时间复杂度是 O(nlogn)
日常的需求都一个样
笔者的需求是:
有一个 origin list 但信息不全， 要通过 origin list 的 id 数组 去请求具体的 detail list
覆盖 origin list
但是返回的 detail list 并没有按照 ids 的请求顺序排序 （不是升序 / 降序）
需要手动排序
题目可以理解为 ：
image
- 把
ids数组的长度用n表示，把最后想要得到的元素的 数目用m表示 - 本题
n == m
题解1 暴力解法
暴力解法: 双层 for循环, 时间复杂度 O(n^2)
image
题解2 高阶函数
高阶函数：flatMap + filter， 类似暴解，时间复杂度 O(n^2)
由 @SAGES** 提出 ：
image
flatMap:
将结果合并为一个新的数组，自动去 nil，同时会把 Optional 的值解包
-
由于
flatMap的时间复杂度是O(n + m)- n 表示 ids 的长度，m 表示 result2 的长度
- m == n，所以 flatMap
本题的时间复杂度为2n
-
filter的时间复杂度是O(n)
由于嵌套关系，省略常数，故本解 时间复杂度也为 O(n^2)
题解3 字典映射 + map
先将模型数组 映射到字典， 再 对 ids map 去字典内查找，时间复杂度 O(n)
由 @Damonwo** 提出
image
- for in 时间复杂度 为
O(n) - map 时间复杂度 也是
O(n)，字典查找O(1)常数，忽略不计
总体为 O(2n) => 故 此解法 O(n)
题解4 sort1
笔者开始想用 sort， 奈何对 sort 的理解 如登月一般
停留在表面， so
此解
- 不利用高阶的时间复杂度为：
O(nlogn) - 高阶的时间复杂度为：
O(nlogn)
由 @冬* 提出
image
此解第一步 将 ids 数组，按照下标映射到 字典内
得到
[23: 1, 77: 2, 56: 3, 9: 0, 87: 4]
最后通过 sorted 闭包 对 person 的 age 进行 index 权重 升序排序
- 高阶过程
- step1
- map 生成多个数组
let map1 = ids.enumerated()
.map { [$1 : $0] }
得到 ： [[9: 0], [23: 1], [77: 2], [56: 3], [87: 4]]
时间复杂度 O(n)
-
step2
- reduce 将元素的值合并成一个新的字典
- 时间复杂度
O(n)
-
step3
- merging 子字典 和 总序列 combine
- 可防止字典有 重复 key 存在 ，如果存在，取旧的 value
最终得到
[77: 2, 9: 0, 87: 5, 56: 4, 23: 1]
所以总的时间为 O(n) + O(n) + O(nlogn) ,取较大的值 即：O(nlogn)
题解5 sort2
此解 同 sort1 的 解法思路大致相同， 时间复杂度 为 O(nlogn)
由 @提拉米不**、提出
image
此解的核心和
sort1 一致，通过获取 person 的 age，在 ids 内的 index 权重 ，进行 sort
优化之后也是将 firstIndex 这一步 放入 map，降低查找时间复杂度
即
image
思路等同于 sort1
- for in 时间复杂度 为
O(n) - sorted 前面提过
O(nlogn)
所以总的时间为 O(n) + O(nlogn) ,取较大的值 即：O(nlogn)
总结
实际开发中
算法的选择还是很秒的
不考虑 时间复杂度，高阶函数会让 Swift 变的优雅；反之尽量采用 较低的 时间复杂度
尽管是一次小小的条件排序
选择越多
才会分优劣
欢迎分享自己的方法 ～
