第29章：归并排序进阶

挑战1：加快追加的速度

考虑一下下面的代码。

let size = 1024 
var values: [Int] = [] 
// 1 
for i in 0 ..< size { 
  values.append(i) 
}

这段代码将导致近十次的重新分配。在//1处添加一条语句，将其减少为一次分配。

提示：reserveCapacity是你的朋友。

挑战2：归并两个序列

编写一个函数，接收两个排序的序列并将它们归并成一个序列。下面是开始时的函数签名。

AnySequence是一个类型清除器，它抽象了具体的实现细节。

解决方案

挑战1的解决方案

let size = 1024 
var values: [Int] = [] 
values.reserveCapacity(size) for i in 0 ..< size { 
  values.append(i) 
}

使用reserveCapacity是加快追加速度的一个好方法。

挑战2的解决方案

这一挑战的棘手之处在于序列的能力有限。这种算法的传统实现依赖于集合类型的能力，如数组来跟踪索引。

由于Sequence类型没有索引的概念，你要利用其迭代器。打开启动器项目，开始。将其内容更新为以下内容。

设置该算法包括以下步骤。

1. 创建一个新的容器来存储归并后的序列。

2. 抓住第一个和第二个序列的迭代器。迭代器通过下一个方法依次分配序列的值。

3. 创建两个变量，初始化为第一个和第二个迭代器的第一个值。 next返回序列中的一个可选的元素，而一个nil的返回值表明迭代器已经分配了序列中的所有元素。

使用迭代器，你将通过比较第一个和第二个下一个值来决定哪个元素应该被追加到结果数组中。在归并函数的末尾写上以下内容。

这段代码是归并算法的主要组成部分。使用while let，你检查是否有必要比较哪些值要插入到结果数组中。

1. 如果第一个值小于第二个值，你将在结果中追加第一个值，并通过在第一个迭代器上调用next，为下一个要比较的值做种子。

2. 如果第二个值小于第一个值，你将做相反的事情。你通过在第二个迭代器上调用next来为下一个被比较的值播种。

3. 你同时追加第一个和第二个值，如果它们相等，你就给两个下一个值做种子。

这个过程将继续下去，直到其中一个迭代器用完了要分配的元素。在这种情况下，这意味着剩下元素的迭代器的元素等于或大于结果中的当前值。

要添加其余的这些值，请在归并函数的末尾写下以下内容。

通过写下面的内容来确认这个函数是否工作。

var array1 = [1, 2, 3, 4, 5, 6, 7, 8]
var array2 = [1, 3, 4, 5, 5, 6, 7, 7]
for element in merge(first: array1, second: array2) { 
  print(element) 
}

你应该看到下面的控制台输出。

1
1
2
3
3
4
4
5
5
5
6
6
7
7
7
8

---

上一章	目录	下一章