26.`O(n²)`排序算法¶

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

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

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

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

冒泡排序¶

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

例子¶

考虑下面这手牌：

冒泡排序算法的一次通过将包括以下步骤：

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

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

随后通过该集合将分别对9和4做同样的处理：

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

实施¶

打开本章的Swift playground来开始吧。在playground的Sources目录下，创建一个名为BubbleSort.swift的新文件。在该文件中写下以下内容：

public func bubbleSort<Element>(_ array: inout [Element])
    where Element: Comparable {
  // 1
  guard array.count >= 2 else {
    return
  }
  // 2
  for end in (1..<array.count).reversed() {
    var swapped = false
    // 3
    for current in 0..<end {
      if array[current] > array[current + 1] {
        array.swapAt(current, current + 1)
        swapped = true
      }
    }
    // 4
    if !swapped {
      return
    }
  }
}

下面是分解步骤的过程：

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

试试吧! 回到操场的主页面，写下以下内容：

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²)，使它成为已知宇宙中不吸引人的排序之一。

选择排序¶

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

例子¶

假设你有以下的手牌：

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

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

实施¶

在你的playground的Sources目录下，创建一个名为SelectionSort.swift的新文件。在该文件中写下以下内容：

public func selectionSort<Element>(_ array: inout [Element])
    where Element: Comparable {
  guard array.count >= 2 else {
    return
  }
  // 1
  for current in 0..<(array.count - 1) {
    var lowest = current
    // 2
    for other in (current + 1)..<array.count {
      if array[lowest] > array[other] {
        lowest = other
      }
    }
    // 3
    if lowest != current {
      array.swapAt(lowest, current)
    }
  }
}

以下是发生的情况：

你对集合中的每一个元素进行传递，除了最后一个元素。没有必要包括最后一个元素，因为如果所有其他元素的顺序都是正确的，最后一个元素也是如此。
在每一次传递中，你都要穿过集合的其余部分，找到价值最低的元素。
如果该元素不是当前的元素，则将其交换。

试试吧! 回到主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进行比较，并通过与9交换位置将4移到左边。
10不需要移位，因为与前一张牌相比，它的位置是正确的。
最后，3通过与10、9和4的比较和互换，分别将其全部移到前面。

值得指出的是，插入式排序的最佳情况发生在数值序列已经排序的情况下，而不需要左移。

实施¶

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

public func insertionSort<Element>(_ array: inout [Element])
    where Element: Comparable {
  guard array.count >= 2 else {
    return
  }
  // 1
  for current in 1..<array.count {
    // 2
    for shifting in (1...current).reversed() {
      // 3
      if array[shifting] < array[shifting - 1] {
        array.swapAt(shifting, shifting - 1)
      } else {
        break
      }
    }
  }
}

下面是你的上述做法：

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

回到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]

如果数据已经被排序，插入排序是最快的排序算法之一。这听起来很明显，但这并不是所有排序算法的真实情况。在实践中，许多数据集合在很大程度上已经被排序了--如果不是完全被排序的话，插入排序在这些情况下会表现得非常好。

归纳¶

在本节中，你将对这些排序算法进行泛化，以适用于除Array以外的集合类型。不过，具体哪些集合类型，取决于算法：

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

回到BubbleSort.swift，将函数更新为以下内容：

public func bubbleSort<T>(_ collection: inout T)
    where T: MutableCollection, T.Element: Comparable {
  guard collection.count >= 2 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[current] > collection[next] {
        collection.swapAt(current, next)
        swapped = true
      }
      current = next
    }
    if !swapped {
      return
    }
  }
}

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

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

public func selectionSort<T>(_ collection: inout T)
    where T: MutableCollection, T.Element: Comparable {
  guard collection.count >= 2 else {
    return
  }
  for current in collection.indices {
    var lowest = current
    var other = collection.index(after: current)
    while other < collection.endIndex {
      if collection[lowest] > collection[other] {
        lowest = other
      }
      other = collection.index(after: other)
    }
    if lowest != current {
      collection.swapAt(lowest, current)
    }
  }
}

而插入式排序则成为：

public func insertionSort<T>(_ collection: inout T)
    where T: BidirectionalCollection & MutableCollection,
          T.Element: Comparable {
  guard collection.count >= 2 else {
    return
  }
  for current in collection.indices {
    var shifting = current
    while shifting > collection.startIndex {
      let previous = collection.index(before: shifting)
      if collection[shifting] < collection[previous] {
        collection.swapAt(shifting, previous)
      } else {
        break
      }
      shifting = previous
    }
  }
}

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

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

关键点¶

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

26.O(n²)排序算法¶

冒泡排序¶

例子¶

实施¶

选择排序¶

例子¶

实施¶

插入式排序¶

例子¶

实施¶

归纳¶

关键点¶

26.`O(n²)`排序算法¶