前言

上一篇文章里，笔者已经对链表、队列和二叉树的基本数据结构做了简单的介绍，附上前文链接：《iOS面试之道》算法基础学习(上) 。在这篇文章里，笔者继续把剩下的部分尝试着去解读，尽量会细致到每一行代码。另外本篇文章也只是笔者自己的理解，如果有理解错误的地方也希望大家进行指正。

关于算法部分后面的内容，主要是围绕一些通用算法进行了讲解。个人认为是本书含金量最高的部分，也是面试中比较常见的算法题目。

排序

关于排序的介绍，常见的主要有7种。冒泡排序、插入排序、选择排序、堆排序、归并排序、快速排序、桶排序。

在介绍每一种排序方法之前，先来看一些概念的的东西：

时间复杂度：在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间，通常用大O符号表示。

关于这7种排序算法的时间复杂度依次为：冒泡排序 = 插入排序 = 选择排序 > 堆排序 = 归并排序 = 快速排序 > 桶排序。

排序算法稳定性:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

关于排序算法稳定性真正的意义笔者认为可以分为2个方面：
1:在无意义数据面前，稳定性起到了避免无意义交换的作用，减少了元素交换的次数。
2:在有意义数据面前，每一个数据元素对应的可能是一个模型，若对模型中的某一属性进行排序，不稳定的排序方法改变了元素位置，其可能就影响了整个模型的排序。

所以时间复杂度和排序算法稳定性都是反映排序算法好坏的重要指标。接下来笔者会对每一种排序算法进行详细的介绍，并用Swift代码进行实现。

1.冒泡排序（稳定）

冒泡排序(Bubble Sort)顾名思义就像鱼儿在水底吐出的气泡，从底部会慢慢的漂浮到水面逐渐变大。代码层面表示就是序列中的元素，一步步的向着序列的一侧进行移动，最后达到我们希望的排序效果。直接来看代码：

func bubbleSort( _ array: inout [Int]) -> [Int]? {
   //i表示数组中依次比较的总次数
    for i in 0..<array.count {
         for j in 0..<array.count - i - 1) {
           //j表示下标，判断第j位和j+1位元素大小，进行排序
            if array[j] > array[j+1] {
                //元素左右进行交换
                let tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmp
            }                
        }
    }
    return array
}

注解：
1:每一次外层i的遍历，都会选出未排序数组中的最大值，放到右侧并固定位置。
2:每一次j的遍历，会根据左右元素进行大小比较，若左边数据较大则进行交换。

但是这样的写法并不优秀，如果我的数组部分有序，但通过上面的写法还是会对已经有序的元素进行不必要的判断，造成了时间复杂度的陡增。关于这个问题笔者会在之后的文章里介绍（链接：iOS冒泡算法优化）。

2.插入排序（稳定）

插入排序(Insert Sort)是对已经有序的序列插入新的元素，使其序列仍然有序。打个比方，就好像班级需要以高矮排成一队，排好队后发现有个同学来晚了，那这个时候就需要以这个同学的身高来和其他同学比较，插入这个队伍中。知道了概念，来看下代码。

func insertSort(_ array: inout [Int]) -> [Int]? {       
    //从1开始遍历，默认不清楚数组是否部分有序
    for i in 1..<array.count {
        //取出第i位元素 赋给临时变量 做后续比较
        let tmp = array[i]
        var j = i - 1
        //当比到最左边或临时变量tmp小于比较的元素时
        while j>=0 && tmp < array[j] {
            //比较的元素array[j]，向右移动一位
            array[j + 1] = array[j]
            //j-1，并继续和左边元素比较
            j -= 1
        }
        //临时变量tmp放到已排序好的数组的下一位
        array[j + 1] = tmp            
    }
    return array
}

注解：
1:外层i遍历，表示取出数组的第i位元素。例如:原数组[1,2,5,4]取出第i=1位的元素2，此时这个元素2可以理解为被取出来，使原数组变成[1,_,5,4]。
2:内层j循环，因为i的左边已经有序，所以根据第i的元素tmp和i左边的元素j进行判断，并根据返回结果插入合适的位置。

虽然说插入排序经历了2层遍历在时间复杂度上和冒泡排序是一样的，但是在比较次数上第一次是1，第二次是2，依次类推总共只需要比较1+2+...+N-1=N*(N-1)/2。并且元素一旦发现左边元素小就立即停止判断，效率上大大提高。

3.选择排序（不稳定）

选择排序(Selection Sort)是在一个待排序的序列中取出最小(或最大)的元素，然后放在已排好序的序列最后。示例代码按照从小到大进行排序，看下代码

func selectSort(_ array: inout [Int]) -> [Int]? {
    
    for i in 0..<array.count {
        //记录最小值的下标
        var k = i
        for j in (i + 1)..<array.count {
            //判断当前无序数组中的最小值
            if array[j] < array[k] {
                //k指向最小值下标
                k = j
            }
        }
        //若当前元素为其本身,不做交换
        if k != i {
            let tmp = array[i] 
            array[i] = array[k]
            array[k] = tmp
        }
    }
    return array
}

注解：
1:外层i循环首先会记录下标并赋值给k。
2:内层j循环通过遍历i的元素，并判断其大小，取出最小值下标，最后交换其位置，完成排序。

选择排序在时间复杂度上和冒泡、插入排序一样都是O(n^2)，但是其交换次数少于冒泡算法。

4:堆排序（不稳定）

堆排序(Heap Sort)是利用堆这种数据结构而设计的一种排序算法，是选择排序的一种。通过调整堆结构，将堆的顶部元素（即数组第0位元素）与末尾的元素进行交换，调整后将末尾元素固定，然后继续调整新的堆结构，每次调整固定一个元素，遍历结束后从而达到排序的效果。关于堆排序详细的介绍可以参考这篇文章:堆排序介绍。

下面的示例代码采取的是构建大顶堆，即升序排列，看代码

func heapSort(_ array: inout [Int]) -> [Int]? {
    
    //构建大顶堆 从最后一个非叶子结点倒序遍历
    for i in (0...(array.count/2-1)).reversed() {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(&array, i: i, length: array.count)
    }     
    //上面已将输入数组调整成堆结构
    for j in (1...(array.count - 1)).reversed() {
        //堆顶元素与末尾元素进行交换
        array.swapAt(0, j)
        adjustHeap(&array, i:0, length:j)
    }
    return array
}

func adjustHeap(_ array: inout [Int], i: Int, length: Int) {
    var j = i
    //取出当前元素i
    let tmp = array[j]
    var k = 2*i+1
    while k < length {
        //左子节点小于右子节点
        if(k+1 < length && array[k] < array[k+1]) {
            //取到右子节点下标
            k+=1
        }
        if(array[k] > tmp){
            //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            array[j] = array[k]
            j = k
        } else {
            break
        }
        k = k*2 + 1
    }
    //将tmp值放到最终的位置
    array[j] = tmp
}

注解：
1:在i循环方法中，首先将原始入参数组调用adjustHeap方法进行大顶堆的构建，目的是方便下面循环中堆顶与末尾元素进行交换操作。进行该遍历操作时需要注意该遍历采用的是倒序遍历的方式，即从最后一个非叶子结点开始。
2:j循环中，对已构建好大堆顶的数组进行堆顶元素与末尾元素的交换，并固定新的末尾元素，遍历结束即得到排序好的数组。
3: adjustHeap方法，是取根节点的下标i元素与其左右子节点对应元素进行大小比较，将最大值赋给根节点。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

5:归并排序（稳定）

归并操作(Merge Sort)是建立在归并操作的排序算法，是将需要排序的序列进行拆分，拆分成每一个单一元素。这时再按每个元素进行比较排序，两两合并，生成新的有序序列。再对新的有序序列进行两两合并操作，直到整个序列有序。
归并排序在性能上会明显优于前面几种排序方法，时间复杂度为O(nlogn), 看下书中给出的代码:

func mergeSort(_ array: [Int]) -> [Int] {
    //初始化辅助数组 默认数据0
    var helper = Array(repeating: 0, count: array.count)
    var array = array
    mergeSort(&array, &helper, 0, array.count - 1)
    return array
    
}

func mergeSort(_ array: inout [Int], _ helper: inout [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(_ array: inout [Int], _ helper: inout [Int], _ low: Int, _ middle: Int, _ high: Int) {
    //辅助数组接收 分割范围内的元素
    for i in low...high {
        helper[i] = array[i]
    }
    //helperLeft为分割部分左边的元素下标,helperRight为分割部分右边的元素下标，初始化时默认是第0位元素下标。
    var helperLeft = low, helperRight = middle + 1
    //合并后新序列的下标
    var current = low
    //判断子序列是否越界
    while helperLeft <= middle && helperRight <= high {
        //判断分割成的子序列元素大小
        if helper[helperLeft] <= helper[helperRight] {
            //对入参array数组进行赋值
            array[current] = helper[helperLeft]
            //判断左序列的下一位元素
            helperLeft += 1
            
        } else {
            //同上
            array[current] = helper[helperRight]
            //判断右序列的下一位元素
            helperRight += 1
        }
        //新序列下标向右移动
        current += 1
    }
    //不满足middle>=helperLeft return
    guard middle - helperLeft >= 0 else {
        return
    }
    
    for i in 0...middle - helperLeft {
        //将元素补齐
        array[current + i] = helper[helperLeft + i]
    }        
}

代码上面的注释都是笔者自己根据理解加上的，可能会有错误，读者可以根据代码来自行理解。

注解：
1:首先初始化辅助数组helper，和需要排序的数组一起传入mergeSort(::::)方法。
2:mergeSort(::::)通过递归，将入参数组进行拆分，直至为单一元素。
3: merge方法根据所传下标参数，对数组array进行拆分。并借助辅助helper数组完成array数组的排序操作。

归并排序理解起来会比前几种排序方法更难一些，学习时理解了归并排序的核心思想：拆分->排序->合并，再结合代码，就能事半功倍。

6:快速排序（不稳定）

快速排序(Quick Sort)是一种高效的排序方法，它利用了归并排序的思想，将需要排列的数组拆分成每一小部分，然后让每一小部分进行排序、合并，最后得到完整的排序序列。直接看代码：

func quickSort(_ array: [Int]) -> [Int] {
    //判断是否为单一元素
    guard array.count > 1 else {
        return array
    }
    //取出数组中间下标元素
    let pivot = array[array.count/2]
    //用到了函数式方法filter，过滤元素
    let left = array.filter{$0 < pivot}
    let middle = array.filter{$0 == pivot}
    let right = array.filter{$0 > pivot}
    //递归 对新数组进行合并
    return quickSort(_:left) + middle + quickSort(_:right)        
}

这部分代码比较简单，就不赘述了。

7:桶排序（稳定）

桶排序 (Bucket Sort)的工作原理是将数组分到n个相同的大小的子区间，每个子区间就是一个桶，然后将输入数组中的元素一一对应，放入对应子区间内的桶中。最后遍历每个桶，依次输入每个桶中对应装的数据即可。因为桶的顺序是有序的，所以只要从第一个桶开始遍历，得到的结果也就是有序的数组。看下代码：

func bucketSort(_ array: inout [Int]) -> [Int]? {
    
    //求出桶的数量
    let max = array.max()
    let min = array.min()
    let bucketCount = max! - min!
    
    //创建桶数组，桶个数=最大值-最小值+1，默认初值都为0。
    var bucket = Array(repeating: 0, count: bucketCount + 1)
    //遍历入参数组元素，并给桶做上标记
    for num in array {
        //数组元素减去最小值，指向桶数组下标
        let index = num - min!
        //将元素出现次数打上标记，每次+1
        bucket[index] += 1
    }
    //记录新数组下标
    var arrayIndex = 0
    
    //对桶内元素进行遍历
    for i in 0..<bucket.count {
        //取出每个桶的标记值
        var j = bucket[i]
        //当桶内有值，根据标记的次数依次减1，添加到数组中
        while j > 0 {
            array[arrayIndex] = i + min!
            j-=1
            arrayIndex+=1
        }
    }
    return array
}

注解：
1:输入为整数数组，所以先求出数组中的最大值和最小值，求出桶的数量，然后创建默认值为0的桶数组。
2:遍历入参数组array中的元素，并放入对应区间的桶中。
3:遍历桶数组，取出每个桶中的标记值。将桶中大于0的标记值所对应的区间值加入到数组中，返回数组。

桶排序的复杂度为O(n),也是上面所有排序方法中性能最好的，逻辑也比较简单。另外关于桶排序中有一点需要注意的是，创建的桶个数尽量应从最小值开始创建，如果只以最大值创建桶的数量，会造成不必要的内存开销。

上面的部分就是笔者根据常见的排序方法，进行的总结。因为书中只给出了归并排序和快速排序的写法，其他几种排序方法的代码实现都是笔者根据自己的理解结合网上资料进行的实现，所以可能会有表述错误的地方，还请大家指正。

搜索

最简单也是最直接的搜索就是遍历集合，然后找到满足条件的元素，但是当数据量巨大时，这样搜索的效率就显得非常的低下。关于搜索这块，主要介绍了二分搜索，这是一种复杂度更低O(logn),效率更高的搜索方法。

定义：

有序数组中，查找某一个特定元素的搜索，它从中间的元素开始搜索，若中间元素是要找的元素，则返回；若中间元素小于要找的元素，则要找的元素一定在大于中间元素的那一部分，所以只需要搜索此部分即可，反正亦然。

直接看代码：

func binarySearch(_ nums: [Int], _ target: Int) -> Bool {
    //初始化
    var left = 0, mid = 0, right = nums.count - 1
    //边界条件判断
    while left <= right {
        //求出有序数组下标
        mid = (right - left)/2 + left
        //判断当前中间元素与目标元素关系
        if nums[mid] == target {
            //等于mid
            return true
        } else if nums[mid] < target{
            //在mid右边
            left = mid + 1
        } else {
            //在mid左边
            right = mid - 1
        }
    }
    return false
}

代码比较简单，通过不断取有序数组的中间值，和目标数值进行比较，不断遍历最后等到结果。关于二分算法，书中最少还介绍了通过递归来完成二分搜索，就是把上述while进行了整合，其原理也是相同的。

实战例题：有一个产品发布了多个版本，他遵循以下规则，若其中一个版本崩溃了，则其后面的所有版本都会崩溃。

关于这样的题目，可以将产品的所有版本号看做一个数组，我们可以通过二分法的操作，来判断数组的中间值是否崩溃，若崩溃则更最早出现崩溃的版本在数组的左边，若不崩溃则出现在右边。这样通过不断缩小范围，确定第一个崩溃的版本。
具体的实现，需要注意的是当在数组左边时，我们的right就不能做-1的操作了，因为此时也不清楚该mid版本是否是我们需要求的第一个版本，其他的代码与上面原理代码类似，就不再赘述了。

总结

这篇文章里面笔者主要把书中后续的排序和搜索的定义与实现进行了介绍，希望能真正帮助到刚接触算法的开发者们。最后关于这部分内容，笔者认为是面试中最常考到的知识点，只要稍微花上几个小时，在运用和面试中都能游刃有余。