第26章：O(n²)排序算法

O(n²)的时间复杂度并不是很好的表现，但是这一类的排序算法很容易理解，在一些场景中也很有用。这些算法的空间效率很高；它们只需要恒定的O(1)的额外内存空间。对于小型数据集，这些排序与更复杂的排序相比非常有利。

在本章中，你将会看到以下排序算法。

冒泡排序
选择排序
插入排序

所有这些都是基于比较的排序方法。它们依赖于一种比较方法，例如小于运算符，来对元素进行排序。这种比较被调用的次数是你衡量一个排序技术一般性能的方法。

冒泡排序

最直接的排序方法之一是冒泡排序，它反复比较相邻的值，并在需要时交换它们，以执行排序。因此，集合中较大的值会 "冒泡 "到集合的末端。

例子

考虑一下下面这手牌。

冒泡排序算法的单次传递将包括以下步骤。

从牌集的开头开始。比较9和4。这些数值需要被交换。然后集合变成[4, 9, 10, 3]。
移动到集合中的下一个索引。比较9和10。这些都是有顺序的。
移动到集合中的下一个索引。比较10和3。这些值需要互换。然后集合就变成了[4, 9, 3, 10]。

该算法的一次通过很少会导致完整的排序，这对这个集合来说是真的。然而，它将导致最大的值--10--冒出到集合的末端。

随后通过该集合将分别对9和4进行同样的处理。

只有当你能在不交换任何值的情况下对集合进行一次完整的传递时，排序才算完成。在最坏的情况下，这将需要n-1次传递，其中n是集合中成员的数量。

实现

打开本章的 Swift 游戏场以开始学习。在游乐场的Sources目录下，创建一个名为BubbleSort.swift的新文件。在该文件中写下以下内容。

下面是具体的操作过程。

如果集合中的元素少于两个，就没有必要对其进行排序。
单次传递将最大的值泡到集合的末端。每一次传递都需要比上一次传递少一个值，所以每一次传递基本上都会使数组缩短一个。
这个循环执行一个单次传递；它比较相邻的值，并在需要时将它们交换。
如果这次没有交换值，集合必须被排序，你可以提前退出。

试试吧! 回到playground的主页面，写下以下内容。

example(of: "bubble sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)") 
  bubbleSort(&array) 
  print("Bubble sorted: \(array)")
}

你应该看到以下输出。

---Example of bubble sort--
Original: [9, 4, 10, 3] 
Bubble sorted: [3, 4, 9, 10]

如果已经排序，泡泡排序的最佳时间复杂度为O(n)，最差和平均时间复杂度为O(n²)，这使得它成为已知宇宙中最不吸引人的排序方式之一。

选择排序

选择排序遵循冒泡排序的基本思想，但通过减少swapAt操作的数量来改进这种算法。选择排序将只在每次结束时进行交换。你会在下面的例子和实现中看到它是如何工作的。

例子

假设你有以下的手牌。

在每一次传递过程中，选择排序将找到未排序的最低值，并将其交换到位。

首先，3被发现为最低值。它将与9互换。
下一个最低值是4，它已经在正确的位置上了。
最后，9与10互换。

实现

在你的游乐场的Source目录下，创建一个名为SelectionSort.swift的新文件。在该文件中写下以下内容。

以下是发生的情况。

你对集合中的每一个元素进行传递，除了最后一个元素。

没有必要包括最后一个元素，因为如果所有其他元素的顺序都是正确的，最后一个元素也是如此。

在每一次传递中，你都要穿过集合的其余部分，找到价值最低的元素。
如果该元素不是当前元素，则将其交换。

试试吧! 回到主playground页面，添加以下内容。

example(of: "selection sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)") 
  selectionSort(&array) 
  print("Selection sorted: \(array)")
}

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

---Example of selection sort--
Original: [9, 4, 10, 3] 
Selection sorted: [3, 4, 9, 10]

就像冒泡排序一样，选择排序的最佳、最差和平均时间复杂度为O(n²)，这是相当糟糕的。不过，这是一个简单的理解，而且它确实比冒泡排序的表现要好!

插入排序

插入排序是一种更有用的算法。与冒泡排序和选择排序一样，插入排序的平均时间复杂度为O(n²)，但插入排序的性能会有所不同。数据越是已经被排序，它需要做的工作就越少。如果数据已经被排序，插入排序的最佳时间复杂度为O(n)。Swift标准库的排序算法使用了一种混合的排序方法，插入排序用于小的（<20个元素）未排序分区。

例子

插入排序的概念类似于你对一手牌的排序。请看下面这副牌。

插入排序将从左到右对牌进行一次迭代。每张牌都会向左移动，直到它到达正确的位置。

你可以忽略第一张牌，因为没有以前的牌可以和它比较。
接下来，你将4与9进行比较，并将4与9互换位置，向左移动。
10不需要移位，因为与前一张牌相比，它的位置是正确的。
最后，通过与10、9和4的比较和互换，3被全部移到前面。

值得指出的是，插入排序的最佳情况发生在数值序列已经排序的情况下，没有必要进行左移。

实现

在你的游乐场的Source目录下，创建一个名为InsertionSort.swift的新文件。在该文件中写下以下内容。

下面是你在上面做的事情。

插入排序要求你从左到右迭代一次。这个循环就是这样做的。
在这里，你从当前索引开始向后运行，所以你可以根据需要向左移动。
只要有必要，就一直向左移动元素。一旦元素就位，就中断内循环并开始下一个元素。

回到主playground页面，在底部写下以下内容。

example(of: "insertion sort") {
  var array = [9, 4, 10, 3]
  print("Original: \(array)") 
  insertionSort(&array) 
  print("Insertion sorted: \(array)")
}

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

---Example of insertion sort--
Original: [9, 4, 10, 3] 
Insertion sorted: [3, 4, 9, 10]

如果数据已经被排序，插入排序是最快的排序算法之一。这可能听起来很明显，但并不是所有的排序算法都是如此。在实践中，许多数据集合已经基本上--如果不是完全--被排序了，插入排序在这些情况下会表现得特别好。

归纳

在这一节中，你将为数组以外的集合类型概括这些排序算法。不过，到底是哪种集合类型，取决于算法的情况。

插入排序在移动元素的时候会向后遍历集合。因此，集合必须是 BidirectionalCollection 类型。
冒泡排序和选择排序只从前到后遍历集合，所以它们可以处理任何集合。
在任何情况下，集合必须是MutableCollection，因为你需要能够交换元素。

回到BubbleSort.swift中，将该函数更新为如下内容。

该算法保持不变；你更新了循环，以使用集合的索引。回到playground的主页面，验证冒泡排序仍然按照它应该的方式工作。

选择排序可以按如下方式更新。

而插入排序就变成了。

只要稍加练习，泛化这些算法就会成为一个有点机械的过程。

在接下来的章节中，你将看到性能优于O(n²)的排序算法。接下来是一种使用被称为分而治之的经典方法的排序算法--合并排序!

关键点

n²算法通常有一个可怕的声誉。不过，其中一些算法通常还是有一些值得称道之处。如果集合已经处于排序状态，插入排序可以在O(n)时间内完成排序，并逐渐缩小到O(n²)。
在你知道你的数据大部分提前处于排序顺序的情况下，插入排序是最好的排序之一。

上一章	目录	下一章