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]
由于最后只有一位数,不需要交换,则无需扫描.
了解了逻辑,我们来看代码该怎么写;
funcselectSort(list:inout[Int]){
letn=list.count
foriin0..<(n-1){
varj=i+1
for_inj..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]
我们可以明显的看到优化的效果,交换的次数降低了,因为我们不是每次交换数值,而是用指针记录后跳出内层循环后进行交换.
我们来看下代码该如何优化:
funcoptimizationSelectSort(list:inout[Int]){
letn=list.count
varidx=0
foriin0..<(n-1){
idx=i;
varj=i+1
for_inj..list[j]{
idx=j;
}
j+=1
}
ifidx!=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]
上述可能不好理解,多看几遍应该可以.
如果还是理解不能,我们就来看看代码吧;
funcpopSort(list:inout[Int]){
letn=list.count
foriin0..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]来举例.
---scopeof:popsort--- [5,6,7,9,8] [5,6,7,8,9] ---scopeof:opt_popsort--- [5,6,7,9,8] [5,6,7,8,9]
这个优化并不是特别直观,最好运行我的源码.优化来自于如果已经排序完成则不用扫描空转.上面的空行就是空转.
funcoptimizationPopSort(list:inout[Int]){
letn=list.count
foriin0..list[j+1]{
list[j]^=list[j+1]
list[j+1]^=list[j]
list[j]^=list[j+1]
flag=1
}
j+=1
}
ifflag==0{
break
}
}
}
就是加了一个标志位来判断是否跳出扫描.
快速排序
快速排序,不是特别好举例,但是最重要的一个排序.
funcquickSort(list:inout[Int]){
funcsort(list:inout[Int],low:Int,high:Int){
iflow=pivot&&l
我们直接看代码就能看出,我们将下标0作为标尺,进行扫描,比其大的排右面,比其小的排左边,用递归的方式进行排序而成,由于一次扫描后同时进行了模糊排序,效率极高.
排序取舍
我们将上述所有的排序算法和系统的排序进行了比较,以10000个随机数为例.
scope(of:"sort",execute:true){
scope(of:"systemsort",execute:true,action:{
letlist=randomList(10000)
timing{_=list.sorted()}
//print(list.sorted())
})
scope(of:"systemsort2",execute:true,action:{
letlist=randomList(10000)
timing{_=list.sorted{$0<$1}}
//print(list.sorted{$0<$1})
})
scope(of:"selectsort",execute:true,action:{
varlist=randomList(10000)
timing{selectSort(list:&list)}
//print(list)
})
scope(of:"opt_selectsort",execute:true,action:{
varlist=randomList(10000)
timing{optimizationSelectSort(list:&list)}
//print(list)
})
scope(of:"popsort",execute:true,action:{
varlist=randomList(10000)
timing{popSort(list:&list)}
//print(list)
})
scope(of:"opt_popsort",execute:true,action:{
varlist=randomList(10000)
timing{optimizationPopSort(list:&list)}
//print(list)
})
scope(of:"quicksort",execute:true,action:{
varlist=randomList(10000)
timing{quickSort(list:&list)}
//print(list)
})
}
---scopeof:sort---
---scopeof:systemsort---
timing:0.010432243347168
---scopeof:systemsort2---
timing:0.00398015975952148
---scopeof:selectsort---
timing:2.67806816101074
---scopeof:opt_selectsort---
timing:0.431572914123535
---scopeof:popsort---
timing:3.39597702026367
---scopeof:opt_popsort---
timing:3.59421491622925
---scopeof:quicksort---
timing:0.00454998016357422
我们可以看到,其中我写的快排是效率最高的,和系统的排序是一个数量级的,而选择比冒泡的效率要高,而令人疑惑的是同样是系统的排序加上{$0<$1}比较规则,效率会有数量级的提升.
现在大家知道如何选择排序算法了么?
二分搜索
@discardableResultfuncbinSearch(list:[Int],find:Int)->Int{
varlow=0,high=list.count-1
whilelow<=high{
letmid=(low+high)/2
iffind==list[mid]{returnmid}
elseif(find>list[mid]){low=mid+1}
else{high=mid-1}
}
return-1;
}
@discardableResultfuncrecursiveBinSearch(list:[Int],find:Int)->Int{
funcsearch(list:[Int],low:Int,high:Int,find:Int)->Int{
iflow<=high{
letmid=(low+high)/2
iffind==list[mid]{returnmid}
elseif(find>list[mid]){
returnsearch(list:list,low:mid+1,high:high,find:find)
}
else{
returnsearch(list:list,low:low,high:mid-1,find:find)
}
}
return-1;
}
returnsearch(list:list,low:0,high:list.count-1,find:find)
}
二分搜索的原理就不多说了,就是折半折半再折半,这种搜索算法的关键就是要有序,所以配合上合适的排序算法才是最重要的!
源码下载：github 或者本地下载
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对毛票票的支持。