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