iOS开发快速进阶与实战

《iOS开发快速进阶与实战》是作者丰富的iOS项目开发经验的总结，书中实例均为真实的开发任务与场景，并包含典型面试题目的解析。 

《iOS开发快速进阶与实战》偏向于iOS应用的实际开发，介绍了iOS开发过程中的技术实现方案和原理，包含基本知识、底层常用技术原理、开发技巧，以及技能扩展等书各方面，其中大部分章节以实际项目开发中常见的问题为背景，内容阐述方式包括介绍原理、对比技术方案、实际应用、引导读者思维等，并在每一章*后部分归纳总结本章的重点内容。
本书既可以作为高等学校计算机软件技术课程的教材，也可以作为企业iOS开发人员的技术参考书。

90后移动开发者，简书作者。曾参与多个移动端项目架构搭建和开发。现任饿了么（上海拉扎斯信息科技有限公司）iOS高级工程师，负责开发饿了么商家端项目。在简书、新浪微博以及个人博客上分享过多篇技术文章。

目录

第1章iOS的类

 

1.1创建并描述一个类

 

1.2类方法的self

 

1.3类属性

 

1.4黑魔法

 

第2章底层实现分析

 

2.1内存分区

 

2.2初始化

 

2.3拷贝

 

2.4数组与集合

 

2.5字典与哈希表

 

2.6KVC

 

2.6.1对象关系映射

 

2.6.2对私有属性访问

 

2.6.3控制是否触发setter、getter方法

 

2.6.4KVC进阶用法

 

第3章开发原理相关

 

3.1定时器的引用

 

3.2动画事务

 

3.3响应链

 

3.4UITableViewCell高度

 

3.5图片初始化

 

3.6静态库与动态库

 

3.7离屏渲染

 

3.8约束动画

 

第4章线程安全——锁

 

4.1NSLock

 

4.2synchronized

 

4.3pthread

 

4.3.1互斥锁(普通锁)

 

4.3.2递归锁

 

4.3.3pthread信号量

 

4.3.4读写锁

 

4.4信号量

 

4.5NSConditionLock与NSCondition

 

4.5.1NSConditionLock

 

4.5.2NSCondition

 

4.6自旋锁

 

4.7递归锁

 

小结

 

第5章排序算法

 

5.1冒泡排序

 

5.2选择排序

 

5.3插入排序

 

5.4快速排序

 

5.5希尔排序

 

5.6归并排序

 

5.7堆排序

 

5.8基数排序

 

小结

 

第6章技能进阶与思考

 

6.1按钮的图文位置

 

6.2创建Pod库

 

6.3子控制器

 

6.4APP状态恢复

 

6.5APP编译过程

 

6.6APP启动

 

6.7多线程

 

6.7.1GCD

 

6.7.2NSOperation

 

6.8继承与多态

 

6.9缓存

 

6.10字数限制

 

参考文献

 

前言成书背景移动互联网经过近几年的快速发展，已日趋成熟稳定，在极大方便人们生活的同时，也正在悄悄改变人们的生活方式。互联网现已从PC端逐步划分出移动端的大群体，手机也不仅局限于其传统打电话发短信等基本功能，高速上网更满足当代人的生活需求。由上网衍生出来的手机功能包括即时通信、新闻资讯、视听娱乐、游戏、支付转账、生活工具等，这些都是移动互联网的代表领域，其中不乏有很多知名的应用为大众所知。智能手机的发展也一直在接受移动互联网发展的检验，从发展之初的Windows Mobile(Windows Phone前身)，到塞班、黑莓，再到现在的iOS、安卓、Windows Phone，智能手机在发展之初无时无刻不经历着大风大浪，或许今年还是非常受欢迎的操作系统，明年市场份额就所剩无几。就目前而言，移动端操作系统主要分为iOS和安卓，这两者现今几乎占据了全部智能手机的市场份额，移动应用大部分只会考虑这两个方向。iPhone自问世之初，一直以惊艳闻名，在随后智能手机发展的过程中，也一直引领设计和硬件功能的创新，不仅于此，iPhone的用户体验和操作系统的流畅度一直是被用户喜爱的主要原因。开发iPhone应用称为iOS开发，不是对其操作系统的开发，而是开发基于iOS系统运行的应用程序。对于iOS开发，有ObjectiveC和Swift两种语言，但仅仅是在语法和编程方式上有较明显的差异，其主要实现方式往往没有太大的区别。关于本书本书是按照章节进行大致划分，内容之间没有依赖顺序关系，每一节的知识点都是相互独立的，读者可以根据自身情况进行选读和跳读。本书内容主要包括三个方面： 一是以开发中遇到的实际问题为例，列出的场景都是实际开发中常见的开发任务，在这些章节内容主要以实践为主，并附上了详尽的代码实现过程； 第二个是偏向理论的内容，主要以面试题为基础进行深入的分析，旨在让读者不再死记硬背面试题，而是根据内容去理解这些理论的原理或实现过程； 后一个是技能进阶，针对问题的实现方式从不同角度给出实现方案，后通过理论比较得出解，或者对于某些问题提供比较巧妙的解决办法，开拓读者的思考方式。笔者自iOS 6开始接触，虽然算不上是早的一批开发者，却也总结了一些个人开发经验。 本书内容是笔者自从事iOS开发以来的所有总结的整理。书中的内容主要以理论和实践为主，从提出问题到分析问题，再到解决问题，包括部分章节内容以使用场景带入，都是实际开发中所经常遇到的问题。整部书从准备到写成，持续了有近一年的时间，其实时间还是蛮紧张的。大部分的章节内容，从提出，到叙述，到举例，到论证，后到总结是一个严谨的流程，不同于写个人博客。书籍和博客虽然是优秀的知识传播媒介，但不足之处在于阅读时不一定能够理解作者真正想表达的意思，特别是对于技术开发这种实践性较强的情况。本书的内容花了很大的篇幅讲述了理论性的知识，示例代码作为其辅助说明的手段。或许读者能够在阅读时产生共鸣，因为可能遇到过相同的问题或者对于问题有相同的理解，但笔者建议读者能够更多地将章节内容以实践运用的方式来加深自我理解。另外，本书中的内容都是以知识点的形式，相对独立化，而在实际开发中又是另一回事，例如，需要考虑代码复用性，以及编程思想的运用，这些都需要读者对其熟练地使用，而不仅仅是了解。基本上所有的开发者都有学习过其他开发者优秀的代码或文章，提升自我能力的前提是站在巨人的肩膀上，可以使自己少走很多弯路，同时也飞速提升了自我实力。因此笔者也希望能够以这本书给读者带来一些真正意义上的帮助。本书中的示例代码都是在Xcode 8.x下运行，书中的示例代码仅考虑iOS 8以上，语言以ObjectiveC为主，部分内容涉及Swift。由于笔者能力有限，书中难免存在疏漏和不足之处，因此特地在GitHub上开了一个仓库，有任何意见和建议的读者，欢迎来这里提出，地址： https://github.com/huangxinyu1213/iOSAdvancedbook。目标读者对于现在的编程来说，其编程语言变得越来越高级，使得开发门槛越来越低，开发者不必过多接触底层的实现，以及去写一些复杂的代码。就类似于iOS开发的ObjectiveC和Swift这两门语言一样，虽然是两种完全不同的开发语言，但开发者从ObjectiveC开发转到Swift开发其实并不是一件很难的事情，因为对iOS的CocoaTouch框架的使用，两门语言基本无异，这也从另一个角度可以证明，高级语言有很多的共同性，开发语言只是一种实现方式。另一方面，市面上现在有很多对于iOS开发基础的图书和教程，包括苹果的官方文档，对于初学者来说，都是很好的入门资料。本书可能并不适合iOS初学者，因为本书并不打算从iOS的基础内容开始讲起，而更适合于一些有iOS开发基础的初中级开发工程师参考。主要内容本书内容不涉及iOS开发的基础知识，由一个个相互独立的知识点组成章节，主要是以进阶为目的，帮助开发者更高效地运用iOS开发技术。主要内容包括以下各章。第1章： iOS的类类是面向对象的基础，iOS的类不仅是实现面向对象，还有一些值得关注的特性和原理。第2章： 底层实现分析iOS开发中，系统为开发者提供了许多便捷和强大的基础功能，避免写一些过于复杂的底层实现代码，使编程人员只需要更加注重于代码和业务本身。第3章： 开发原理相关主要介绍开发中常用技术以及实现的原理，同时也会对一些技术给出不同的实现方案，并做出比较，让开发者对一些原理知识能够有比较明确的认识。第4章： 线程安全——锁线程安全是iOS开发中避免不了的话题，随着多线程的使用，对于资源的竞争以及数据的操作都可能存在风险，所以有必要在操作时保证线程安全。第5章： 排序算法对算法的掌握是非常有必要的，不仅是在面试中经常会考算法，在实际应用中，算法的使用能更高效地处理数据。同时算法的思想也能更好地帮助我们理解计算机语言。第6章： 技能进阶与思考本章内容更偏向于实际场景的应用和实现方式的思考，以及扩充开发者的知识宽度。电子资源笔者提供书中所有实例的源代码，读者可以从清华大学出版社网站www.tup.com.cn下载。本书使用与资源下载的相关问题请联系[email protected]。
编者2018年5月

第5章排序算法
APP开发是对计算机语言的应用，当然也需要涉及对算法的使用。虽然作为iOS开发，似乎接触更多的是对界面和数据的处理，但对于开发第三方库以及底层框架，会有很多场景需要采用适当的算法，例如，APP的缓存策略，需要有一些算法来保证缓存的重用或销毁，诸如此类等。不管是什么开发语言，对算法的掌握是非常有必要的，不仅是在面试中经常会考算法，在实际应用中，算法的使用能更高效地处理数据。同时算法的思想也能更好地帮助我们理解计算机语言。本章内容： ■冒泡排序■选择排序■插入排序■快速排序■希尔排序■归并排序■堆排序■基数排序排序算法是算法中一个比较常见的知识点，主要功能是对一个乱序数组进行排序，为了达到更少的计算量，对一些排序方法进行了命名，其中比较出名的8大排序算法是： 冒泡排序，选择排序，希尔排序，快速排序，归并排序，堆排序，基数排序。如果不涉及架构方面，以及多重计算优化的话，算法其实并不常用，当然在很多比较大的公司的面试题中，算法是一个比较重要的考察方面，并且考察的算法主要就是排序算法和二叉树。而在面试排序算法中，主要考察的排序并不是全部的8大算法，主要分为三个层次： ①手写冒泡排序； ②了解冒泡、选择、快速排序，并以伪代码形式写出； ③除了前面两个层次，需要对剩下的排序算法有了解，并可以简单说出原理。这是面试题中关于考算法的三个等级，一般的公司不强求算法的话都只要求掌握个就行了，而大一些的公司，例如BAT，需要掌握到第二个层次，而第三个层次基本上没有公司会考到，当然不排除有些主攻算法的面试官会问到，所以这里对所有的排序算法进行分析讲解，希望读者们在以后的面试算法中能够轻松应付。由于ObjectiveC的数组和字典不能存储值类型、结构体，也就是包括int、NSInteger、BOOL、CGRect类型都不能直接存储，需要转换成NSNumber或者NSValue来存储。所以为了展示排序算法，我们采用Swift语言来实现，首先Swift相比于ObjectiveC来说不区分可变和不可变数组，另外，Swift的数组和字典属于值类型，并且可以存储基本数据类型，甚至是nil也可以。5.1冒泡排序这是8大排序算法中简单的排序，这里也不做详细介绍，代码如下。

func BubbleSort(arr: inout ［Int］) -> ［Int］ {
for i in 0..for j in i 1..if arr［i］ > arr［j］ {
let tmp = arr［i］
arr［i］ = arr［j］
arr［j］ = tmp
}
}
print(arr)
}
return arr
}

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
print(BubbleSort(arr: &arr))

这里需要直接对传递进来的数组进行修改，所以函数在参数上要设置添加inout标识符表示这个数组可以与在函数内保持同一份，因为数组是值类型。虽然是简单的冒泡排序，我们也来分析一下，首先层循环从头到尾，每次将数组的每一位，通过第二次循环依次与之后的每一位进行比较，如果比后面某一个数大的话就与其交换。我们根据代码来进一步分析，首先外传循环次，进入内循环，i是0，j是1到arr.count-1，次内循环将arr［0］与arr［1］比较，也就是2与1比较，因为2是比1大的，所以交换，但是注意，内循环第二次的时候，是arr［0］与arr［2］比较，这时的arr［0］已经是1了，同理，从arr［2］开始到后，遇到数字0时会与1再交换一次，所以次内循环一遍结束后数组的情况是： 

［0, 2, 5, 9, 4, 1, 6, 3, 8, 7］

然后外循环第二次，将2与后面的数字进行比较，后发现1比2小，进行交换，并且之后没有比数字1更小的了，所以第二次循环结束后数组情况是： 

［0, 1, 5, 9, 4, 2, 6, 3, 8, 7］

同理接下来的每次如下： 

［0, 1, 2, 9, 5, 4, 6, 3, 8, 7］
［0, 1, 2, 3, 9, 5, 6, 4, 8, 7］
［0, 1, 2, 3, 4, 9, 6, 5, 8, 7］
［0, 1, 2, 3, 4, 5, 9, 6, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 7, 9, 8］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］

综合起来可以发现，每次都是将数组中剩下数字的小值找出来，类似于冒泡泡一样，终得到排好序的有序数组。当然也可以改变代码的实现逻辑，每次循环将数组剩下数字的值找出来放在数组的后面，这也是可以的。冒泡排序的时间复杂度是O(n2)。5.2选择排序选择排序与冒泡排序有些类似，但比冒泡要更好一些，代码如下。

func selectSort(arr: inout ［Int］) -> ［Int］ {
for i in 0..var minIndex = i
for j in i 1..if arr［minIndex］ > arr［j］ {
minIndex = j
}
}
if i != minIndex {
let tmp = arr［i］
arr［i］ = arr［minIndex］
arr［minIndex］ = tmp
}

print(arr)
}
return arr
}

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
print(selectSort(arr: &arr))

打印结果： 

［0, 1, 5, 9, 4, 2, 6, 3, 8, 7］

［0, 1, 5, 9, 4, 2, 6, 3, 8, 7］
［0, 1, 2, 9, 4, 5, 6, 3, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］

通过打印结果可以看出，选择排序也是在外层循环每次结束将数组剩下数字的小值找出来，放在已排好序的末尾，结果是一样的，但是在实现逻辑上，选择排序会更好一些，因为在选择排序中，都是通过记录小值的index来获取小值的位置，后才进行交换，少做了无用功。但是时间复杂度仍然是O(n2)。5.3插入排序插入排序是比较直观的排序算法，将数组从头至尾依次通过交换向前排至正确的位置。

func insertSort(arr: inout ［Int］) -> ［Int］ {
for i in 1..let temp = arr［i］
var j = i
while j > 0, temp < arr［j – 1］ {
arr［j］ = arr［j-1］
j -= 1
}
arr［j］ = temp
print(arr)
}
return arr
}

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
print(insertSort(arr: &arr))

打印结果： 

［1, 2, 5, 9, 4, 0, 6, 3, 8, 7］
［1, 2, 5, 9, 4, 0, 6, 3, 8, 7］
［1, 2, 5, 9, 4, 0, 6, 3, 8, 7］
［1, 2, 4, 5, 9, 0, 6, 3, 8, 7］
［0, 1, 2, 4, 5, 9, 6, 3, 8, 7］
［0, 1, 2, 4, 5, 6, 9, 3, 8, 7］
［0, 1, 2, 3, 4, 5, 6, 9, 8, 7］

［0, 1, 2, 3, 4, 5, 6, 8, 9, 7］
［0, 1, 2, 3, 4, 5, 6, 7, 8, 9］

之所以插入排序是一种比较直观的排序方法，是因为插入排序用语言来描述的话是非常简单的，在无序数组中，从第1位开始(前面有第0位)，与前面的已排好序的数中从后往前比较，直到插入在这个数所在顺序的位置中，以此类推。在如上代码中，for循环从1开始，利用temp存储arr［1］的值，然后与arr［1］之前的数进行比较，也就是arr［0］，由于arr［0］比arr［1］大，则将arr［0］的值赋给arr［1］，由于arr［1］就一位，所以while结束，此时将temp存储的数赋给arr［0］，达到移动值的目的，此时数组已成为： 

［1, 2, 5, 9, 4, 0, 6, 3, 8, 7］

第二轮循环开始，从arr［2］开始，将temp赋值为arr［2］，也就是5，拿5与前面的依次比较，直到找到比5大的数，由于5比1和2都大，找到左边都没有，所以将存储的temp仍然返回给arr［j］，即arr［2］。直到数字6的时候，temp为6，此时数组已经为： 

［0, 1, 2, 4, 5, 9, 6, 3, 8, 7］

将0与前一位比较，没有9大，则将6的位置赋值为9，此时数组为： 

［0, 1, 2, 4, 5, 9, 9, 3, 8, 7］

再与前面比较，比5大，则break while循环，同时将记录的j的位置替换为原来的temp，所以此次循环结束的数组为： 

［0, 1, 2, 4, 5, 6, 9, 3, 8, 7］

之后以此类推，完成整个排序算法。虽然上面用了很浅显的文字描述了插入排序的过程，但是插入排序确实是逻辑上很清晰的排序算法。举个例子， 10个人按身高排队，先找个人出来站好，再找第二个人来与个比较身高，高则站后面，矮则站前面，同理，后面再有人来排队的话，只要与站在后面的人依次向前比较，就能找到正确的位置。插入排序相当于冒泡排序和选择排序来说，是一种值移动的方法，而冒泡和选择排序是产生中间变量用于交换，所以在数组个数不大的情况下插入排序是要优于冒泡和选择排序的。由于仍然是需要两轮循环，所以插入排序的时间复杂度仍然是O(n2)。5.4快速排序快速排序又叫二分排序、二分插入排序、折半排序，相比于前几种排序算法，是一种真正体现出算法优越性的排序。快速排序有些是在插入排序的基础上，使用二分查找的方式，将一个list划分为两个list来执行，所以在时间复杂度上有很明显的优势。代码如下。

func partition(arr: inout ［Int］, left: Int, right: Int) -> Int {
var left = left
var right = right
let pivot = arr［left］

while left < right {
while left < right, arr［right］ >= pivot {
right -= 1
}
arr［left］ = arr［right］
while left < right, arr［left］ <= pivot {
left = 1
}
arr［right］ = arr［left］
}
arr［left］ = pivot
return left
}

func quickSort(arr: inout ［Int］, left: Int, right: Int) {
guard left <= right else {
return
}

let pivotIndex = partition(arr: &arr, left: left, right: right)
quickSort(arr: &arr, left: left, right: pivotIndex – 1)
quickSort(arr: &arr, left: pivotIndex 1, right: right)
}

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
quickSort(arr: &arr, left: 0, right: arr.count – 1)
print(arr)

我们将快速排序的算法分成两个函数，这是采用了二分查找与分治的思想，partition函数采用二分查找，获取划分的界限，从而将问题分解为更小的问题来解决。事实上，我们可以将partition放在快速排序的函数体内，成为其私有的函数，从而体现完整性，不过这里暂且只讨论算法，所以不做考虑。可以从代码中看出，partition函数是将数组的某一区域进行一个简单的排序划分，获取到划分的位置，根据其位置再将数组划分为两个区域，然后分别递归调用快速排序函数。接下来根据数组以及代码详细分析一下排序过程。我们传递的数组是［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］，并且传递了数组的一个区域，表示在该区域里执行。当然在外层调用快速排序的就是整个数组的区域，即0~arr.count-1。进入quickSort函数，由于数组个数至少是大于1的(个数为0或者为1没有必要排序)，所以执行partition函数，partition函数是快速排序的要点所在，接下来，我们调用partition函数传递的参数，仍然是该数组以及其整个范围。鉴于Swift的参数默认为let不可修改，所以可以使用同arr参数类似的inout修饰，但这将使整个函数显得过于冗杂，因此在partition内创建同名的局部变量left、right，并且记录区域的个值pivot为arr［left］，我们称其为比较数，然后便开始while循环了。外层循环是left一定要小于right的，因为内部查找是从数组两边往中间合拢的，当left大于或等于right则表示此次遍历交汇了，即查找完毕。详细看一下内部代码，内部个while循环表示，从数组右侧开始，在仍然满足left小于right的情况下，一直找到比比较数pivot小的数，数组一开始如下： 

［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］

一开始left为0，right为9，pivot为arr［0］，即2。接着刚才的分析，从数组right位开始向前(右)找，一直找到比2小的数，即arr［5］=0。然后跳出内部个循环，此时left为0，right为5，执行语句： 

arr［left］ = arr［right］

此时数组为： 

［0, 1, 5, 9, 4, 0, 6, 3, 8, 7］

可以看到第0位已经被arr［5］覆盖了，接着执行内部下一个循环。相反地，仍然在left小于right的情况下，从left开始向后(左)一直找出比pivot大的值，即比2大的值，结果在第2位找到了，因为第2位是5，因此跳出循环。此时，left为2，right为5，接着执行语句： 

arr［right］ = arr［left］

此时数组为： 

［0, 1, 5, 9, 4, 5, 6, 3, 8, 7］

将第5位的0赋值为第2位的数5，此时外部while循环执行一遍结束，仍然满足left小于right条件，所以继续while，此时left为2，right为5，pivot值为2。同理，从right开始向后查找比pivot小的数，right从5一直到2，也没有找到比pivot小的数，而此时left已经等于right了，所以外层的while循环结束了。结束后，left为2，right为2，执行语句： 

arr［left］ = pivot
［0, 1, 2, 9, 4, 5, 6, 3, 8, 7］

后，将left的值2返回出去，至此partition函数执行结束。这时可以看到底partition函数做了什么？在函数一开始的地方，我们设置数组位2为我们的pivot比较值，后得到的结果是将2排到了正确的位置，并且比2小的数都在其左边，比2大的数都在其右边，但是左右也并非是有序的。我们将2返回给了quickSort函数内部的局部变量pivotIndex，这表示已经将该位置确定好，接下来只要同理分别执行两边的数组就能达到目的。quickSort(arr: &arr, left: left, right: pivotIndex-1)调用表示将arr［2］左边的区域再次进行划分，quickSort(arr: &arr, left: pivotIndex 1, right: right)调用表示将arr［2］右侧的区域再次进行划分，这样在每个划分的区域内确定其比较值的位置，当划分到小单位时，整个数组就排好序了。其时间复杂度为O(nlogn)。5.5希尔排序前面介绍了4种排序： 冒泡排序，选择排序，插入排序和快速排序。这是4种常见的排序方法，而后面介绍的4种排序或许读者只是听过，却很少接触过，对于一般的排序事务，前面4种排序已然足够应付，况且快速排序是8大排序中效率的，自然而然后面这4种排序就很少有人问津了，但作为了解以及算法思路还是值得学习的。希尔排序又称为缩小增量排序，是插入排序的进化版，但与插入排序不同的是，希尔排序将子序列按照某个增量值进行排序，随着增量值的变小，整个数组形成了一个大致排好序的序列，后按照增量1一个数一个数地直接进行插入排序，整个过程避免了很多重复的交换值操作。但希尔排序是一种非稳定的排序算法，所谓非稳定性，指的是对于数组中两个相同的元素，可能在排序之后顺序发生变化，即使两个数大小相同。希尔排序中两个相同的数可能会因为增量划分到不同的组中，导致后排序好之后两个数位置发生了变化，因此不稳定。代码如下。

func shellSort(arr: inout ［Int］) {
var gap = arr.count / 2
while gap >= 1 {
var i = gap
while i < arr.count {
let temp = arr［i］
var j = i – gap
while j >= 0, temp < arr［j］ {
arr［j gap］ = arr［j］
j -= gap
}
if j != (i – gap) {
arr［j gap］ = temp
}
i = 1
}
gap = gap / 2
}
}
var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
shellSort(arr: &arr)
print(arr)

希尔排序的算法并不复杂，可以看出有插入排序的影子。首先定义初的增量值，为数组个数的一半，在例子中，gap值即为5。在gap始终大于等于1的情况下，先将gap值赋给i，即i为5，j为0，记录arr［5］的值给temp，即temp = 0，然后便开始增量排序了，首先将temp与arr［0］比较，即arr［5］与arr［0］比较，如果arr［0］比temp大，则应将arr［5］赋值为temp，此时数组由： 

［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］

变成了

［2, 1, 5, 9, 4, 2, 6, 3, 8, 7］

j -= gap，表示将temp与该组中下一位进行比较，此时j已经为-5，跳出循环了，同理，后判断j是否不等于(i – gap)，如果不等于，则表示j已经自减过，也就是表示更换过数，所以将temp的值赋给后j gap的那一位，在此处，j gap是0，即将temp存储的值赋给arr［0］，从而达到交换的目的。同理，arr［6］与arr［1］比较，arr［7］与arr［2］比较，一直到arr［9］与arr［4］比较，这时增量为5的循环结束，自除以2，增量为2，再次按照如上逻辑进行插入排序，这次会形成较为有序的数组。直到增量为1，真正的插入排序，此时只要做比较少的操作就可以了。为了方便读者理解，再举个例子，例如一群身高不一的学生站成一排，然后0~4报数，报数完毕后，先让报0的同学站出来，按照插入排序的方法进行排序，这时，报0的同学排好身高位置后归队，同理报1的同学站出来排列，一直到一轮结束后，再按照0、1报数，同理，再次细分、排序，一直到后，所有同学再进行逐个插入排序，由于上一次已经排好一部分，所以这一次并不会做太多操作就能实现整个希尔排序。从宏观角度上看，希尔排序每次先一轮排序都为下一轮排序提供了有利条件，从而避免了重复的无用交换，从而达到对插入排序的优化。希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长，所以插入排序的元素个数很少，速度很快； 当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。5.6归并排序归并排序又称为二路归并，是采用分治法典型的例子，其基本思想是将整个数组的排序问题递归划分为子序列，后层层往上合并为一个有序序列，直至终实现全部排序完成。代码如下。

func mergeSort(arr: inout ［Int］, left: Int, right: Int) {
guard left < right else {
return

}
let mid = (left right) / 2

mergeSort(arr: &arr, left: left, right: mid)
mergeSort(arr: &arr, left: mid 1, right: right)

var temp: ［Int］ = Array(repeatElement(0, count: right – left 1))
var i = left
var j = mid 1
var k = 0

while i <= mid, j <= right {
if arr［i］ <= arr［j］ {
temp［k］ = arr［i］
k = 1
i = 1
} else {
temp［k］ = arr［j］
k = 1
j = 1
}
}
while i <= mid {
temp［k］ = arr［i］
k = 1
i = 1
}
while j <= right {
temp［k］ = arr［j］
k = 1
j = 1
}
for p in 0..arr［left p］ = temp［p］
}
}

通过代码的前7行可以看到归并排序的大概分治逻辑，即将数组按照折半来逐级划分，直至划分到left=right，也就是划分的子序列仅有一个元素，也就是划分到了小的单位，随后，每一层级执行下面的代码，将当前区域left至right的数组变成有序的。首先创建一个含有right-left 1个元素的数组，数组每个元素都暂且为0，作为存储用。由于该区域是下一级返回过来的，所以在left至right区域中，left到mid是有序的，mid 1至right也是有序的，现在就是要将left至right再排序，所以做法是将两个区域从小的值开始比较，然后将较小值存入temp中，再与较小值所在区域的下一位进行比较，直至某一区域的元素检索完，将另一元素的剩下元素全部赋值给temp剩下的位置，这样temp就得到了一个在left至right的有序数组。这是实现了该区域的排序，当然这不是终点，而只是众多分治中的某一步，接下来就返回上一级的分治之中，将该区域的有序数组与邻近区域的有序数组再次合并为另一个更大的有序数组，如此到后实现排序的全部完成。由于采用的是较为容易理解的分治递归思想，使归并排序看起来并不复杂，并且时间复杂度为O(nlogn)，是一种效率较高且稳定的算法。5.7堆排序堆排序是这几个排序中逻辑稍复杂的算法，之所以显得有些复杂，是因为堆排序涉及一个新概念，就是堆，堆的数据结构可以看作一个完全二叉树。二叉树是每个节点多只有两个子树的树结构，类似于图51的树状结构就称为二叉树。

图51二叉树

而完全二叉树是深度为h，有n个节点的二叉树，当且仅当其每个节点的编号都与深度为h的满二叉树中从1至n的节点编号一一对应。换句话说，我们生成一个完全二叉树，是从左至右依次添加到树结构上，如图52所示的二叉树即为完全二叉树。

图52完全二叉树

本节中堆的结构就大致是完全二叉树的结构，而在下面对堆排序的实现中，也是通过这种结构来实现的。而二叉树的结构与数组的对应关系也是比较简单的，即数组中每个数所在的位置对应于完全二叉树的节点顺序。例如，我们排序中用到的数组： 

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］ 

图53数组的完全二叉树表示

用完全二叉树表现如图53所示。
而这样的完全二叉树结构还不能称为堆，因为堆还有两个条件： (1) 堆的元素或者小元素出现在堆顶； (2) 堆的父节点的值都是大于或者小于其子节点的值。其实，如果满足第二个条件，个条件也自然成立，根据以上对堆的定义，以及堆的元素顺序，可以分为堆和小堆，即父节点大于子节点的称为堆，反之称为小堆。在之前的排序中，都是将数组排成从小到大的顺序，此例中，采用堆或者小堆都可以实现，下面看一下代码。

func maxHeapify(arr: inout ［Int］, index: Int, size: Int) {
var i = index
while true {
var iMax = i
let iLeft = 2 * i 1
let iRight = 2 * i 2

if iLeft < size, arr［i］ < arr［iLeft］ {
iMax = iLeft
}
if iRight < size, arr［iMax］ < arr［iRight］ {
iMax = iRight
}
if iMax != i {
let temp = arr［iMax］
arr［iMax］ = arr［i］
arr［i］ = temp
i = iMax
} else {
break
}
}
}

func buildMaxHeap(arr: inout ［Int］) {
let lastParent = arr.count / 2 – 1
for i in (0…lastParent).reversed() {
maxHeapify(arr: &arr, index: i, size: arr.count)
}
}

func heapSort(arr: inout ［Int］) {
buildMaxHeap(arr: &arr)
for i in (1…arr.count – 1).reversed() {
let temp = arr［0］
arr［0］ = arr［i］
arr［i］ = temp
maxHeapify(arr: &arr, index: 0, size: i)
}
}

var arr = ［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］
heapSort(arr: &arr)

我们将堆排序分成了三部分代码，heapSort是主方法，buildMaxHeap是创建堆(本例中采用堆来实现从低到高的排序，这并不冲突)，maxHeapify是对节点index进行调整。

图54数组建堆前

在解释这段代码之前，先图解一番其过程。数组［2, 1, 5, 9, 4, 0, 6, 3, 8, 7］用二叉树来表现如图54所示。

接下来，将对这个二叉树进行构建成堆，首先从后一个父节点开始。首先确定一下对于父节点和子节点的公式。对于节点i来说： i的父节点为： (i-1)/2i的左子节点为： 2×i 1i的右子节点为：  2×i 2并且对于节点i来说，是必有父节点的，但其左子节点和右子节点不一定有，因为节点i可能为叶子节点。接下来的任务是构建成堆，堆的定义在之前讲过，是在完全二叉树的基础上对于任一节点的值都大于其左右子节点，所以我们从这个二叉树的后一个父节点开始查找并替换。而后一个父节点即是数组的后一个元素的父节点，为(arr.count-1) / 2，即第4位，正好也为4。判断第4位与其左右子节点的大小，由于只有左子节点，所以将其和左子节点比较，又因为arr［4］ < arr［9］，子节点大于父节点，所以替换，如图55所示。
由于arr［4］的子节点是叶子节点，所以不能继续向下查找判断，此轮循环结束，寻找下一个父节点arr［3］，arr［3］的值为9，在图55所示二叉树中有两个子节点，但值9是比值3和值8大的，也就是arr［3］比其两个子节点的值都大，所以不用交换，并且也不用向下执行，此循环结束。下一个循环，arr［2］值为5，其右节点的值6大于值5，所以交换，如图56所示。

图55建堆过程1

图56建堆过程2

接下来到父节点arr［1］，其左节点比arr［1］大，交换，如图57所示。
然而到这里，由于其左节点arr［3］为父节点，同时arr［3］的右子节点比当前的arr［3］的值大，所以继续交换，如图58所示。此时可能有读者会有疑问，如果arr［3］的某个子节点会有比值9还大的存在，该如何与arr［1］进行交换呢？实际上，我们之所以从后一个父节点开始往上遍历，为的就是如果在

图57建堆过程3

图58建堆过程4

某一节点，例如节点a与其子节点b比较大小的时候，子节点b也为父节点，能够保证a的这一子节点b已经是比b的子节点都大。简单总结一下就是，

图59建堆过程5

如果某一节点小于其某一子节点，那么交换后，该节点肯定大于其任意子节点，以及孙子节点。结合上面过程可以理解为，值9一开始是值3和值8的父节点，即使值9被交换上去了，仍然是大于值3和值8的。继续到节点arr［0］，已是堆顶，此时arr［0］值2，比其左子节点值9小，交换，得到图59。
但是此时arr［1］小于左子节点arr［3］，交换后仍然小于arr［7］，再交换。这一过程如图510所示。

图510建堆过程6

至此，该完全二叉树已经满足堆的条件，所以可以称此时的完全二叉树为堆。同时，以上图解的这一过程，我们称之为堆调整，目的就是将一个不满足堆的完全二叉树，通过交换，后成为一个堆结构。再对比之前的堆排序代码，可以看到如上过程就是函数buildMaxHeap的过程，其中对于某一节点进行查找子节点并交换是由函数maxHeapify完成的。至此已经完成了堆排序复杂的一步了，接下来就很好理解了。
通过如上的操作，现在将值9置换到了堆顶，堆顶也是数组中的首元素arr［0］，接下来需要将值9再交换至函数后，如图511所示。

图511建堆过程7
有读者可能会有疑问，为何要将值交换至末尾？这是因为，我们刚刚通过堆排序，找到了数组中的值，由于是从小到大的顺序，所以每次将堆排序结构中的值找出来依次放在末尾，就可以实现完整的排序了。此时值9已经被交换至末尾，我们在函数heapSort中缩小size，表示接下来的构建堆以及寻找值，都是除了arr［9］，在其之前操作。同时由于值4被交换至堆顶，此时以及破坏了堆的结构，所以要重新对堆顶进行检查，注意此时，因为已经不管值9了，并且在现在的二叉树的操作范围内，我们只改动了堆顶节点，对于其他父节点，仍然保持大于子节点的特性，所以此时只要对堆顶节点进行操作即可，操作方法即为函数maxHeapify。以此类推，我们每次构建一次堆，都能找出剩下元素中的值，并将其排列在数组第n大的位置上，终实现完整的堆排序。5.8基数排序基数排序，又称为“桶子法”排序，属于一种分配式排序，排序思想也不同于之前介绍的几种排序，而是一种借助于多关键字排序思想进行排序的方法，其多关键字排序就是根据其不同的优先级来划分关键字。其中，在数字排序中，一般将排序数的个十百千位划分为其优先级的关键字，逐级根据其关键字依次从个位向高位划分，每次划分结束，将划分好的数据收集起来，再进行下一次的高位划分，直至后整个排序完成。为了达到更好的演示效果，我们使用复杂一点儿的数据来进行图示。首先用于图示的数组如下： 

var arr = ［132, 785, 064, 527, 308, 457, 002, 921, 233, 477］

我们将整个待排序数组分为10个桶，因为每一位数字为0~9，刚好10个，所以可以将数组按照某一逻辑划分到相应的桶中，这个逻辑就是从个位开始，将0~9作为关键字，按照个位数值来划分依次入列。
如图512所示，首先按照个位进行了一个简单的划分，数组的值都进入了相应的桶中，然后将这些数再收集起来，按照十位来再次划分，如图513所示。

图512数组按个位划分

图513数组再按十位划分

同理，将按照十位划分过后的数据收集起来，再次按照百位来进行划分，因为数的位数就是百位。如图514所示，因为已经循环到了位——百位，所以循环结束，此时再次将桶中的数据收集起来，你或许会惊奇地发现数组已经排好序了，也就是说基数排序已经完成了。

图514数组再按百位划分

下面先来看一下代码。

func radixSort(list: inout Array) {
var bucket = createBucket()
let maxNumber = listMaxItem(list: list)
let maxLength = numberLength(number: maxNumber)

for digit in 1…maxLength {
for item in list {
let baseNumber = fetchBaseNumber(number: item, digit: digit)
bucket［baseNumber］.append(item) 
}
print(“第＼(digit)轮入桶结果”)
print(“＼(bucket)”)

//出桶
var index = 0
for i in 0..while !bucket［i］.isEmpty {
list［index］ = bucket［i］.remove(at: 0)
index = 1
}
}
print(“第＼(digit)轮出桶结果”)
print(“＼(list)＼n”)
}
}

func createBucket() -> Array> {
var bucket: Array> = ［］
for _ in 0..<10 {
bucket.append(［］)
}
return bucket
}

func listMaxItem(list: Array) -> Int {
var maxNumber = list［0］
for item in list {
if maxNumber < item {
maxNumber = item
}
}
return maxNumber
}

func numberLength(number: Int) -> Int {
return “＼(number)”.characters.count
}

func fetchBaseNumber(number: Int, digit: Int) -> Int{
if digit > 0 && digit <= numberLength(number: number) {
var numbersArray: Array = ［］
for char in “＼(number)”.characters {
numbersArray.append(Int(“＼(char)”)!)
}
return numbersArray［numbersArray.count – digit］
}
return 0
}

可以看到，首先创建了10个空数组，表示10个桶结构，这个是后面所要用到的，接着找出数组中的数以及该数的位数来确定后面的循环次数。然后开始循环，digit从1到位数表示从个位开始到位。在每次的位循环中，按照我们根据当前是循环哪一位，来获取数组中每个数的该位的数字，并将这个数放到创建好的桶中，例如个数132，次个位循环时，判断个位是2，所以将132放入第二个桶中的数组中，以此类推。分配完毕后，桶中10个数组中的每个数组，有的可能含有值，有的可能为空数组。所以遍历循环桶结构，只要桶中某个数组还有值，就将其复写到原数组中，并将其remove。这样个位的一遍循环结束后，数组进行了一次分配收集，桶也实现了填充数据到提出数据，后又变为含有10个空数组。同理，再进行十位以及百位的循环。基数排序的时间复杂度为O(d(n radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集，是属于一种稳定的排序算法。小结本章介绍了著名的8大排序。其中，冒泡排序、选择排序、插入排序是简单的排序，快速排序、希尔排序、堆排序是比较高效率的排序，还有两种是体现分治思想的归并排序和基数排序。每种排序都有各自的特点，有的简单有效，有的利用空间换时间来达到高效排序，其实终的思想是大致相同的。读者可以根据实际需求来选择使用，所以说，没有好的排序，只有适合的排序。在实际的iOS开发中，或许很少会用到排序算法，所以大多数开发者对此也并没有深入了解，其实在涉及底层以及数据结构和算法时，就会使用得到，例如一些图片压缩算法。并且，以上介绍的几种算法也有比较优秀的设计思路，在实际开发中也用得到，例如分治递归。所以笔者将排序算法单独拿出来讲，可以作为了解，同时也希望读者可以在这些算法的精华中获取到更有用的编程思想以及理论知识，从而为以后打下良好的理论基础。