O(n²) 的排序算法

冒泡排序

最常见的排序方法就是冒泡排序，冒泡排序会重复比较两个相邻的元素，如果需要排序，就要执行排序。集合中最大的元素会上升到集合的尾部。

示例

观察如下卡片：

sort1.png

一个完整的冒泡排序算法由以下几步组成：

• 在集合的开始部分，9和4进行比较，需要进行交换，该集合变成 [4, 9, 10, 3]。
• 接下来比较 9和10，由于 9 小于 10，不需要进行交换。该集合 还是 [4, 9, 10, 3]。
• 接下来比较 10 和 3，需要进行交换，该集合变为 [4, 9, 3, 10]
  经过上述的排序之后，卡片的顺序为
  sort2.png
  对集合重复以上操作，第二次执行完成时，卡片的顺序为：
  sort3.png
  重复执行第3次之后：
  sort4.png

代码实现

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
    }
  }
}

1，如果数组的长度小于2，则没有必要进行排序了。
2，一次冒泡排序会将最大的元素放到集合的最末端，每个回合比较的次数，都会比上一回合的比较次数少一次。
3，每个回合，都会对两个相邻的元素进行比较，如果需要交换位置就进行交换。
4，如果在其中一个回合中，没有发生元素交换，则说明数组已经是有序的，则无需进行下一回合的比较了，直接退出即可。

选择排序

选择排序是在冒泡排序的基础上，减少 交换(swap at)的操作。选择排序在每一回合结束后，会执行交换操作。接下来，你会看到选择排序是如何操作的。

示例

sort5.png
在每一回合中，选择排序会找到最小的元素，并把它交换至相应位置：
1，首先，遍历数组，找到最小值3，并和9进行交换，顺序变为3, 4, 10, 9
2，第二次遍历的时候，从 4开始查找，4是最小值，已经在正确的位置上了，无需进行交换了。
3，第三次遍历是，从10 开始，交换 10 和 9的位置。
sort6.png

实现

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)
    }
  }
}

1，在每一个回合中，找到值最小元素的位置，如果其不再正确的位置上，则需要进行调整。
2，在每一个次遍历中，找到最小的元素，并记录下来。
3，如果最小值元素的索引和当前索引不一致，则交换两个元素。

插入排序

插入排序是一个更有用的算法，和冒泡排序、选择排序类似，插入排序平均时间复杂度为O(n²)，但是插入排序的性能有所不同，如果更多的数据已经排好序，则排序的效率会更高，在Swift标准库中，当对小于20个元素进行排序时，使用的是插入排序。

示例

插入排序的思想和你在玩牌时，对牌进行整理的思想有点相似。考虑以下情景：

sort7.png

插入排序将会从左到右依次遍历卡牌，然后移动卡牌，直到完全符合排序规则为止。

sort8.png

• 1，第一张牌9，由于没有牌在第一张前面可以用来比较，所以可以忽略第一张牌。
• 2，接下来，用 4 和 9 进行比较，通过将 4 和 9 进行交换，将 4 移到左边。
• 3，通过 10和 9 进行比较，10 不需要进行移动。
• 4，最后，通过 3 和 10， 9，4 进行比较，3 插入到最前面。

public func insertionSortTwo<Element>(_ array: inout [Element]) where Element: Comparable {

    guard array.count > 1 else {
        return
    }

    print("Array: \(array)")
    for begin in (1..<array.count) {
        // 找到要插入的位置
        let des = search(begin, array)
        print("begin: \(begin), des: \(des)")
        // 插入元素
        insert(begin, des, &array)
    }
}
/*
 将 source 位置的元素插入到dest位置
 */
private func insert<Element>(_ source: Int, _ dest: Int, _ sourceArray: inout [Element]) where Element: Comparable{
    // 对source处的值进行备份
    let e = sourceArray[source]

    if dest == source {
        print("排序后的Array: \(sourceArray)")
        return
    }

    // 将 [dest, source)区间的元素后移
    for i in (dest...source).reversed() where i > 0 {
        sourceArray[i] = sourceArray[i - 1]
    }

    sourceArray[dest] = e

    print("排序后的Array: \(sourceArray)")

}

/*
 利用二分搜索找到 index位置元素的待插入位置
 已经排好序数组的范围时 [0, index)
 */
private func search<Element>(_ index: Int, _ sourceArray: [Element]) -> Int where Element: Comparable {
    var begin = 0
    var end = index

    // 当 begin == end 时，查找结束，这时的 begin 就是插入位置的索引。
    while begin < end {
        let mid = (begin + end) >> 1
        if sourceArray[index] < sourceArray[mid] {
            end = mid
        } else {
            begin = mid + 1
        }
    }
    return begin;
}

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》