从哪开始？
如果你之前没有接触过算法和数据结构，你可以从下面这些简单易懂的算法开始看起：
栈
举个应用的栗子
栈类似于数组，但是限制了存取操作的灵活性。栈只允许使用者从栈顶压入(push)元素；从栈顶弹出(pop)元素；取得(peek)栈顶元素，但不弹出。
这样的限制有什么意义呢？在很多算法的实现中，你可能需要将某些对象放到一个临时的列表中，之后再将其取出。通常加入和取出元素的顺序非常重要。
栈可以保证元素存入和取出的顺序是后进先出(last-in first-out, LIFO)的。栈中弹出的元素总是你最后放进去的那个。另外一个非常类似的数据结构是队列，它是一个先进先出(first-in, first-out, FIFO)的结构。
举例来说，我们先将一个数字压入栈中：
stack.push(10)栈现在是 [10]。压入下一个数字：
stack.push(3)栈现在是 [10, 3]。再压入一个数字：
stack.push(57)栈现在是 [10, 3, 57]。现在把栈顶的数字弹出来：
stack.pop()这行代码返回 57，因为它是我们最后压入的元素。现在栈又变成了 [10, 3]。
stack.pop()这行代码返回 3，以此类推。如果栈空了，弹栈操作将返回 nil，在有些实现中，会触发一个 stack underflow 错误消息。
栈在 Swift 中的实现非常容易。只需要包装一下自带的数组，将存取功能限制为 pop、push 和 peek 即可。
public struct Stack<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
注意到，压栈操作是将新元素压入数组的尾部，而不是头部。在数组的头部插入元素是一个很耗时的操作，它的时间复杂度为 O(n)，因为需要将现有元素往后移位为新元素腾出空间。而在尾部插入元素的时间复杂度为 O(1)；无论数组有多少元素，这个操作所消耗的时间都是一个常量。
关于栈的有趣知识：每次你调用函数或方法，CPU 都会将函数返回地址压入到运行栈中。当这个函数执行结束的时候，CPU 将返回地址从栈中取出，并据此返回到函数被调用的位置。所以，如果不断地调用太多的函数(例如死递归函数)，就会得到一个所谓的“栈溢出(stack overflow)” 错误，因为 CPU 运行栈没有空间了。
队列
举个应用的栗子
队列的本质是一个数组，但只能从队尾添加元素，从队首移除元素。这保证了第一个入队的元素总是第一个出队。先到先得！
为什么要这样做呢？在很多算法的实现中，你可能需要将某些对象放到一个临时的列表中，之后再将其取出。通常加入和取出元素的顺序非常重要。
队列可以保证元素存入和取出的顺序是先进先出(first-in first-out, FIFO)的，第一个入队的元素总是第一个出队，公平合理！另外一个非常类似的数据结构是栈，它是一个后进先出(last-in, first-out, LIFO)的结构。
举例来说，我们将一个数字入队：
queue.enqueue(10)队列现在为 [ 10 ]。再将下一个数字入队：
queue.enqueue(3)队列现在为 [ 10, 3 ]。再加入一个数字：
queue.enqueue(57)队列现在为 [ 10, 3, 57 ]。现在我们将第一个元素出队：
queue.dequeue()这条语句返回数字 10，因为这是我们入队的第一个元素。队列现在是 [ 3, 57 ]。剩下的元素都往前移动一位。
queue.dequeue()这条语句返回 3，下次调用 dequeue 将返回 57，以此类推。如果队列为空，出队操作将返回 nil，在有些实现中，会触发一个错误信息。
注意：队列并不总是最好的选择，如果加入和删除元素的顺序无所谓的话，你可以选择使用栈来达到目的。栈更加简单快速。
实现代码
下面给出了一个简单粗暴的队列实现。它只是简单地包装了一下自带的数组，并提供了入队(enqueue)、出队(dequeue)和取得队首元素(peek)三个操作：
public struct Queue<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}上面实现的队列只是可以正常工作，但并没有任何的优化。
入队操作的时间复杂度为 O(1)，因为在数组的尾部添加元素只需要固定的时间，跟数组的大小无关。很好。
你可能会好奇为什么在数组尾部添加元素的时间复杂度为 O(1)，或者说只需要固定的时间。这是因为在 Swift 的内部实现中，数组的尾部总是有一些预设的空间可供使用。如果我们进行如下操作：
var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")则数组可能看起来想下面这样
[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]xxx 代表已经申请，但还没有使用的内存。在尾部添加一个新的元素就会用到下一块未被使用的内存：
[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]这只是简单的拷贝内存的工作，只需要固定的常量时间。
当然，数组尾部的未使用内存的大小是有限的，如果最后一块未使用内存也被占用的时候，再添加元素会使得数组重新调整大小来获取更多的空间。
重新调整的过程包括申请新的内存，将已有数据迁移到新内存中。这个操作的时间复杂度是 O(n)，所以是一个较慢的操作。但考虑到这种情况并不常见，所以，这个操作的时间复杂度依然是 O(1) 的，或者说是近似 O(1) 的。
但出队操作就有点不一样了。出队操作是将数组头部的元素移除，而不是尾部。这个操作的时间复杂度永远都是 O(n)，因为这会导致内存的移位操作。
在我们的例子中，将 "Ada" 出队会使得 "Steve" 接替 "Ada" 的位置；"Tim" 接替 "Steve" 的位置；"Grace" 接替 "Tim" 的位置：
出队前 [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
/ / /
/ / /
/ / /
/ / /
出队后 [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]
在内存中移动这些元素的时间复杂度永远都是 O(n)，所以我们实现的简单队列对于入队操作的效率是很高的，但对于出队操作的效率却较为低下。
更加高效的队列
为了让队列的出队操作更加高效，我们可以使用和入队所用的相同小技巧，保留一些额外的空间，只不过这次是在队首而不是队尾。这次我们需要手动编码实现这个想法，因为 Swift 内建数组并没有提供这种机制。
我们的想法如下：每当我们将一个元素出队，我们不再将剩下的元素向前移位（慢），而是将其标记为空（快）。在将 "Ada" 出队后，数组如下：
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]"Steve" 出队后，数组如下：
[ xxx, xxx, "Tim", "Grace", xxx, xxx ]这些在前端空出来的位子永远都不会再次使用，所以这是些被浪费的空间。解决方法是将剩下的元素往前移动来填补这些空位：
[ "Tim", "Grace", xxx, xxx, xxx, xxx ]这就需要移动内存，所以这是一个 O(n) 操作，但因为这个操作只是偶尔发生，所以出队操作平均时间复杂度为 O(1)
下面给出了改进版的队列的时间方式：
public struct Queue<T> {
fileprivate var array = [T?]()
fileprivate var head = 0
public var isEmpty: Bool {
return count == 0
}
public var count: Int {
return array.count - head
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
guard head < array.count, let element = array[head] else { return nil }
array[head] = nil
head += 1
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
return element
}
public var front: T? {
if isEmpty {
return nil
} else {
return array[head]
}
}
}现在数组存储的元素类型是 T?，而不是先前的 T，因为我们需要某种方式来将数组的元素标记为空。head 变量用于存储队首元素的下标值。
绝大多数的改进都是针对 dequeue() 函数，在将队首元素出队时，我们首先将 array[head] 设置为 nil 来将这个元素从数组中移除。然后将 head 的值加一，使得下一个元素变成新的队首。
数组从这样：
[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
head变成这样：
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
head这就像在某个外星球的奇怪超市，在那里排队结账的人保持不动，而收银员往队尾移动来挨个结账。
当然，如果我们从不移除队首的空位，随着不断地入队和出队，队列所占空间将不断增长。为了周期性地清理无用空间，我们编写了如下代码：
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}这段代码计算了队首空余的元素占数组总元素的百分比，如果空余元素超过 25%，我们就进行一波清理。但是，如果队列的长度过小，我们也不想频繁地清理空间，所以在清理空间之前，队列中至少要有 50 个元素。
注意：这个 50 只是我凭空捏造的一个数字，在实际的项目中，你应该根据项目本身来选定一个合情合理的值。
如果想在 Playground 中测试，可以参考下面的代码：
var q = Queue<String>()
q.array // [] empty array
q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count // 3
q.dequeue() // "Ada"
q.array // [nil, {Some "Steve"}, {Some "Tim"}]
q.count // 2
q.dequeue() // "Steve"
q.array // [nil, nil, {Some "Tim"}]
q.count // 1
q.enqueue("Grace")
q.array // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count // 2为了测试队列的自动调整特性，将下面这段代码：
if array.count > 50 && percentage > 0.25 {替换为：
if head > 2 {现在，如果你再次执行出队操作，数组将看起来像下面这样：
q.dequeue() // "Tim"
q.array // [{Some "Grace"}]
q.count // 1在数组前面的 nil 已经被移除了，数组本身也没有空间浪费了。新版本的队列实现并没有比初版复杂很多，但现在出队操作的复杂度已经从当初的 O(n) 变为了现在的 O(1)，只是因为我们在数组的使用策略上耍了一点小心机。
扩展阅读
事实上，队列还有很多种其他的实现方式，例如可以使用[链表](../Linked List/)、[环形缓冲区](../Ring Buffer/)或是堆来实现。
队列有很多变体，包括双端队列，一个两端都可以出队和入队的队列；[优先队列](../Priority Queue/)，一个有序的队列，最重要的元素排在队首。
插入排序
目标：将一个数组按照从低到高（或从高到低）来排序。
现有一个数字类型的数组需要进行排序，插入排序的工作方式如下：
首先，将这些待排序的数字放在一个数组中，成为未排序的原始数组。
从其中取出一个数字，具体取哪个无所谓。为简单起见，每次都直接取出第一个元素。
将这个数字插入到一个新的已排序数组中。
然后再次从未排序数组中取出一个数字，将其插入到已排序数组中。它要么插在第一个元素的前面，要么插在后面，来保证这两个数字是有序的。
再一次从未排序数组中取出一个元素，安插在新数组的合适位置，以求新数组依然有序。
一直这样做下去，直到未排序数组中没有数字了为止。这样就可以达到排序的目的了。
这就是算法叫“插入”排序的原因，因为排序过程中不断地从未排序数组中取出元素插入到已排序的目标数组。
译者注：类似于打牌的时候抓牌的过程！
举例
例如，待排序的数组为 [ 8, 3, 5, 4, 6 ]。
取出第一个数字 8，将它插入到已排序数组中。已排序数组目前还是空的，所以这个过程非常简单。已排序数组现在为 [ 8 ]，未排序数组为 [ 3, 5, 4, 6 ]。
取出下一个数字 3，将其插入到已排序数组。他应该在 8 的前面，所以已排序数组现在为 [ 3, 8 ]，未排序数组缩减为 [ 5, 4, 6 ]
取出下一个数字 5，将其插入到已排序数组中。它应该在 3 和 8 之间。所以，现在已排序数组为 [ 3, 5, 8],未排序数组为 [ 4, 6 ]。
重复以上过程，直到未排序数组为空为止。
原地排序
根据上面的解释，排序过程中似乎使用了两个数组，一个用于存放未排序的的元素，另一个存放已排序的元素。
但实际上插入排序可以“原地”进行，无需再创建另一个数组。只需要标记好哪部分是未排序的，哪部分是已排序的即可。
初始数组为 [ 8, 3, 5, 4, 6 ]。我们使用 | 符号来分隔已排序和未排序部分：
[| 8, 3, 5, 4, 6 ]上图显示已排序部分为空，未排序部分的第一个数字为 8。
处理完第一个数字之后，数组如下所示：
[ 8 | 3, 5, 4, 6 ]目前，已排序的部分为 [ 8 ]，未排序的部分为 [ 3, 5, 4, 6 ]。分隔符 | 向右位移了一个单位。
下面列出了排序过程中数组内容的变化：
[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]每一步分隔符 | 都向右位移一个单位。可以观察到，数组开头到分隔符之间的部分总是已排序的。未排序部分每减少一个元素，已排序部分就增加一个，直到未排序元素为空为止。
如何插入
每个周期开始，取出未排序数组的头部元素，将其插入到已排序数组中。这时候，必须要保证元素被插入到了正确的位置。怎么做呢？
现在假设已经完成了前面几个元素的排序，数组看起来像下面这样：
[ 3, 5, 8 | 4, 6 ]下一个待排序的数字是 4。我们要做的就是将其插入到已排序数组 [ 3, 5, 8 ] 的某个位置。
下面提供了一个实现思路：跟前面的元素 8 进行比较。
[ 3, 5, 8, 4 | 6 ]
^
它比 4 大吗？是的，所以 4 应该放到 8 的前面去。我们将两个数字交换位置来达到目的：
[ 3, 5, 4, 8 | 6 ]
<-->
已交换至此还没有结束。交换之后，新的排在前面的元素 5 也比 4 大。我们如法炮制，也将这两个数字交换位置：
[ 3, 4, 5, 8 | 6 ]
<-->
已交换继续，再次检查排在前面的新元素 3，它比 4 大吗？不，它必 4 小，这就意味着 4 已经在正确的位置上了。已排序的数组也再次变得有序了。
这就是插入排序算法的内循环的文字描述了，具体的代码在下一节给出。通过交换数字的方式，我们将待排序的元素移动到了已排序数组的正确位置上
代码
下面是Swift实现的插入排序：
func insertionSort(_ array: [Int]) -> [Int] {
var sortedArray = array // 1
for index in 1..<sortedArray.count { // 2
var currentIndex = index
while currentIndex > 0 && sortedArray[currentIndex] < sortedArray[currentIndex - 1] { // 3
sortedArray.swapAt(currentIndex - 1, currentIndex)
currentIndex -= 1
}
}
return sortedArray
}
把下面代码放入Playground中玩一下:
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)下面介绍代码是如何工作的。
由于参数
array无法直接修改，我们需要先复制一下数组，类似 Swift 自己sort()函数，insertionSort()会返回的排序后的新数组。这个函数中有两层循环。外层循环数组中的每一个元素，就是从|数组中取最顶层的，x变量是排序部分最后位置和管道符开始的位置（
|的位置），请记住在任何时候，数组开始部分从0至x是已经排好的，从x到最后是没有排序的部分。内层循环获取
x位置的数字，就是未排序数组的头部，它可能比之前的数字都笑，内层循环会反向遍历已经排序的数字，每次比较发现之前排序中的数字较大后就交换一下位置，当内层循环结束后，数组头部就完成一次排序，已经排序的部分增加一个数字。
注意 外层循环不是从0开始而是从1开始。把开始位置的数字移动到已排序区没有什么意义，因此我们直接跳过。
不用 swap
之前版本插入排序已经工作的很好了，但是可以通过省略 swap() 变的更快一些
可以看到我们通过交换数字位置把下一个数字插入排序区：
[ 3, 5, 8, 4 | 6 ]
<-->
swap
[ 3, 5, 4, 8 | 6 ]
<-->
swap
不用通过位置交换的方法实现，我们可以把所有的元素右移一个位置，然后把新数字复制到正确的位置。
[ 3, 5, 8, 4 | 6 ] 保存 4
*
[ 3, 5, 8, 8 | 6 ] 向右挪动 8
--->
[ 3, 5, 5, 8 | 6 ] 向右挪动 5
--->
[ 3, 4, 5, 8 | 6 ] 复制 4 到正确的位置
*代码如下:
func insertionSort(_ array: [Int]) -> [Int] {
var sortedArray = array
for index in 1..<sortedArray.count {
var currentIndex = index
let temp = sortedArray[currentIndex]
while currentIndex > 0 && temp < sortedArray[currentIndex - 1] {
sortedArray[currentIndex] = sortedArray[currentIndex - 1] // 1
currentIndex -= 1
}
sortedArray[currentIndex] = temp // 2
}
return sortedArray
}//1一行把之前的数字移动一位。在内层循环结束后， y 是新数字的下标的位置， //2 这行复制新数字到这个位置。
更普遍适用
如果可以排序其他类型比仅仅排序数字更加吸引人。我们可以创建一个数据泛型，并使用自定义的比较函数或者匿名函数。只需要修改两处就可以了。
函数定义如下:
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {这个数组类型为 [T] , T 是泛型模板。现在 insertionSort() 可以接受任意的类型数组， 无论是数字，字符或者什么。。
这个新参数 isOrderedBefore: (T, T) -> Bool 是一个函数，函数定义为比较两个 T 类型的对象并返回比较结果， 如果第一个对象比第二个对象在前，返回 true, 否则返回 false。 Swift 内置的 sort() 函数也正是如此。
只需要改变内层循环，修改如下：
while y > 0 && isOrderedBefore(temp, a[y - 1]) {通过 isOrderedBefore () 代替 `temp < a[y - 1] , 功能不变，但是我们现在可以比较任意类型对象，不只是数字。
在 playground 玩一下看看:
let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)< 和 > 定义排序的顺序，分别是从低到高和从高到底。
当然你也能对其他类型排序如字符串。
let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)或者其他复杂对象:
let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }这个匿名函数告诉 insertionSort() 需要排序的对象的优先级。
插入排序是一个稳定排序算法。稳定是指当元素有相同的关键值的情况下在排序后仍然保持相对位置。对于简单的数字或者字符并不重要，但是当排序复杂的对象时是非常重要的。在上面的例子里，如果两个对象有相同的 priority, 忽略他们其他的属性，这两个对象不会交换位置。
性能
插入排序在数组已经排序好的情况下非常快。听起来有些荒唐，但是不是所有的搜索算法都是能这样。 实际情况下，对于非常大的数据集的一部分进行排序，插入排序还是很不错的。
最坏和平均排序的时间复杂度为 O(n^2) 。这是因为有两层循环，其他的算法如快速排序和归并排序为 O(n log n) ，在数据集很大时也很快。
插入排序在很小的数组时排序很快。一些标准库在排序区小于等于10的时候把快速排序换成插入排序。
我做了简单比较了insertionSort() 和 Swift 内置的 sort() 。在100个左右的数据的数组时，二者差距非常小，但是当你输入变得更大时，O(n^2) 很快比 O(n log n) 性能差很多，插入排序已经跟不上班了。。
其他
二分查找
目标：在数组中快速找到目标
比如，你想知道数组中有没有这个数字，如果存在，它的下标值是多少。
在大多数情况下，我们可以使用 Swift 的 indexOf() 函数：
let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]
numbers.index(of: 43) // returns 15SWift 自带的 indexOf() 函数用的是线性查找. 代码如下：
func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
for i in 0 ..< a.count {
if a[i] == key {
return i
}
}
return nil
}调用一下看看:
linearSearch(numbers, 43) // returns 15那么问题来了， linearSearch() 从数组头开始遍历直到它找到你要的数字。在最坏的情况下，这个值可能不在数组里，以上的工作都没有意义。
平均情况下，线性搜索算法需要遍历一半的数组，当数组非常大时这个算法会变的非常慢。
分而治之
一般的方式是通过 二分查找 来加快速度。做法是持续不断的把一个数组分成两部分直到这个值被找到。
n个元素的数组使用二分查找的时间复杂度是 O(log n) 而不是 O(n)。 那么差距到底是多少呢？ 二分查找一个 1,000,000 大的数组只需要 20 步，因为 log_2(1,000,000) = 19.9 。 查找一个十亿大数组也只需要 30 步。（想一下你最后一次用数组是十亿大的吗？）
嗯听起来不错，但是使用二分查找有一个前提，那就是数组必须排序。实际上这也不是个问题。
二分查找到底是如何工作的呢？
把数组分成两半，根据查找对象的 搜索值 查看是在左半部分还是右半部分。
如何决定搜索值是在那边？ 这就是为什么要先进行数组排序，这样才能做一个简单的比较。
如果搜索值是在左半部分，继续重复操作，把左边再分成两小块，在查看搜索值是在哪边。（在右边也是一样的）
一直重复直到搜索值找到，如果数组最后无法再继续分割，那么只能遗憾的告诉你没有找到搜索值。
Now you know why it's called a "binary" search: in every step it splits the array into two halves. This process of divide-and-conquer is what allows it to quickly narrow down where the search key must be.
现在你知道为什么叫 二分 查找了吧。每步需要把数组分成两半。分而治之 的过程就是快速缩小搜索值的范围。
代码实现
下面是一个递归版的二分查找：
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// If we get here, then the search key is not present in the array.
return nil
} else {
// Calculate where to split the array.
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
// Is the search key in the left half?
if a[midIndex] > key {
return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
// Is the search key in the right half?
} else if a[midIndex] < key {
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
// If we get here, then we've found the search key!
} else {
return midIndex
}
}
}复制代码到Playground中玩一下看看：
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43, range: 0 ..< numbers.count) // gives 13注意 数字 数组是排序过，否则二分查找将无法适用。
本文谈到二分查找需要把数组分成两半，但是我们并不需要创建两个数组，使用 Swift 的 Range 对象来实现跟踪分组，最开始 range 对象涵盖全部数组，用 0 ..< numbers.count 表示， 随着数组二分查找， range 对象变的越来越小。
注意：range.upperBound总是指向数组最后一位下标+1的值，比如当 range 为0..<19时，因为共有19位数字在数组中，所以range.lowerBound = 0，range.upperBound = 19。但是在上面的数组中最后一位的下标是18，并不是19，因为是从0开始的。所以请记住当使用range的时候，upperBound最是比最后一个元素的下标大1。
一步一步的来看看
非常有用对观察一个算法具体如何是工作的。
上面例子是中包含 19 个数字，当拍完序后如下：
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]我们需要在本数组中查找 43。
为了拆分数组，我们需要知道中间值的下标，由下面的代码实现：
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2最开始，range 的 lowerBound = 0 , upperBound = 19。 midIndex 为 `0 + (19 - 0)/2 = 19/2 = 9 ，实际结果是 9.5, 但是因为用的整数型，所以结果需要向下舍入。
在下图中 * 代表中间值，如图所示，这个值到两边是相同的个数，因此从这里分成两个值。
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*现在二分查找需要决定使用那一半数组，相关代码如下：
if a[midIndex] > key {
// use left half
} else if a[midIndex] < key {
// use right half
} else {
return midIndex
}本例中， `a[midIndex] = 29 , 比搜索值小，因此我们可以得出结论，搜索值永远不会再左半部分出现。因为左边所有的值都比 29 小。因此搜索值肯定是在右边部分(也可能不在数组中)。
现在我们可以简单的重复二分查找，从 midIndex + 1 到 range.upperBound :
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
由于不用担心数组的左半部分，我把他们全部标记为 x, 现在我们只需要查看右边部分，从下标 10 开始。
We calculate the index of the new middle element: midIndex = 10 + (19 - 10)/2 = 14, and split the array down the middle again.
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*显而易见， a[14] 是右边数组的中间值。
搜索值是比 a[14] 大还是小呢？ 因为 43 < 47, 这次我们需要查看左半部分并忽略右边部分的大的值:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]新的 midIndex在这里:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
*搜索值比 37 大，继续从右边查找：
[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
*搜索值比较大，再拆分一次并使用右边的部分：
[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
*现在结束。搜索值正是我们正在寻找的，因此我们最后找到了 43 值，在 13 的位置。w00t! 耶！
看起来需要很多步，但是实际找到目标值只需要 4 步，因为 log_2(19) = 4.23 。如果用线性搜索需要 14 步。
如果我们搜索 42 会怎样呢？ 当搜索进行到无法分割数组时，range.upperBound 变的比 range.lowerBound 小，这也反映出目标值不在数组中。
注意 在许多二分查找的实现需要计算midIndex = (lowerBound + upperBound) / 2。 在处理超大数据的时候这里可能会有个小问题， 因为lowerBound + upperBound可能会超出整数范围导致溢出。在 64 位机器上可能不会有问题，但是在 32 位机器上需要注意。
循环 vs 递归
二分查找使用递归很容易理解，因为是按照人的逻辑一步一步的分成更小的子数组。但是这并不是只有递归才能实现 binarySearch() , 使用循环实现速度会更好。
下面是用Swift循环实现的二分查找：
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
var upperBound = a.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
return midIndex
} else if a[midIndex] < key {
lowerBound = midIndex + 1
} else {
upperBound = midIndex
}
}
return nil
}你可以看到代码与递归的写法非常相似，最大的不同是使用的 while 循环。
测试一下:
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43) // gives 13最后
数组必须排序后才能查找是不是个问题呢？视情况而定，需要注意的是排序也是需要时间的，加上二分查找的时间可能比线性搜索还要慢。二分查找的优点是只需要一次排序就可以做很多次查找。
更多信息查看 Wikipedia.
二叉搜索树(BST)
这里有个例子
二叉搜索树是一种特殊的 二叉树 (该树每个父节点最多有两个子节点)，在插入和删除后总是保持顺序。
想了解关于树的知识？请先看这里.
“排序”树
这里有一个二叉搜索树的图:
可以看到左边子节点总是比它的父节点小，而右边子节点总是比它的父节点大。这是二叉搜索树的关键特点。
如 2 比 7 小，因此它在左边，而 5 比 2 大，因此它在右边
插入一个新节点
插入新节点时，先与根节点比较，如果较小则走 左 分支，如果较大则走 右 分支。继续如此比较操作，直到我们找到一个空节点可以插入。
比如我们需要插入一个新值 9：
从根节点开始（根节点是
7）与新值9做比较，9 > 7，向右分支下移，这次遇到的节点是10因为
9 < 10， 向左下分支移动现在没有值可以进行比较，把
9插入这里
下面是插入 9 后的树：
对于新元素只有一个位置可以插入，查找该位置非常快，需要 O(h) 时间， h 为树的高度
注意： 节点 高度 是从此节点到叶子节点的步数。树的总高度是根节点到最低叶子节点的距离。许多二叉搜索树的操作是跟树个高度有关的。
通过遵循这个简单规则 -- 小值在左边，大值在右边。我们可以保持树的顺序，所以无论什么时候我们都可以查询这个值是否在树上。
树的查找
为了查找一个值是否在树中，我们采用以下的步骤：
如果值小于当前值，取左边树
如果值大于当前值，取右边树
如果当前值等于当前节点值，就找到了！
就像大部分对树的操作，查找也是不断的递归直到找到节点或者查找结束。
下面是搜索 5 的例子：
树的搜索是很快的，是 O(h) 时间复杂度。如果是一个平衡很好的树,即使有百万的节点，也不过需要 20 步就能结束查找(和二分搜索的思想很像)。
树的遍历
有时你需要遍历所有的节点，不仅仅只查找单个节点。
共有三种方式来遍历二叉树：
中序遍历（或者 深度优先）：先访问左子树，然后访问节点本身，最后访问右子树。
前序遍历：先访问节点本身，然后访问左子树，最后访问右子树。
后序遍历：先访问左子树，然后右子树，最后节点本身。
遍历树也会用到递归。
如果你中序遍历一个二叉搜索树，遍历的结果就像从小到大排列一样。上述例子中的树遍历结果为 1, 2, 5, 7, 9, 10 :
删除节点
删除节点很简单，删除节点后，把当前的节点替换为它的左子树最大的节点或者右子树最小节点。这样树在删除后还会保持原来的顺序。在下述例子中， 10 被移除， 图2 为用 9 代替， 图3 为用 11 代替。
替换节点只会在该节点有子节点的时候才会做，如果没有子节点，你可以直接从它的父节点中移除：
代码 (方法1)
理论介绍到此为止。来看看怎么实现吧，可以使用不同的方式实现， 首先我们先试试建一个基于类的版本，随后我们再用枚举来实现。
这是一个 二叉搜索树 的类：
public class BinarySearchTree<T: Comparable> {
private(set) public var value: T
private(set) public var parent: BinarySearchTree?
private(set) public var left: BinarySearchTree?
private(set) public var right: BinarySearchTree?
public init(value: T) {
self.value = value
}
public var isRoot: Bool {
return parent == nil
}
public var isLeaf: Bool {
return left == nil && right == nil
}
public var isLeftChild: Bool {
return parent?.left === self
}
public var isRightChild: Bool {
return parent?.right === self
}
public var hasLeftChild: Bool {
return left != nil
}
public var hasRightChild: Bool {
return right != nil
}
public var hasAnyChild: Bool {
return hasLeftChild || hasRightChild
}
public var hasBothChildren: Bool {
return hasLeftChild && hasRightChild
}
public var count: Int {
return (left?.count ?? 0) + 1 + (right?.count ?? 0)
}
}
这是一个单节点，它使用了泛型可以存储任意类型数据，它引用了一个 left 和 right 子节点以及 parent 父节点。
来试试：
let tree = BinarySearchTree<Int>(value: 7)count 是指树上有多少个节点。它不仅仅统计直接连接的子节点，还包含了它的子节点以及子节点的全部后代。如果它是根节点，那么计算的是整个树。初始值为 0。
注意： 因为left，right和parent是可选值，我们正好可以使用 Swift 的可选链 (?) 以及可选值联合运算符 (??)。 也可以使用if let的方法，但是这样代码更简练。
插入
只有一个的树节点没什么意义，让我们插入一些新的节点：
public func insert(value: T) {
if value < self.value {
if let left = left {
left.insert(value: value)
} else {
left = BinarySearchTree(value: value)
left?.parent = self
}
} else {
if let right = right {
right.insert(value: value)
} else {
right = BinarySearchTree(value: value)
right?.parent = self
}
}
}类似树的其他操作，插入操作也是递归实现的。我们比较新值与已有节点来决定是放在左子树还是右子树。
如果没有左或右子树在比较了，创建一个 BinarySearchTree 对象并和 parent 建立连接。
注意： 因为整个二叉搜索树必须保持左边是小值，右边是大值的顺序，因此插入一个新元素后必须还是一个正确的二叉树。
插入一些节点吧：
let tree = BinarySearchTree<Int>(value: 7)
tree.insert(2)
tree.insert(5)
tree.insert(10)
tree.insert(9)
tree.insert(1)注意： 为了后面讲的更清楚，需要随机插入数字，如果排序后再插入它们，树的形状可能会不正确。
创建一个支持数组插入的快捷方法 insert() ：
public convenience init(array: [T]) {
precondition(array.count > 0)
self.init(value: array.first!)
for v in array.dropFirst() {
insert(value: v)
}
}现在简单了：
let tree = BinarySearchTree<Int>(array: [7, 2, 5, 10, 9, 1])数组中的第一个元素是树的根节点。
Debug输出
在处理一些复杂的数据结构的时候，使用一些可读的 debug 输出非常有用。
extension BinarySearchTree: CustomStringConvertible {
public var description: String {
var s = ""
if let left = left {
s += "(\(left.description)) <- "
}
s += "\(value)"
if let right = right {
s += " -> (\(right.description))"
}
return s
}
}
使用 print(tree) 打印如下：
((1) <- 2 -> (5)) <- 7 -> ((9) <- 10)
根节点在中间，想象一下可以看出其实是一颗这样的树：
你可能好奇如果输入一个重复数据会怎样？答案是总是插在右子树上。试试看！
查找
现在我们树上有一些值了，做什么好呢？当然是做查找啦！查找快速是使用二叉搜索树的主要目的。 :-)
这是 search() 的实现：
public func search(value: T) -> BinarySearchTree? {
if value < self.value {
return left?.search(value)
} else if value > self.value {
return right?.search(value)
} else {
return self // found it!
}
}逻辑非常明确：从当前节点开始（一般是从根节点开始）比较。如果目标值比当前节点小，继续从左子树查找，如果比当前节点值大，从右子树开始查找。
如果 left 或 right 为 nil，返回 nil 表示没有查到。
注意 在 Swift 中，使用可选链非常方便。left?.search(value)中left为 nil 的时候会自动返回 nil, 不需要明确的检查。
查找是一个递归的过程，也可以用一个简单的循环代替：
public func search(value: T) -> BinarySearchTree? {
var node: BinarySearchTree? = self
while let n = node {
if value < n.value {
node = n.left
} else if value > n.value {
node = n.right
} else {
return node
}
}
return nil
}
这两种实现是等价的。就个人而言，我更倾向使用循环的方式，人各有志，没关系。 ;-)
测试代码如下:
tree.search(5)
tree.search(2)
tree.search(7)
tree.search(6) // nil前三行返回相应的 BinaryTreeNode 对象，最后一行返回 nil, 因为没有 6 这个节点。
注意： 如果树中含有重复值， search() 函数会返回最高的节点，这也很合理，因为是从根节点开始查找的。遍历
还记得遍历树的三种方式吗？ 下面就是其实现。
public func traverseInOrder(process: (T) -> Void) {
left?.traverseInOrder(process: process)
process(value)
right?.traverseInOrder(process: process)
}
public func traversePreOrder(process: (T) -> Void) {
process(value)
left?.traversePreOrder(process: process)
right?.traversePreOrder(process: process)
}
public func traversePostOrder(process: (T) -> Void) {
left?.traversePostOrder(process: process)
right?.traversePostOrder(process: process)
process(value)
}
他们功能一模一样，但是输出顺序截然不同。所有的遍历是通过递归实现的。 Swift 的可选链使调用 traverseInOrder () 等函数可以忽略是否有没有左右子树。
从低到高输出树的所有值：
tree.traverseInOrder { value in print(value) }This prints the following:
1
2
5
7
9
10你也可以添加 map() 和 filter() 方法。下面是 map 的实现：
public func map(formula: (T) -> T) -> [T] {
var a = [T]()
if let left = left { a += left.map(formula: formula) }
a.append(formula(value))
if let right = right { a += right.map(formula: formula) }
return a
}
每个树上的节点调用 formula 后的结果存入数组中。 map() 是与中序遍历一起完成的。
下面是 map() 一个简单的使用例子：
public func toArray() -> [T] {
return map { $0 }
}这个函数可以把树的存值变成一个排序后的数组，在 playground 中试一下：
tree.toArray() // [1, 2, 5, 7, 9, 10]作为练习，你来实现 filter 和 reduce 吧。
删除
先定义一些帮助函数，让代码更加易读：
private func reconnectParentTo(node: BinarySearchTree?) {
if let parent = parent {
if isLeftChild {
parent.left = node
} else {
parent.right = node
}
}
node?.parent = parent
}这个函数的作用是批量修改树的 parent, left 和 right 指针。可以把当前节点（self）的父节点重新连接另一个子节点。
我们还需要一个函数返回节点的最小值和最大值：
public func minimum() -> BinarySearchTree {
var node = self
while let next = node.left {
node = next
}
return node
}
public func maximum() -> BinarySearchTree {
var node = self
while let next = node.right {
node = next
}
return node
}
剩余代码如下：
@discardableResult public func remove() -> BinarySearchTree? {
let replacement: BinarySearchTree?
//当前节点的代替者要么是左边的最大值，要么是右边的最小值，哪一个都不会为nil
if let right = right {
replacement = right.minimum()
} else if let left = left {
replacement = left.maximum()
} else {
replacement = nil
}
replacement?.remove()
// 把要代替的节点移到当前节点位置
replacement?.right = right
replacement?.left = left
right?.parent = replacement
left?.parent = replacement
reconnectParentTo(node:replacement)
//当前节点不再是树的一部分，因此可以清理删除了
parent = nil
left = nil
right = nil
return replacement
}深度和高度
某一节点的高度是它到最低叶子节点的距离。我们可以如下计算：
public func height() -> Int {
if isLeaf {
return 0
} else {
return 1 + max(left?.height() ?? 0, right?.height() ?? 0)
}
}取左右子树的高度作为该节点的高度。递归再一次解决了这个问题。 由于需要查看所有字节，时间复杂度为 O(n) 。
注意： Swift的可选值联合运算符可以减少left和right的判空处理，你也可以用if let，但是这样代码更简练。
测试:
tree.height() // 2节点 深度 是指到根节点的距离，代码如下：
public func depth() -> Int {
var node = self
var edges = 0
while let parent = node.parent {
node = parent
edges += 1
}
return edges
}
通过 parent 指针一步一步向上遍历树，直到找到根节点（ 根节点的 parent 值为空）。时间复杂度为 O(h) ：
if let node9 = tree.search(9) {
node9.depth() // returns 2
}前驱和后继
二叉搜索树总是 排序 的，但是这不意味着树中连续的数字是相邻的。
只看 7 的左子树是无法找到它的前驱的，因为左子树是 2, 正确的前驱是 5。 后驱也是类似。
predecessor() 函数返回当前节点的前驱
public func predecessor() -> BinarySearchTree<T>? {
if let left = left {
return left.maximum()
} else {
var node = self
while let parent = node.parent {
if parent.value < value { return parent }
node = parent
}
return nil
}
}有左子树的情况下，前驱就是左子树的最大值。（因为左子树均小于当前节点值，那么左子树最大的值就是最靠近节点的值，译者注）从上图中可以看到 5 是 7 左子树中最大的值。
如果没有左子树，只能一直遍历父节点直到找到比自己小的值。(右子树都不比自己大，左子树没有，最多可能在父节点中，译者注)。想知道 9 的前驱是谁吗？通过这样的方法找到的是 7。
后继 工作方式类似，做个左右对称替换就好了：
public func successor() -> BinarySearchTree<T>? {
if let right = right {
return right.minimum()
} else {
var node = self
while let parent = node.parent {
if parent.value > value { return parent }
node = parent
}
return nil
}
}这两个方法的时间复杂度为 O(h)
注意： 线索二叉树 变通了一下，把 无用 的左右指针重新设计用来直接指向前驱和后继节点。非常有想法！树是否合法呢？
有一些做法可以破坏树的结构，在非根节点上调用 insert() 方式可能会破坏树的结构。如：
if let node1 = tree.search(1) {
node1.insert(100)
}根节点是 7, 因此 100 肯定是在右子树上。但是不在根节点上操作而是在一个叶子树上插入新节点， 因此 100 被插入了错误的位置。
导致的问题就是 tree.search(100) 返回 nil。
你可以通过如下方法来判断二叉搜索树是否合法：
public func isBST(minValue: T, maxValue: T) -> Bool {
if value < minValue || value > maxValue { return false }
let leftBST = left?.isBST(minValue: minValue, maxValue: value) ?? true
let rightBST = right?.isBST(minValue: value, maxValue: maxValue) ?? true
return leftBST && rightBST
}验证方法是左子树值包含的值只会小于当前值，右子树包含色值只会大于当前值。
调用如下:
if let node1 = tree.search(1) {
tree.isBST(minValue: Int.min, maxValue: Int.max) // true
node1.insert(100) // EVIL!!!
tree.search(100) // nil
tree.isBST(minValue: Int.min, maxValue: Int.max) // false
}代码（方案2）
我们先用类实现了一次，也可以用枚举来实现。
关键的区别就是引用类型和值类型。基于类实现的树更新时是内存的同一个实例，而枚举实现的树是不可改变的，每次插入或者删除操作后会给你一个全新的一个树的拷贝，哪一种更好呢？ 这完全取决于你要做什么。
这是我们用枚举实现的二叉搜索树：
public enum BinarySearchTree<T: Comparable> {
case Empty
case Leaf(T)
indirect case Node(BinarySearchTree, T, BinarySearchTree)
}枚举有三种：
Empty
表示分支结束（类实现的用nil） -Leaf是一个叶子节点没有子节点 -Node是一个节点含有一个或者两个子节点。 用indirect修饰，这样它就能包含BinarySearchTree的值。没有indirect` 无法使用枚举递归。
注意： 二叉树的节点并没有引用它们的父节点。这倒不是大问题，可以用特定的方式来实现。
用递归实现，不同枚举有不同的结果。如下，这是一个实现计算节点数量和高度的代码
public var count: Int {
switch self {
case .Empty: return 0
case .Leaf: return 1
case let .Node(left, _, right): return left.count + 1 + right.count
}
}
public var height: Int {
switch self {
case .Empty: return -1
case .Leaf: return 0
case let .Node(left, _, right): return 1 + max(left.height, right.height)
}
}插入新节点如下：
public func insert(newValue: T) -> BinarySearchTree {
switch self {
case .Empty:
return .Leaf(newValue)
case .Leaf(let value):
if newValue < value {
return .Node(.Leaf(newValue), value, .Empty)
} else {
return .Node(.Empty, value, .Leaf(newValue))
}
case .Node(let left, let value, let right):
if newValue < value {
return .Node(left.insert(newValue), value, right)
} else {
return .Node(left, value, right.insert(newValue))
}
}
}在 playground 调用:
var tree = BinarySearchTree.Leaf(7)
tree = tree.insert(2)
tree = tree.insert(5)
tree = tree.insert(10)
tree = tree.insert(9)
tree = tree.insert(1)注意，每次插入后会得到一个新的树对象。因此需要把新结果赋值给 tree
下面是树最重要的功能-查找：
public func search(x: T) -> BinarySearchTree? {
switch self {
case .Empty:
return nil
case .Leaf(let y):
return (x == y) ? self : nil
case let .Node(left, y, right):
if x < y {
return left.search(x)
} else if y < x {
return right.search(x)
} else {
return self
}
}
}大多数的函数有相同的代码结构。
调用:
tree.search(10)
tree.search(1)
tree.search(11) // nil使用如下的方法做 Debug
extension BinarySearchTree: CustomDebugStringConvertible {
public var debugDescription: String {
switch self {
case .Empty: return "."
case .Leaf(let value): return "\(value)"
case .Node(let left, let value, let right):
return "(\(left.debugDescription) <- \(value) -> \(right.debugDescription))"
}
}
}打印如下：
((1 <- 2 -> 5) <- 7 -> (9 <- 10 -> .))根节点在中点，点 代表是没有子节点。
树如果不平衡了..
平衡 二叉搜索树左右子树有相同的节点。在这种情况下是理想状态，树的高度是 log(n)， n 为节点的个数。
当一个分支明显的比其他长时查找会变的很慢。在最坏的情况下，树的高度变成 n， 这样不再是二叉搜索树，更像是 链表。时间复杂度变成 O(n)， 性能会差很多，非常糟糕。
一种方法是随机插入使得二叉搜索树保持平衡。一般情况下应该能保持树的平衡，但是这样无法保证，实际也确实如此。
另一种方式是使用 自平衡 的二叉搜索树。这种数据结构能在插入或删除后调整树的平衡。如 AVL树 和 红黑树。
更多
Binary Search Tree on Wikipedia
归并排序
举个例子
目标：从小大排列数组（或者反过来）
该算法是 John von Neumann 在1945年提出的，归并排序是一个高效的算法，最好，最坏，期望时间复杂度均为 O(n log n) 。
归并排序使用 分治 的思想把一个大问题分成一个一个小问题，然后在分别解决。归并算法的就是 先分解 后 合并 处理。
排列 n 个数的数字使用归并排序步骤如下：
把数字存入未排序的序列
把序列一分为二，得到两个未排序的序列
一直分割下去，直到无法再分割。最后得到一个 n 个序列，每个序列只有一个数字
按顺序比较合并，每次合并后时进行排序。这时候操作非常简单因为每一个序列已经排序过了。
例子
分割
假设数组为 [2, 1, 5, 4, 9]，显然是乱序的，目标是一直分割下去直到无法分割。
首先，把数组分割成两半：[2, 1] 和 [5, 4, 9]。现在还能分割吗？当然可以啦！
焦点放在左半部分上，将 [2, 1] 分割为 2 和 [1] 。能继续再分割吗？不能，少年你该去查看其它序列了。
把 [5, 4, 9] 分割成 [5] 和 [4, 9] 。[5] 不能再分割了， 但是 [4, 9] 可以继续分割为 [4] 和 [9] 。
分割结束后为 [2] [1] [5] [4] [9] 。注意每一个序列只包含一个元素。
合并
现在数组已经分割完了，下一步开始边 排序 边 合并。记住这种思想只能解决很多小问题，但是无法解决大问题。每次合并迭代时，需要考虑两个序列的合并。
数组为 [2] [1] [5] [4] [9]，第一合并后的结果返回 [1, 2] 和 [4, 5] 以及 [9]。因为 [9] 没有配对的，所以什么都不做。
下一次将把 [1, 2] 和 [4, 5] 合并在一起，结果为 [1, 2, 4, 5]， [9] 因为没有配对的又被落下了。
现在只剩下 [1, 2, 4, 5] 和 [9]，最后合并的数组为 [1, 2, 4, 5, 9]`。
自上而下的实现
Swift 实现如下：
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}每一步的解释如下:
如果只有一个元素的数组不需要分割，直接返回即可
找到数组中间位置
使用中间位置递归分割左边部分
同样的分割右边部分
最后把所有的值合并起来，确保都是一直排序的
原文介绍的过程并不具体，计算的时序和栈图应该如下图所示（译者注）swift > [2, 1, 5, 4, 9] > > ---> [2, 1] //递归分割 > --->[2] , [1] //递归分割结束 > --->[1, 2] //对当前进行合并 > > --->[5, 4, 9] //递归分割 > --->[5 ,4], [9]//递归入栈右边第一次分割 > --->[5], [4], [9] //递归入栈右边第二次分割,分割完后开始进行合并 > --->[4，5]，[9] //递归函数出栈右边第一次合并 > ---> [4，5，9] //递归函数出栈右边第二次合并 > > ---> [1，2] [4，5，9] //开始合并 > ---> [1, 2, 4, 5, 9] //合并结束 > > > >
下面是合并算法:
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
orderedPile.reserveCapacity(leftPile.count + rightPile.count)
// 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}看起来可能比较抓狂，其实很简单：
合并时候你需要用两个位置数跟踪两个数组
目前合并用的新数组是空的，但是随后你会将其他数组中元素补充进来。因为已知这个数组填充结束需要的元素数量，需要保持此大小容量以避免额外的开销。
这个 while 循环通过取左右数组更小的值，把它放入
orderedPile中。（从那边取值后，那边的位置数就+1，译者补充）经过第一个循环后，
leftPile或者rightPile肯定有一个会完全合并入orderedPile中。 所以就不用在进行比较了，直接把剩余的数组放入orderedPile中即可。
举个例子介绍解释 merge()， 假如排列 leftPile = [1, 7, 8] 和 rightPile = [3, 6, 9]。 注意这两个序列已经排列过了， 这是归并排序合并的前提。 合并成一个更大而且排序好的序列如下：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r左位置数用 l 指向左序列的第一个元素 1 。右位置数用 r 指向第一个元素 3。因此第一个值是 1 放入 orderedPile 中。移动 l 到下一个位置。
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
-->l r现在 1 指向 7 ，但是 r 仍然在 3 的位置，现在把最小的值 3 放入 orderedPile 中。如下：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r重复过程如下，每步都取 leftPile 或者 rightPile 最小的值，并放入 orderedPile 中：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r
现在左边序列中已经没有值要添加了，现在可以把右边剩余的值放入排序序列中了。结果为 1, 3, 6, 7, 8, 9 。
算法的思想非常简单：从左到右依次遍历两个序列，每次取最小的。这种做法的前提就是需要保证每个序列都是已经排序的。
自下而上
之前看到的算法方式称为 ”自上而下“ ，因为我们先分割数组然后再合并他们。在排序一个数组（链表也可以）的时候你可以不用分割这步直接开始合并单独的数组元素，称为 自下而上 的方法。
是时候更上一层楼了. :-)
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let n = a.count
var z = [a, a] // 1
var d = 0
var width = 1
while width < n { // 2
var i = 0
while i < n { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}看起来比 自上而下 的复杂多了，但是注意代码主体也包含三个和 merge() 相同的 while 循环。
重点如下:
因为不能一边合并左右序列，一边重写序列的内容，归并算法需要一个临时数组。因为每次合并重新初始化一个新数组是很浪费的，用两个数组即可。
d值为 0 或 1，用d来切换使用这两个数组,z[d]用来读取，z[1-d]用来写，这种方式称为双缓冲。原理上 自下而上 的版本和 自下而上 的版本是一样的。首先，先合并一个元素的序列，然后合并两个元素的序列，再合并四个元素的序列。序列的大小由
width决定。width初始值为1，但是在每次循环后都乘以2，所以外层循环决定每次合并的序列大小，排序的数组之增加。里面的循环遍历所有的序列并合并每一对序列，结果通过存入
z[1 - d]。和 自上而下 的算法是一样的逻辑。主要不同在于这里使用了双重循环，从
z[d]中读出，然后存入z[1 - d]中。不是用<而是用isOrderedBefore函数来进行比较。归并算法使用了泛型，你可以用它排列任意类型的对象。此时，
z[d]中的width的序列合并为width * 2的序列存入z[1 - d]中。这里交换一下当前数组，这样下一步就能从新的创建的序列里读取数据。
译者注
可以看做数组本来就是一个一个数字组成，width初始为1， 就是先两两比较成一组，然后写入一个新数组中，两两比较后，就是按组比较，每组两个，所以width * 2即两组比较，以此类推下去，当width < n，2 * width > n时结束排列。 这里用z做双缓冲的意思也很简单，每次读上次排序的数组，然后将比较结果写入下一个结果中。所以这里var z = [a,a]等价于var c = [](); var z = [a,c]， 只有第一个数组会被用来遍历，第二个只是大小和a一样的空数组。
这个函数支持泛型，所以可以支持任何类型的数据，只要你提供一个 isOrderedBefore 的函数用来作比较顺序。
例如：
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]性能
归并排序算法的速度依赖数组大小，数组越大，消耗越大。
数组是否已经排序不会影响归并排序，无论原来元素是否排序过，都需要做同样量的分割和比较。
因此，最好，最坏情况和期望时间复杂度均为 O(n log n) 。
归并排序不方便之处在于需要一个和待排序数组一样的临时的数组，无法就地排序，不如快排方便。
大多数的归并排序都是 稳定 排序。意味着有相同关键值的元素保存相对位置不变。稳定排序对于数字和字符串来说没什么意义，但是在排序复杂对象数据结构时候会很重要。
更多
Boyer-Moore 字符串搜索
栗子
目标：不导入 Foundation ，不使用 NSString 的 rangeOfString() 方法写一个纯Swift版的字符串搜索算法。
换句话说，我们想实现 String 的一个 indexOf(pattern: String) 扩展，返回 第一个查询到的模式字符串的String.Index ，如果不存在返回 nil 。
例如:
// Input:
let s = "Hello, World"
s.indexOf(pattern: "World")
// Output:
<String.Index?> 7
// Input:
let animals = "?????"
animals.indexOf(pattern: "?")
// Output:
<String.Index?> 6注意：奶牛的索引为 6 ，而不是 3，因为这里使用的 emoji，它需要更多的字节。实际的 String.Index 值并不重要只要它指向正确的位置。 brute-force 算法实现，但是效率非常低，尤其在有大量的文本的时候。实际上你不用挨个查看原文本中字符，很多情形下你可以直接跳过一些字符。
这种跳跃式查找的算法称为 Boyer-Moore 。这个算法存在已近已经很久了，它作为字符串查找算法基准。
Swift 版实现：
extension String {
func index(of pattern: String) -> Index? {
//缓存搜索模式串的长度，因为我们以后会多次使用它，计算一次比较耗时。
let patternLength = pattern.count
guard patternLength > 0, patternLength <= count else { return nil }
// 创建跳表，当模式串中的一个字符被找到后决定跳多远
var skipTable = [Character: Int]()
for (i, c) in pattern.enumerated() {
skipTable[c] = patternLength - i - 1
}
//指向模式串的最后一个字符
let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]
//模式串的匹配是自右向左，所以查找时跳的长度根据模式串决定。(因为索引开始值指向字符串中的第一个字符，所以它最小是1)
var i = index(startIndex, offsetBy: patternLength - 1)
//这个函数用于反向遍历原字符串和模式串，找到不匹配的字符或者到达模式串的开头后退出
func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}
//主循环一直遍历到字符串的末尾
while i < endIndex {
let c = self[i]
//当前字符与模式串的最后一个字符是否匹配
if c == lastChar {
//可能匹配，做一个 brute-force 反向查找
if let k = backwards() { return k }
//如果不匹配，只能向前跳过该字符
i = index(after: i)
} else {
//字符不匹配，直接跳过。跳过的距离由跳表决定，如果字符没有在模式串中，可以直接跳模式串的长度，但是如果字符是在模式串中，前面可能有可以匹配的，所以我们现在还不能跳
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}这个算法工作如下。把模式串与原字符串对齐，看看那个字符与模式串的最后一个字符对齐：
source string: Hello, World
search pattern: World
^有三种可能：
这两个字符相等，正好匹配上。
如果字符不相同，但是这个字符在原字符串中存在，也在模式串中存在。
这个字符都没有在模式串中出现过。
举个例子，如下面 o 和 d 不相同，但是 o 出现在搜索字符串中。因为着可以跳过几个字符：
source string: Hello, World
search pattern: World
^注意 o 对齐了，然后再对比搜索字符串的最后一个字符 W 和 d 。两者不同，但是 W 在模式串中出现了。因此跳过几个字符对齐两个 W ：
source string: Hello, World
search pattern: World
^现在两个字符相同，模式串可能与原字符串相同。从尾到头做 brute-force 的反向搜索，这就是这个算法整个流程。
跳过多少位由 “跳表” 决定，它通过字典类型存储每个字符和其要跳跃多少位。跳表如下：
W: 4
o: 3
r: 2
l: 1
d: 0越在模式串末尾的字符，跳的位数越小。如果模式串中有重复的字符，由靠近尾部的字符决定跳的位数。
注意： 如果模式串包含很少的字符，做brute-force搜索也很快，在这种情况下需要权衡一下建跳表的代价，因为做brute-force也很快。
申明：这段代码是基于1989年7月 Costas Menico 在 Dr Dobb 杂志发表的文章 ——《更快的字符搜索》 。1989年啊！有时候保存点旧杂志还是有用的！
参见更加详细的分析
Boyer-Moore-Horspool 算法
上面算法改进版的是 Boyer-Moore-Horspool 算法。
类似 Boyer-Moore 算法，它也使用跳表进行跳跃。不同之处在于我们如何处理部分匹配的情况。在上面的版本中，如果只有部分匹配，我们只跳一个字符，在本算法中，我们也是用跳表。
下面是 Boyer-Moore-Horspool 的算法：
extension String {
func index(of pattern: String) -> Index? {
//缓存搜索模式串的长度，因为我们以后会多次使用它，计算一次比较耗时。
let patternLength = pattern.count
guard patternLength > 0, patternLength <= characters.count else { return nil }
// 创建跳表，当模式串中的一个字符被找到后决定跳多远
var skipTable = [Character: Int]()
for (i, c) in pattern.enumerated() {
skipTable[c] = patternLength - i - 1
}
//指向模式串的最后一个字符
let p = pattern.index(before: pattern.endIndex)
let lastChar = pattern[p]
//模式串的匹配是自右向左，所以查找时跳的长度根据模式串决定。(因为索引开始值指向字符串中的第一个字符，所以它最小是1)
var i = index(startIndex, offsetBy: patternLength - 1)
//这个函数用于反向遍历原字符串和模式串，找到不匹配的字符或者到达模式串的开头后退出
func backwards() -> Index? {
var q = p
var j = i
while q > pattern.startIndex {
j = index(before: j)
q = index(before: q)
if self[j] != pattern[q] { return nil }
}
return j
}
//主循环一直遍历到字符串的末尾
while i < endIndex {
let c = self[i]
//当前字符与模式串的最后一个字符是否匹配
if c == lastChar {
//可能匹配，做一个 brute-force 反向查找
if let k = backwards() { return k }
//确定至少可以跳一个字符(因为第一个字符是在跳表中，而且 `skipTable[lastChar] = 0`)
let jumpOffset = max(skipTable[c] ?? patternLength, 1)
i = index(i, offsetBy: jumpOffset, limitedBy: endIndex) ?? endIndex
} else {
//字符不匹配，直接跳过。跳过的距离由跳表决定，如果字符没有在模式串中，可以直接跳模式串的长度，但是如果字符是在模式串中，前面可能有可以匹配的，所以我们现在还不能跳
i = index(i, offsetBy: skipTable[c] ?? patternLength, limitedBy: endIndex) ?? endIndex
}
}
return nil
}
}实际上 Horspool 版本的算法要比原先的好一些，但是还是要看你做什么。