时间复杂度为O(n^2)的排序算法性能并不好，但作为刚入门算法的同学来说，还是有必要学习一下的。这里我们会讲到三种排序算法：1）冒泡排序；2）选择排序；3）插入排序。
冒泡排序
原理
首先介绍下冒泡排序算法的原理：
- 从第一个元素开始，比较相邻的元素，如果第一个比第二个大，就交换它们的值
- 对每一组相邻元素做同样的操作，完成最后一组的操作后，最后的元素肯定是最大的数
- 除了最后已排好序的元素，对其他所有的元素重复以上的步骤
- 重复上面的步骤，直到没有任何一组数字需要比较
例子
下面看一个例子，假设我们有下面的数组：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 8 | | 7 | | 14 | | 5 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
根据上面的原理，首先将第一个和第二个比较，8 与 7 交换，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 7 | | 8 | | 14 | | 5 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
第二个和第三个继续比较，第三个数 14 大于第二个数 8，无需交换。
第三个和第四个比较，14 与 5 交换，至此第一轮的比较已经完成，最后一个数就是最大的数。结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 7 | | 8 | | 5 | | 14 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
下面是第二轮对比，第一组 7 和 8 的顺序已经是对的，无需再交换；第一组 8 和 5，需要交换，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 7 | | 5 | | 8 | | 14 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
最后一个已经是做大的了，不用再对比。也就是说每经过一轮对比，下一轮要对比的元素就会少一个。
下面第三轮对比，7 与 5 交换，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 5 | | 7 | | 8 | | 14 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
因为这是第三轮的对比，后面两个数不需要再对比，到此，排序完成。
实现
为了保证方法的通用性，我们不仅对数组进行排序。Swift 中有一个协议叫做 MutableCollection， 这个协议规定 collection 必须支持通过下标去访问或者修改里面的元素，所以我们直接对 MutableCollection 类型的对象进行排序。
实现代码如下：
func bubbleSort<T>(_ collection: inout T)
where T: MutableCollection, T.Element: Comparable {
guard collection.count > 1 else {
return
}
for end in collection.indices.reversed() {
var swapped = false
var current = collection.startIndex
while current < end {
let next = collection.index(after: current)
if collection[next] < collection[current] {
collection.swapAt(next, current)
swapped = true
}
current = next
}
if !swapped {
return
}
}
}
代码解析：
- 首先，至少要有两个元素，我们才进行排序，如果
collection.count不大于1，直接返回 - 因为每经过一轮对比，下一轮对比就要忽略最后的元素，所以
for循环的循环条件，把indices倒序 - 定义了一个
swapped变量，记录当前这轮对比是否有调换过元素 -
while循环执行当前这一轮对比，如果后面的元素小于前面的元素就调换位置 - 如果
swapped为false，说明当前这轮对比没有调换过元素，也就意味着已经排好序，提前退出循环
测试
var ints = [4,5,5467,73,234,678,87,989]
bubbleSort(&ints)
print(ints)
// 结果
[4, 5, 73, 87, 234, 678, 989, 5467]
结果正确。
选择排序
选择排序对冒泡排序进行了一些改进，减少了元素之间的交换次数。选择排序只在每一轮对比完成之后才叫换一次。
例子
下面看一个例子，假设我们有下面的数组：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 8 | | 7 | | 14 | | 5 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
首先找到最小的元素 5，8 与 5 交换，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 5 | | 7 | | 14 | | 8 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
再找到除第一个元素外的最小元素 7，7 在第二个位置，无需交换。
再找到除前面两个元素外的最小元素8，放到第三个位置，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 5 | | 7 | | 8 | | 14 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
到此，排序完成。很明显，交换的次数比冒泡排序少了很多。
实现
为了保证方法的通用性，跟冒泡排序一样，我们直接对 MutableCollection 类型的对象进行排序。
func selectionSort<T>(_ collection: inout T)
where T: MutableCollection, T.Element: Comparable {
guard collection.count > 1 else {
return
}
for current in collection.indices {
var lowest = current
var next = collection.index(after: current)
while next < collection.endIndex {
if collection[next] < collection[lowest] {
lowest = next
}
next = collection.index(after: next)
}
if lowest != current {
collection.swapAt(lowest, current)
}
}
}
代码解析：
- 首先，至少要有两个元素，我们才进行排序，如果
collection.count不大于1，直接返回 - 因为每经过一轮交换，下一轮要忽略前面的元素，所以使用
for循环，条件是从最小的下标开始 -
while循环找出最小的元素 - 如果找到的最小元素与当前元素不相等，则交换位置
测试
var ints = [4,5,5467,73,234,678,87,989]
selectionSort(&ints)
print(ints)
// 结果
[4, 5, 73, 87, 234, 678, 989, 5467]
结果正确。
插入排序
插入排序的原理：将当前的元素与上一个进行对比，如果当前的元素小于上一个元素，则交换位置，重复这个步骤，直到把它放到合适的位置为止。
例子
下面看一个例子，假设我们有下面的数组：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 8 | | 7 | | 14 | | 5 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
因为第一个元素前面没有其他元素，所以忽略第一个元素。
第二个元素 7 与前面的 8 对比，需要交换位置，结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 7 | | 8 | | 14 | | 5 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
第三个元素 14 比前面的两个元素都大，无需交换。
第四个元素 5，比前面的元素都小，所以他会一直与前面的元素交换，直到它在第一个位置。结果如下：
+--------+ +--------+ +--------+ +--------+
| | | | | | | |
| 5 | | 7 | | 8 | | 14 |
| | | | | | | |
+--------+ +--------+ +--------+ +--------+
实现
为了保证方法的通用性，我们不直接对数组类型进行排序，而是 Swift 的集合类型。首先我们要交换元素的位置，集合类型必须是 MutableCollection 类型；另外我们还要访问上一个元素，BidirectionalCollection类型才拥有这个特性。所以我们排序的类型是 BidirectionalCollection & MutableCollection。代码如下：
func insertionSort<T>(_ collection: inout T)
where T: BidirectionalCollection & MutableCollection,
T.Element: Comparable {
guard collection.count > 1 else {
return
}
for current in collection.indices {
var moving = current
while moving > collection.startIndex {
let previous = collection.index(before: moving)
if collection[previous] > collection[moving] {
collection.swapAt(previous, moving)
} else {
break
}
moving = previous
}
}
}
- 首先，至少要有两个元素，我们才进行排序，如果
collection.count不大于1，直接返回 -
for循环保证当前将要往左运动的元素 -
while循环里面，把当前元素与上一个元素对比，如果上一个元素大于当前元素，则交换位置；否则前面的元素肯定已经排好序，所以直接break
测试
var ints = [4,5,5467,73,234,678,87,989]
insertionSort(&ints)
print(ints)
// 结果
[4, 5, 73, 87, 234, 678, 989, 5467]
结果正确。
完整代码 >>
参考资料
Data Structures and Algorithms in Swift --- raywenderlich.com，如果想看原版书籍，请点击链接购买。
完
欢迎加入我管理的Swift开发群：536353151。
