Swift 算法实战之路:排序

[中文教程]
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看143 回复回复1 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 143|回复: 1
收起左侧

[中文教程] Swift 算法实战之路:排序

[复制链接]
代码买卖 发表于 2016-9-7 03:34:33 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 代码买卖 于 2016-9-7 04:53 编辑


以前的文章中,我们主要是在讲数据结构:比如数组链表队列。这些数据结构都是了解Swift和算法的基础。从今以后的文章,我们将更多的关注于通用算法,这次我们就来聊聊排序。这次的主要内容有:

  • 基本概念
  • 排序实战


Swift 算法实战之路:排序

Swift 算法实战之路:排序 - 敏捷大拇指 - Swift 算法实战之路:排序





1、基本概念

我们平常用的排序算法一般就以下几种:

名称
时间复杂度
空间复杂度
是否稳定
冒泡排序
O(n^2)
O(1)
插入排序
O(n^2)
O(1)
选择排序
O(n^2)
O(1)
堆排序
O(nlogn)
O(1)
归并排序
O(nlogn)
O(1)
快速排序
O(nlogn)
O(1)
桶排序
O(n)
O(k)


这些算法具体的定义本文不再赘述。一般情况下,好的排序算法性能是O(nlogn),坏的性能是O(n^2)。本文在此用swift示范实现归并排序:

[Swift] 纯文本查看 复制代码
func mergeSort(array: [Int]) -> [Int] {
  var helper = Array(count: array.count, repeatedValue: 0)
  var array = array
  mergeSort(&array, &helper, 0, array.count - 1)
  return array
}

func mergeSort(inout array: [Int], inout _ helper: [Int], _ low: Int, _ high: Int) {
  guard low < high else {
    return
  }

  let middle = (high - low) / 2 + low
  mergeSort(&array, &helper, low, middle)
  mergeSort(&array, &helper, middle + 1, high)
  merge(&array, &helper, low, middle, high)
}

func merge(inout array: [Int], inout _ helper: [Int], _ low: Int, _ middle: Int, _ high: Int) {
  // copy both halves into a helper array
  for i in low ... high {
    helper[i ] = array[i ]
  }

  var helperLeft = low
  var helperRight = middle + 1
  var current = low

  // iterate through helper array and copy the right one to original array
  while helperLeft <= middle && helperRight <= high {
    if helper[helperLeft] <= helper[helperRight] {
      array[current] = helper[helperLeft]
      helperLeft += 1
    } else {
      array[current] = helper[helperRight]
      helperRight += 1
    }
    current += 1
  }

  // handle the rest
  guard middle - helperLeft >= 0 else {
    return
  }
  for i in 0 ... middle - helperLeft {
    array[current + i] = helper[helperLeft + i]
  }
}


表格中有一个特例是桶排序,它是将输入的数组分配到一定数量的空桶中,每个空桶再单独排序。当输入的数组是均匀分配时,桶排序的时间复杂度为O(n)。举个微软的面试题来当例子:

有三种颜色(红,黄,蓝)的球若干,要求将所有红色的球放在黄色球的前面,最后放上所有的蓝色球。


这道题目最直接的解法就是桶排序。首先第一次遍历,统计有多少个红色球(假设x个),多少个黄色球(假设y个),和多少个蓝色球(假设z个)。然后再一次遍历,数组前部x个位置填充红色球,中间y个位置放上对应数量的黄色球,最后z个位置再放上蓝色球。

另外解释一下稳定的意思:相等的键值,如果排过序后与原来未排序的次序相同,则称此排序算法为稳定。举个例子:

[Swift] 纯文本查看 复制代码
// 原数组
[[2, 1], [1,3], [1,4]]

// 排序算法一
[[1,3], [1,4], [2, 1]]
// 排序算法二
[[1,4], [1,3], [2, 1]]


我们注意到排序算法一和二的区别就在于对[1, 3], [1, 4]这两个元素的处理。排序算法一中,这两个元素位置与原数组相同,故称其为稳定算法。而排序算法二则是不稳定算法。

Swift中,排序的使用如下:

[Swift] 纯文本查看 复制代码
// 以升序排列为例,原数组可改变
array.sortInPlace(<)

// 以降序排列为例,原数组不可改变
newArray = array.sort(>)

// 字典键值排序示例
let keys = Array(map.keys)
let sortedKeys = keys.sort() {
  let value1 = map[$0]
  let value2 = map[$1]
  return value1 > value2
}


在其他语言比如Java中,其自带的sort函数是用归并排序实现的。而在Swift源代码中,sort函数采用的是一种内审算法(IntroSort)。它由堆排序、插入排序、快速排序三种算法构成,依据输入的深度相应选择最佳的算法来完成。本文关注的重点是实战,所以不做展开。对源代码感兴趣的朋友可以去Github读苹果的Swift的开源库。




2、排序实战

直接来看一道Facebook, Google, Linkedin都考过的面试题。

已知有很多会议,如果有这些会议时间有重叠,则将它们合并。

比如有一个会议的时间为3点到5点,另一个会议时间为4点到6点,那么合并之后的会议时间为3点到6点。


解决算法题目第一步永远是把具体问题抽象化。这里每一个会议我们已知开始时间和结束时间,就可以写一个类来定义它:

[Swift] 纯文本查看 复制代码
public class MeetingTime {
  public var start: Int
  public var end: Int
  public init(_ start: Int, _ end: Int) {
    self.start = start
    self.end = end
  }
}


然后题目说已知有很多会议,就是说我们已知有一个MeetingTime的数组、所以题目就转化为写一个函数,输入为一个MeetingTime的数组,输出为一个将原数组中所有重叠时间都处理过的新数组。

[Swift] 纯文本查看 复制代码
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] {}


下面来分析一下题目怎么解。最基本的思路是遍历一次数组,然后归并所有重叠时间。举个例子:[[1, 3], [5, 6], [4, 7], [2, 3]]。这里我们可以发现[1, 3]和[2, 3]可以归并为[1, 3],[5, 6]和[4, 7]可以归并为[5, 7]。所以这里就提出一个要求:要将所有可能重叠的时间尽量放在一起,这样遍历的时候可以就可以从前往后一个接着一个的归并。于是很自然的想到 —— 按照会议开始的时间排序。

这里我们要对一个class进行排序,而且要自定义排序方法,在Swift中可以这样写:

[Swift] 纯文本查看 复制代码
meetingTimes.sortInPlace() {
  if $0.start != $1.start {
    return $0.start < $1.start
  } else {
    return $0.end < $1.end
  }
}


意思就是首先对开始时间进行升序排列,如果它们相同,就比较结束时间。

有了排好顺序的数组,要得到新的归并后的结果数组,我们只需要在遍历的时候,每次比较原数组(排序后)当前会议时间与结果数组中当前的会议时间,假如它们有重叠,则归并;如果没有,则直接添加进结果数组之中。所有代码如下:

[Swift] 纯文本查看 复制代码
func merge(meetingTimes: [MeetingTime]) -> [MeetingTime] {
  // 处理特殊情况
  guard meetingTimes.count > 1 else {
    return meetingTimes
  }

  // 排序  
  var meetingTimes = meetingTimes.sort() {
    if $0.start != $1.start {
      return $0.start < $1.start
    } else {
      return $0.end < $1.end
    }
  }

  // 新建结果数组
  var res = [MeetingTime]()
  res.append(meetingTimes[0])

  // 遍历排序后的原数组,并与结果数组归并     
  for i in 1..<meetingTimes.count {
    let last = res[res.count - 1]
    let current = intervals[i ]
    if current.start > last.end {
      res.append(current)
    } else {
      last.end = max(last.end, current.end)
    }
  }

  return res
}





3、展望

排序在Swift中的应用场景很多,比如tableView中对于dataSource的处理。当然很多时候,排序都是和搜索,尤其是二分搜索配合使用。下期探讨搜索的时候,会对排序进行进一步拓展。




相关内容

Swift 算法实战之路:基本语法与技巧

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:链表

Swift 算法实战之路:栈和队列

Swift 算法实战之路:二叉树

Swift 算法实战之路:排序

Swift 算法实战之路:二分搜索

Swift 算法实战之路:深度和广度优先搜索

Swift 算法实战之路:动态规划




作者:故胤道长

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

强者更强 发表于 2016-9-9 22:20:38 | 显示全部楼层
头一次听说桶排序~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表