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  或者 本地下载

总结

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

(0)

相关推荐

  • Swift代码实现冒泡排序算法的简单实例

    冒泡排序原理 1.对需要排序的数据,俩俩进行比较,小的放前面,大的放后面 2.依次对每一对相邻的数据作步骤1的工作,当排序到最后一个元素的时候,我们能保证这个数据是最大. 3.针对所有的元素重复以上的步骤,除了最后一个(这里为什么需要针对除了最后一个元素的全部元素做一次呢,因为最后一个元素已经是最大的不需要排序了,同时,由于元素的交换,交换上来的元素的大小不一定比前面的元素的大,所以需要再做一次). 4持续对越来越少的元素重复3的步骤,直到没有任何一对元素需要比较. 时间复杂度 我们一般谈最坏时

  • Swift实现Selection Sort选择排序算法的实例讲解

    选择排序Selection Sort是一种和插入排序Insertion Sort类似的排序方法,它同样只适用于对规模不大的集合进行排序.它的核心思想是,在序列内部,把序列逻辑上分成已排序和未排序两部分,不断找到未排序部分中最符合排序规则的元素,添加进已排序部分,直到序列中所有元素都已经添加到了已排序部分,此时,整个序列就排序完成了. 冒泡排序是两两比较不断交换来实现排序,所以比较繁琐. 而选择排序  则是先选择要交换的那个数,才去交换.这样就可以省去很多不必要的步骤. Swift版实现示例: f

  • Swift实现堆排序算法的代码示例

    算法思想 堆排序利用了最大堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单. 1.用最大堆排序的基本思想 (1)先将初始文件R[1..n]建成一个最大堆,此堆为初始的无序区 (2)再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key (3)由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-

  • 理解二叉堆数据结构及Swift的堆排序算法实现示例

    二叉堆的性质 1.二叉堆是一颗完全二叉树,最后一层的叶子从左到右排列,其它的每一层都是满的 2.最小堆父结点小于等于其每一个子结点的键值,最大堆则相反 3.每个结点的左子树或者右子树都是一个二叉堆 下面是一个最小堆: 堆的存储 通常堆是通过一维数组来实现的.在起始数组为 0 的情形中: 1.父节点i的左子节点在位置 (2*i+1); 2.父节点i的右子节点在位置 (2*i+2); 3.子节点i的父节点在位置 floor((i-1)/2); 维持堆的性质 我们以最大堆来介绍(后续会分别给出最大堆和

  • 简单理解插入排序算法及Swift版的代码示例

    算法思想 插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌.开始时,我们左手中没有牌,桌上有洗好的扑克牌,我们抓取一张扑克牌并放入左手的正确位置.为了找到一张扑克牌的正确位置,我们从右到左将它与手中的每张牌进行比较,左手上的牌总是排序好的,而这些牌原来都是桌上牌堆中顶部的牌,当我们抓完牌时,左手中的牌自然是有顺序的. 之所以叫插入排序,不是为别的,正是因为该算法的核心就是将无序的元素插入排好序的部分. 插入排序的核心思想即在于划分已排序和未排序,将每个待排序的元素逐个与已排序的元素比较,

  • Swift编程中实现希尔排序算法的代码实例

    思想 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,

  • 快速排序算法在Swift编程中的几种代码实现示例

    总所周知 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用. 基本原理是: 数组a = [1,3,5,7,6,4,2] 1 选定一个 基准 a[0] 2 把比 a[0]小的放左边,比a[0]大的放右边. 中断递归如果少于两个数字 则不执行. 3 然后再分别对两边 执行 1,2,3操作. 对快速排序 的 想法 1 在待排序元素 大部分是有序的情况下, 速度 非常很快. 2 在最差的情况下,速度就很慢了. 相当于冒泡了 3 所以 快排的 优化, 定基准 非常重要,

  • Swift实现快速排序算法的代码示例

    思想 快速排序作为分治代表,通常实现由三步 1.数据中选择一个元素作为"基准"(pivot),通常选取最后一个元素: 2.分区(partition) 所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边.分区操作结束后,基准元素所处的位置就是最终排序后它的位置. 3.对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为

  • 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

  • JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

    排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,

  • TypeScript实现十大排序算法之冒泡排序示例详解

    目录 一. 冒泡排序的定义 二. 冒泡排序的流程 三. 冒泡排序的图解 四. 冒泡排序的代码 五. 冒泡排序的时间复杂度 六. 冒泡排序的总结 一. 冒泡排序的定义 冒泡排序是一种简单的排序方法. 基本思路是通过两两比较相邻的元素并交换它们的位置,从而使整个序列按照顺序排列. 该算法一趟排序后,最大值总是会移到数组最后面,那么接下来就不用再考虑这个最大值. 一直重复这样的操作,最终就可以得到排序完成的数组. 这种算法是稳定的,即相等元素的相对位置不会发生变化. 而且在最坏情况下,时间复杂度为O(

  • Python中的tkinter库简单案例详解

    目录 案例一 Label & Button 标签和按钮 案例二 Entry & Text 输入和文本框 案例三 Listbox 部件 案例四 Radiobutton 选择按钮 案例五 Scale 尺度 案例六 Checkbutton 勾选项 案例七 Canvas 画布 案例八 Menubar 菜单 案例九 Frame 框架 案例十 messagebox 弹窗 案例十一 pack grid place 放置 登录窗口 TKinterPython 的 GUI 库非常多,之所以选择 Tkinte

  • python 排序算法总结及实例详解

    总结了一下常见集中排序的算法 归并排序 归并排序也称合并排序,是分治法的典型应用.分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并. 具体的归并排序就是,将一组无序数按n/2递归分解成只有一个元素的子项,一个元素就是已经排好序的了.然后将这些有序的子元素进行合并. 合并的过程就是 对 两个已经排好序的子序列,先选取两个子序列中最小的元素进行比较,选取两个元素中最小的那个子序列并将其从子序列中 去掉添加到最终的结果集中,直到两个子序列归并完成. 代码如下: #!/usr/bin/p

  • PHP排序算法系列之归并排序详解

    归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已

  • Java经典排序算法之二分插入排序详解

    一.折半插入排序(二分插入排序) 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法.在处理A[i]时,A[0]--A[i-1]已经按关键码值排好序.所谓折半比较,就是在插入A[i]时,取A[i-1/2]的关键码值与A[i]的关键码值进行比较,如果A[i]的关键码值小于A[i-1/2]的关键码值,则说明A[i]只能插入A[0]到A[i-1/2]之间,故可以在A[0]到A[i-1/2-1]之间继续使用折半比较:否则只能插入A[i-1/2]到A[i-1]之间,故可

  • PHP排序算法系列之插入排序详解

    插入排序 有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在

  • js中apply与call简单用法详解

    你可以直接看例子,也可以先读一下介绍: call和apply是为了动态改变this而出现的,当一个object没有某个方法,但是其他的有,我们可以借助call或apply用其它对象的方法来操作. call, apply都属于Function.prototype的一个方法,它是JavaScript引擎内在实现的,因为属于Function.prototype,所以每个Function对象实例,也就是每个方法都有call, apply属性.既然作为方法的属性,那它们的使用就当然是针对方法的了.这两个方

  • iOS中视频播放器的简单封装详解

    前言 如果仅仅是播放视频两者的使用都非常简单,但是相比MediaPlayer,AVPlayer对于视频播放的可控制性更强一些,可以通过自定义的一些控件来实现视频的播放暂停等等.因此这里使用AVPlayer的视频播放. 视频播放器布局 首先使用xib创建CLAVPlayerView继承UIView用来承载播放器,这样我们在外部使用的时候,直接在控制器View或者Cell上添加CLAVPlayerView即可,至于播放器播放或者暂停等操作交给CLAVPlayerView来管理.下面来看一下CLAVP

随机推荐