Swift中排序算法的简单取舍详解

来源：本站原创|时间：2020-01-11|栏目：Swift|点击：157 次

前言

对于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 ) 
 let n = list.count
 for i in 0..<(n-1) 
 var j = i + 1
 for _ in j..<n 
  if list > list 
  list ^= list
  list ^= list
  list ^= list
  
  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 ) 
 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 > list 
  idx = j;
  
  j += 1
 
 if idx != i 
  list ^= list
  list ^= list
  list ^= list

通过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 ) 
 let n = list.count
 for i in 0..<n-1 
 var j = 0
 for _ in 0..<(n-1-i) 
  if list > listj+1 
  list ^= listj+1
  listj+1 ^= list
  list ^= listj+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 ) 
 let n = list.count
 for i in 0..<n-1 
  var flag = 0
  var j = 0
  for _ in 0..<(n-1-i) 
   if list > listj+1 
    list ^= listj+1
    listj+1 ^= list
    list ^= listj+1
    flag = 1
   
   j += 1
  
  if flag == 0 
   break

就是加了一个标志位来判断是否跳出扫描.

快速排序

快速排序, 不是特别好举例, 但是最重要的一个排序.

func quickSort(list: inout ) 
 func sort(list: inout , low: Int, high: Int) 
  if low < high 
   let pivot = list
   var l = low; var h = high
   while l < h 
    while list >= pivot && l < h h -= 1
    list = list
    while list <= pivot && l < h l += 1
    list = list
   
   list = 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: , find: Int) -> Int 
 var low = 0, high = list.count - 1
 while low <= high 
  let mid = (low + high) / 2
  if find == list return mid
  else if (find > list) low = mid + 1
  else high = mid - 1
 
 return -1;

@discardableResult func recursiveBinSearch(list: , find: Int) -> Int 
 func search(list: , low: Int, high: Int, find: Int) -> Int 
  if low <= high 
   let mid = (low + high) / 2
   if find == list return mid
   else if (find > list) 
    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 或者本地下载

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

上一篇：Swift如何为设置中心添加常用功能

栏目：Swift

下一篇：Swift利用纯代码实现时钟效果实例代码

本文标题：Swift中排序算法的简单取舍详解

本文地址：https://www.xiuzhanwang.com/a1/Swift/11961.html

更多Swift

Swift

Swift中排序算法的简单取舍详解

您可能感兴趣的文章

阅读排行

本栏相关

随机阅读