Swift中排序算法的简单取舍详解
前言
对于iOS开发者来说, 算法的实现过程其实并不怎么关心, 因为只需要调用高级接口就可以得到系统最优的算法, 但了解轮子背后的原理才能更好的取舍, 不是么?下面话不多说了,来一起看看详细的介绍吧。
选择排序
我们以[9, 8, 7, 6, 5]举例.
[9, 8, 7, 6, 5]
第一次扫描, 扫描每一个数, 如比第一个数小则交换, 直到找到最小的数, 将其交换至下标0.
[8, 9, 7, 6, 5] [7, 9, 8, 6, 5] [6, 9, 8, 7, 5] [5, 9, 8, 7, 6]
第二次扫描, 由于确定了第一个数, 则从第二个数开始扫描, 逻辑同上取得次小的数交换至下标1.
[5, 8, 9, 7, 6] [5, 7, 9, 8, 6] [5, 6, 9, 8, 7]
第三次扫描, 跳过两个数, 从第三个数开始扫描, 并交换取得下标2.
[5, 6, 8, 9, 7] [5, 6, 7, 9, 8]
第四次扫描, 套用上述逻辑取得下标3.
[5, 6, 7, 8, 9]
由于最后只有一位数, 不需要交换, 则无需扫描.
了解了逻辑, 我们来看代码该怎么写;
func selectSort(list: inout [Int]) { let n = list.count for i in 0..<(n-1) { var j = i + 1 for _ in j..<n { if list[i] > list[j] { list[i] ^= list[j] list[j] ^= list[i] list[i] ^= list[j] } j += 1 } } }
外层循环取从0扫描到n-1, i代表了扫描推进的次数.
内层循环从i+1, 扫描到最后一位, 逐个比较, 如果比i小则交换.
选择排序(优化)
上述我们通过了非常简单的逻辑阐述了选择排序, 果然, 算法没有想象中难吧. 接下来, 我们来看看如何优化这个排序算法.
我们同样以[9, 8, 7, 6, 5]举例.
[9, 8, 7, 6, 5]
第一次扫描, 和之前一样扫描, 但只记住最小值的下标, 退出内层循环时交换.
[5, 8, 7, 6, 9]
第二次扫描, 确定第一位最小值后推进一格, 逻辑同上进行交换.
[5, 6, 7, 8, 9]
我们可以明显的看到优化的效果, 交换的次数降低了, 因为我们不是每次交换数值, 而是用指针记录后跳出内层循环后进行交换.
我们来看下代码该如何优化:
func optimizationSelectSort(list: inout [Int]) { let n = list.count var idx = 0 for i in 0..<(n - 1) { idx = i; var j = i + 1 for _ in j..<n { if list[idx] > list[j] { idx = j; } j += 1 } if idx != i { list[i] ^= list[idx] list[idx] ^= list[i] list[i] ^= list[idx] } } }
通过idx记录最小值的下标, 如果下标和当前值不等则交换数值.
冒泡排序
接下来我们来看冒泡排序, 同样以[9, 8, 7, 6, 5]为例.
[9, 8, 7, 6, 5]
第一次扫描, 同样扫描每一个数, 不同的是, 有两个指针同时向前走, 如果n>n-1则交换. 确定最末值为最大值.
[8, 9, 7, 6, 5] [8, 7, 9, 6, 5] [8, 7, 6, 9, 5] [8, 7, 6, 5, 9]
第二次扫描, 从头进行扫描, 由于以确定最末尾为最大值, 则少扫描一位.
[7, 8, 6, 5, 9] [7, 6, 8, 5, 9] [7, 6, 5, 8, 9]
第三次扫描, 和上述逻辑相同.
[6, 7, 5, 8, 9] [6, 5, 7, 8, 9]
第四次扫描, 得到排序完成的值.
[5, 6, 7, 8, 9]
上述可能不好理解, 多看几遍应该可以.
如果还是理解不能, 我们就来看看代码吧;
func popSort(list: inout [Int]) { let n = list.count for i in 0..<n-1 { var j = 0 for _ in 0..<(n-1-i) { if list[j] > list[j+1] { list[j] ^= list[j+1] list[j+1] ^= list[j] list[j] ^= list[j+1] } j += 1 } } }
外层循环同样从0扫描到n-1, 这点不赘述.
内层循环从头也就是0扫描到n-1-i, 也就是每次扫描少扫一位, 应为每次都会确定最末位为最大值.
冒泡排序(优化)
冒泡排序的优化就没有选择排序的优化那么给力了, 还有可能产生负优化, 慎用!!
这次我们用[5, 6, 7, 9, 8]来举例.
--- scope of: popsort --- [5, 6, 7, 9, 8] [5, 6, 7, 8, 9] --- scope of: opt_popsort --- [5, 6, 7, 9, 8] [5, 6, 7, 8, 9]
这个优化并不是特别直观, 最好运行我的源码. 优化来自于如果已经排序完成则不用扫描空转. 上面的空行就是空转.
func optimizationPopSort(list: inout [Int]) { let n = list.count for i in 0..<n-1 { var flag = 0 var j = 0 for _ in 0..<(n-1-i) { if list[j] > list[j+1] { list[j] ^= list[j+1] list[j+1] ^= list[j] list[j] ^= list[j+1] flag = 1 } j += 1 } if flag == 0 { break } } }
就是加了一个标志位来判断是否跳出扫描.
快速排序
快速排序, 不是特别好举例, 但是最重要的一个排序.
func quickSort(list: inout [Int]) { func sort(list: inout [Int], low: Int, high: Int) { if low < high { let pivot = list[low] var l = low; var h = high while l < h { while list[h] >= pivot && l < h {h -= 1} list[l] = list[h] while list[l] <= pivot && l < h {l += 1} list[h] = list[l] } list[h] = pivot sort(list: &list, low: low, high: l-1) sort(list: &list, low: l+1, high: high) } } sort(list: &list, low: 0, high: list.count - 1) }
我们直接看代码就能看出, 我们将下标0作为标尺, 进行扫描, 比其大的排右面, 比其小的排左边, 用递归的方式进行排序而成, 由于一次扫描后同时进行了模糊排序, 效率极高.
排序取舍
我们将上述所有的排序算法和系统的排序进行了比较, 以10000个随机数为例.
scope(of: "sort", execute: true) { scope(of: "systemsort", execute: true, action: { let list = randomList(10000) timing {_ = list.sorted()} // print(list.sorted()) }) scope(of: "systemsort2", execute: true, action: { let list = randomList(10000) timing {_ = list.sorted {$0 < $1}} // print(list.sorted {$0 < $1}) }) scope(of: "selectsort", execute: true, action: { var list = randomList(10000) timing {selectSort(list: &list)} // print(list) }) scope(of: "opt_selectsort", execute: true, action: { var list = randomList(10000) timing {optimizationSelectSort(list: &list)} // print(list) }) scope(of: "popsort", execute: true, action: { var list = randomList(10000) timing {popSort(list: &list)} // print(list) }) scope(of: "opt_popsort", execute: true, action: { var list = randomList(10000) timing {optimizationPopSort(list: &list)} // print(list) }) scope(of: "quicksort", execute: true, action: { var list = randomList(10000) timing {quickSort(list: &list)} // print(list) }) }
--- scope of: sort --- --- scope of: systemsort --- timing: 0.010432243347168 --- scope of: systemsort2 --- timing: 0.00398015975952148 --- scope of: selectsort --- timing: 2.67806816101074 --- scope of: opt_selectsort --- timing: 0.431572914123535 --- scope of: popsort --- timing: 3.39597702026367 --- scope of: opt_popsort --- timing: 3.59421491622925 --- scope of: quicksort --- timing: 0.00454998016357422
我们可以看到, 其中我写的快排是效率最高的, 和系统的排序是一个数量级的, 而选择比冒泡的效率要高, 而令人疑惑的是同样是系统的排序加上{$0 < $1}比较规则, 效率会有数量级的提升.
现在大家知道如何选择排序算法了么?
二分搜索
@discardableResult func binSearch(list: [Int], find: Int) -> Int { var low = 0, high = list.count - 1 while low <= high { let mid = (low + high) / 2 if find == list[mid] {return mid} else if (find > list[mid]) {low = mid + 1} else {high = mid - 1} } return -1; }
@discardableResult func recursiveBinSearch(list: [Int], find: Int) -> Int { func search(list: [Int], low: Int, high: Int, find: Int) -> Int { if low <= high { let mid = (low + high) / 2 if find == list[mid] {return mid} else if (find > list[mid]) { return search(list: list, low: mid+1, high: high, find: find) } else { return search(list: list, low: low, high: mid-1, find: find) } } return -1; } return search(list: list, low: 0, high: list.count - 1, find: find) }
二分搜索的原理就不多说了, 就是折半折半再折半, 这种搜索算法的关键就是要有序, 所以配合上合适的排序算法才是最重要的!
源码下载:github 或者 本地下载
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对猪先飞的支持。
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要给大家介绍了关于swift中利用runtime交换方法的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。...2020-06-30
- 在本篇文章里小编给大家整理的是关于C#实现排序的代码以及相关知识点,需要的朋友们参考下。...2020-06-25
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 有时候,我们需要一个显示文字,又想这些文字与边界之间有自定义的边距,所以下面这篇文章主要给大家介绍了关于Swift设置UILabel内边距的相关资料,需要的朋友可以参考下...2021-10-14
- 这篇文章主要给大家介绍了关于swift中@UIApplicationMain的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。...2020-06-30
- c# n个数排序实现代...2020-06-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
- 这篇文章主要介绍了C#使用linq对数组进行筛选排序的方法,实例分析了C#实用linq扩展进行数组排序的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 给大家详细讲解了IOS开发中swift语言xcworkspace多项目管理的方法和介绍,一起参考一下。...2020-06-30
Swift 中如何使用 Option Pattern 改善可选项的 API 设计
这篇文章主要介绍了Swift 中如何使用 Option Pattern 改善可选项的 API 设计,帮助大家更好的进行ios开发,感兴趣的朋友可以了解下...2020-10-23