美文网首页swift 文章收集iOS算法
Swift 算法实战之路:排序

Swift 算法实战之路:排序

作者: 故胤道长 | 来源:发表于2016-07-25 13:22 被阅读3271次

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

    • 基本概念
    • 排序实战

    基本概念

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

    名称 时间复杂度 空间复杂度 是否稳定
    冒泡排序 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示范实现归并排序:

    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个位置再放上蓝色球。

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

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

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

    Swift中,排序的使用如下:

    // 以升序排列为例,原数组可改变
    array.sort
    
    // 以降序排列为例,原数组不可改变
    newArray = array.sorted(by: >)
    
    // 字典键值排序示例
    let keys = Array(map.keys)
    let sortedKeys = keys.sorted() {
      return map[$0]! > map[$1]!
    }
    

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

    排序实战

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

    已知有很多会议,如果有这些会议时间有重叠,则将它们合并。
    比如有一个会议的时间为3点到5点,另一个会议时间为4点到6点,那么合并之后的会议时间为3点到6点

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

    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的数组,输出为一个将原数组中所有重叠时间都处理过的新数组。

    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中可以这样写:

    meetingTimes.sortInPlace() {
      if $0.start != $1.start {
        return $0.start < $1.start
      } else {
        return $0.end < $1.end
      }
    }
    

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

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

    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 = meetingTimes[i]
        if current.start > last.end {
          res.append(current)
        } else {
          last.end = max(last.end, current.end)
        }
      }
            
      return res
    }
    

    展望

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

    相关文章

      网友评论

      • 我系哆啦:还没上swift3.0 :smile:
        故胤道长:@我系哆啦 下一篇就是3.0的语法了:smile:
      • Ryan文濤:博主,我想问下,对于假如没有算法底子的人学习算法的话。能推荐一些学习的书单吗?或者哪些
        zyg:在百度一搜 结果。。。(https://book.douban.com/review/5182383/) 大话数据结构 评价不怎么好
        Ryan文濤:@故胤道长 好的,谢谢。:smile:
        故胤道长:@Ryan文濤 先看《大话数据结构》,然后去刷《cracking the code interview》。想更进一步的话去看《算法导论》

      本文标题:Swift 算法实战之路:排序

      本文链接:https://www.haomeiwen.com/subject/bbzijttx.html