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

发布时间：2020-12-15 00:56:18 所属栏目：C语言来源：网络整理

导读：前言对于iOS开发者来说,算法的实现过程其实并不怎么关心,因为只需要调用高级接口就可以得到系统最优的算法,但了解轮子背后的原理才能更好的取舍,不是么下面话不多说了，来一起看看详细的介绍吧。选择排序我们以[9,8,7,6,5]举例. [9,5] 第一次扫描,扫描每

前言

对于iOS开发者来说,算法的实现过程其实并不怎么关心,因为只需要调用高级接口就可以得到系统最优的算法,但了解轮子背后的原理才能更好的取舍,不是么?下面话不多说了，来一起看看详细的介绍吧。

选择排序

我们以[9,8,7,6,5]举例.

[9,5]

第一次扫描,扫描每一个数,如比第一个数小则交换,直到找到最小的数,将其交换至下标0.

[8,9,5]
[7,5]
[6,5]
[5,6]

第二次扫描,由于确定了第一个数,则从第二个数开始扫描,逻辑同上取得次小的数交换至下标1.

[5,6]
[5,7]

第三次扫描,跳过两个数,从第三个数开始扫描,并交换取得下标2.

[5,7]
[5,8]

第四次扫描,套用上述逻辑取得下标3.

[5,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,和之前一样扫描,但只记住最小值的下标,退出内层循环时交换.

[5,9]

第二次扫描,确定第一位最小值后推进一格,逻辑同上进行交换.

[5,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,5]为例.

[9,同样扫描每一个数,不同的是,有两个指针同时向前走,如果n>n-1则交换. 确定最末值为最大值.

[8,5]
[8,5,从头进行扫描,由于以确定最末尾为最大值,则少扫描一位.

[7,9]
[7,9]

第三次扫描,和上述逻辑相同.

[6,9]
[6,9]

第四次扫描,得到排序完成的值.

[5,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,8]来举例.

--- scope of: popsort ---
[5,8]
[5,9]








--- scope of: opt_popsort ---
[5,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",action: {
  let list = randomList(10000)
  timing {_ = list.sorted {$0 < $1}}
//  print(list.sorted {$0 < $1})
 })
 
 scope(of: "selectsort",action: {
  var list = randomList(10000)
  timing {selectSort(list: &list)}
//  print(list)
 })

 scope(of: "opt_selectsort",action: {
  var list = randomList(10000)
  timing {optimizationSelectSort(list: &list)}
//  print(list)
 })

 scope(of: "popsort",action: {
  var list = randomList(10000)
  timing {popSort(list: &list)}
//  print(list)
 })

 scope(of: "opt_popsort",action: {
  var list = randomList(10000)
  timing {optimizationPopSort(list: &list)}
//  print(list)
 })

 scope(of: "quicksort",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],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,high: mid-1,find: find)
   }
  }
  return -1;
 }
 return search(list: list,high: list.count - 1,find: find)
}

二分搜索的原理就不多说了,就是折半折半再折半,这种搜索算法的关键就是要有序,所以配合上合适的排序算法才是最重要的!
源码下载：github  或者 本地下载
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对编程小技巧的支持。


            
            
您可能感兴趣的文章:
快速排序算法在Swift编程中的几种代码实现示例
Swift代码实现冒泡排序算法的简单实例
Swift实现堆排序算法的代码示例
Swift实现快速排序算法的代码示例
Swift编程中实现希尔排序算法的代码实例
简单理解插入排序算法及Swift版的代码示例
理解二叉堆数据结构及Swift的堆排序算法实现示例
Swift实现Selection Sort选择排序算法的实例讲解
                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!