搜索算法

• *线性搜索－从数组中查找某个元素。

• 二分搜索－从已排序的数组中快速查找元素。

• 统计出现次数－统计某个值在数组中的出现次数。

• 查找最大／最小值－找到数组中的最大／最小值。

• 第 K 大元素－找到数组中的第 K 大元素，例如中位数。

• 选取样本－随机地从集合中选取一些元素作为样本。

• 并查集－保持一些不相交的集合，帮助你快速合并它们。

线性搜索（Linear Search）

目标：在数组中查找特定值。

我们有一组通用对象。 通过线性搜索，我们迭代数组中的所有对象，并将每个对象与我们正在寻找的对象进行比较。 如果两个对象相等，我们停止并返回当前对象在数组中的索引。 如果不相等，只要数组中还有对象，我们就会继续寻找下一个。

一个例子

假设我们有一个数组[5,2,4,7]，我们想检查数组是否包含数字2。

我们首先将数组中的第一个数字5与我们正在寻找的数字2进行比较。 它们显然不一样，所以我们继续比较下一个数组元素。

我们将数组中的数字2与数字2进行比较，注意到它们是相等的。 现在我们可以停止迭代并返回1，这是数组中数字2的索引。

代码

这是Swift线性搜索的简单实现：

func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
  for (index, obj) in array.enumerated() where obj == object {
    return index
  }
  return nil
}

将此代码放在playground里测试：

let array = [5, 2, 4, 7]
linearSearch(array, 2) 	// This will return 1

性能

线性搜索性能是O(n) 。它将我们要查找的对象与数组中的每个对象进行比较，因此它所花费的时间与数组长度成正比。在最坏的情况下，我们需要查看数组中的所有元素。

最好的情况是 O(1)，但这种情况很少见，因为我们要查找的对象必须位于数组的开头才能立即找到。你可能会很幸运，但大部分时间你都不会。平均而言，线性搜索需要查看数组中对象的一半。

扩展阅读

线性搜索的维基百科

二分搜索(Binary Search)

目标：在数组中快速寻找一个元素。

假设你有一个数字数组，你想确定一个特定的数字是否在该数组中，如果在，那么获得这个数字的索引。

对于上面的情况，Swift的indexOf()函数足够完成：

let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]

numbers.indexOf(43)  // returns 15

内置的indexOf()函数执行的是线性搜索。代码大概是：

func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
    for i in 0 ..< a.count {
        if a[i] == key {
            return i
        }
    }
    return nil
}

使用如下：

linearSearch(numbers, 43)  // returns 15

有什么问题呢？ linearSearch（）从头开始遍历整个数组，直到找到你正在寻找的元素。 在最坏的情况是数值不在数组中，那么之前的遍历就白费。

平均而言，线性搜索算法需要查看数组中一半的值。 如果您的数组足够大，这将会变得非常慢！

分而治之

提升速度的经典方法是使用 二分搜索。 诀窍是将数组分成两半，直到找到值。

对于大小为n的数组，性能不是线性搜索的O(n)，而是只有 O(log n)。换句话说，对具有1,000,000个元素的数组进行二分搜索只需要大约20个步骤来查找要查找的内容，因为log_2（1,000,000）= 19.9。对于具有十亿个元素的数组，它只需要30步。 （然而，你上一次使用数十亿项的数组是什么时候？）

听起来很棒，但使用二分搜索有一个缺点：数组必须被排好序的。 在实践中，这通常不是问题。

下面二分搜索的工作原理：

• 将数组分成两半，并确定您要查找的内容（称为搜索键）是在左半部分还是在右半部分。

• 您如何确定搜索键的键在哪一半呢？ 这就是首先要对数组进行排序的原因，排好序你就可以做一个简单的<或>比较。

• 如果搜索键位于左半部分，则在那里重复该过程：将左半部分分成两个更小的部分，并查看搜索键位于哪一块。 （同样，对于右半部分同样处理。）

• 重复此操作直到找到搜索键。 如果无法进一步拆分数组，则必须遗憾地得出结论，搜索键不在数组中。

现在你知道为什么它被称为“二分”搜索：在每一步中它将数组分成两半。 分而治之 可以快速缩小搜索键所在的位置。

代码

这是Swift中二分搜索的递归实现：

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
    if range.lowerBound >= range.upperBound {
        // If we get here, then the search key is not present in the array.
        return nil

    } else {
        // Calculate where to split the array.
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        // Is the search key in the left half?
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)

        // Is the search key in the right half?
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)

        // If we get here, then we've found the search key!
        } else {
            return midIndex
        }
    }
}

尝试一下，将代码复制到 playground 并执行以下操作：

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

binarySearch(numbers, key: 43, range: 0 ..< numbers.count)  // gives 13

请注意，numbers数组已排序。 否则二分搜索算法不能工作！

二分搜索通过将数组分成两半来搜索，但我们实际上并没有创建两个新数组。 我们使用SwiftRange对象跟踪这些拆分。起初，此范围涵盖整个数组，0 .. <numbers.count。 当我们拆分数组时，范围变得越来越小。

注意： 需要注意的一点是range.upperBound总是指向最后一个元素之后的元素。 在这个例子中，范围是0 .. <19，因为数组中有19个数字，所以range.lowerBound = 0和range.upperBound = 19。但是在我们的数组中，最后一个元素是在索引18而不是19，因为我们从0开始计数。在处理范围时要记住这一点：upperBound总是比最后一个元素的索引多一。

分步执行示例

查看算法的详细工作方式或许是很有用的。

上例中的数组由19个数字组成，排序后如下所示：

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

我们试图确定数字43是否在这个数组中。

将数组拆分为一半，我们需要知道中间对象的索引。 这是由这行代码确定：

let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

最初，范围有lowerBound = 0和upperBound = 19。 细看，我们发现midIndex是0 +（19 - 0）/ 2 = 19/2 = 9。 它实际上是9.5，但因为我们使用的是整数，所以答案是向下舍入了。

在下图中，*处表示中间项。 如您所见，每侧的项目数相同，因此我们将在中间分开。

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                  *

二分搜索将确定使用哪一半的相关代码是：

if a[midIndex] > key {
    // use left half
} else if a[midIndex] < key {
    // use right half
} else {
    return midIndex
}

在这种情况下，a[midIndex] = 29。 这比搜索键的值小，所以我们可以得出结论，搜索键永远不会出现在数组的左半部分。毕竟，左半部分只包含小于29的数字。 因此，搜索键肯定位于右半部分（或根本不在数组中）。

现在我们可以简单地重复二分搜索，数组间距从midIndex + 1到range.upperBound：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

由于我们不再需要关注数组的左半部分，我用x标记了它。 从现在开始，我们只看右半部分，从数组索引10开始。

我们计算新的中间元素的索引：midIndex = 10 +（19 - 10）/ 2 = 14，然后再将数组从中间拆分。

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                                 *

正如你所看到的，a [14]是数组右半部分的中间元素。

搜索键是大于还是小于a [14]？ 小，因为43 <47。 这次我们取左半边并忽略右边较大的数字：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]

新的midIndex如下：

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
                                     *

搜索键大于37，因此继续右侧：

[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
                                        *

同样，搜索键更大，因此再次拆分并采取右侧：

[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
                                            *

现在我们已经完成了。搜索键等于我们正在查看的数组元素，所以我们终于找到了我们要搜索的内容：数字43位于数组索引13。

这可能看起来像很多工作，但实际上只需要四个步骤就能找到数组中的搜索键，因为log_2（19）= 4.23。通过线性搜索，它将花费14个步骤。

如果我们要搜索42而不是43会发生什么？在这种情况下，最后我们不能再进一步拆分数组。 range.upperBound变得小于range.lowerBound。这告诉算法搜索键不在数组中，它返回nil。

注意： 二分搜索许多执行会计算 midIndex = (lowerBound + upperBound) / 2。这包含了一个在非常大的数组中会出现的细微bug，因为lowerBound + upperBound可能溢出一个整数可以容纳的最大数。这种情况不太可能发生在64位CPU上，但绝对可能在32位机器上发生。

迭代与递归

二分搜索本质上是递归的，因为您将相同的逻辑一遍又一遍地应用于越来越小的子数组。 但是，这并不意味着您必须将binarySearch()实现为递归函数。 将递归算法转换为迭代版本通常更有效，使用简单的循环而不是大量的递归函数调用。

这是Swift中二分搜索的迭代实现：

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}

如您所见，代码与递归版本非常相似。 主要区别在于使用while循环。

使用迭代实现：

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

binarySearch(numbers, key: 43)  // gives 13

结束

数组必须先排序是一个问题？ 排序是需要时间的 —— 二分搜索和排序的组合可能比进行简单的线性搜索要慢。但是在您只排序一次然后进行多次搜索的情况下，二分搜索会起到大作用。

二分搜索的维基百科

统计出现次数(Count Occurrences)

目标：计算某个值在数组中出现的次数。

显而易见的方法是从数组的开头直到结束的线性搜索，计算您遇到该值的次数。 这是一个 O(n) 算法。

但是，如果数组已经排过序的，则可以通过使用修改二分搜索来更快的完成这个任务，时间复杂度为O(logn)。

假设我们有以下数组：

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

如果我们想知道值3出现的次数，我们可以进行常规二分搜索。 这可以获得四个3索引中的一个：

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
           *  *  *  *

但是，这仍然没有告诉你有多少其它的3。 要找到那些其它的3，你仍然需要在左边进行线性搜索，在右边进行线性搜索。 在大多数情况下，这将是足够快的，但在最坏的情况下 —— 当这个数组中除了之前的一个3之外就没有其它3了 —— 这样时间复杂度依然是O(n)。

一个诀窍是使用两个二分搜索，一个用于查找3开始（左边界）的位置，另一个用于查找3结束的位置（右边界）。

代码如下：

func countOccurrencesOfKey(_ key: Int, inArray a: [Int]) -> Int {
  func leftBoundary() -> Int {
    var low = 0
    var high = a.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] < key {
        low = midIndex + 1
      } else {
        high = midIndex
      }
    }
    return low
  }

  func rightBoundary() -> Int {
    var low = 0
    var high = a.count
    while low < high {
      let midIndex = low + (high - low)/2
      if a[midIndex] > key {
        high = midIndex
      } else {
        low = midIndex + 1
      }
    }
    return low
  }

  return rightBoundary() - leftBoundary()
}

请注意，辅助函数leftBoundary()和rightBoundary()与二分搜索算法非常相似。最大的区别在于，当它们找到搜索键时，它们不会停止，而是继续前进。

要测试此算法，将代码复制到 playground，然后执行以下操作：

let a = [ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

countOccurrencesOfKey(3, inArray: a)  // returns 4

请记住： 使用的数组，确保已经排序过！

来看看这个例子的过程。 该数组是：

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]

为了找到左边界，我们从low = 0和high = 12开始。 第一个中间索引是6：

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
                    *

通过常规二分搜索，你现在就可以完成了，但是我们不只是查看是否出现了值3 —— 而是想要找到它第一次出现的位置。

由于该算法遵循与二分搜索相同的原理，我们现在忽略数组的右半部分并计算新的中间索引：

[ 0, 1, 1, 3, 3, 3 | x, x, x, x, x, x ]
           *

我们再次找到了一个3，这是第一个。 但算法不知道，所以我们再次拆分数组：

[ 0, 1, 1 | x, x, x | x, x, x, x, x, x ]
     *

还没完， 再次拆分，但这次使用右半部分：

[ x, x | 1 | x, x, x | x, x, x, x, x, x ]
         *

数组不能再被拆分，这意味着左边界在索引3处。

现在让我们重新开始，尝试找到右边界。 这非常相似，所以我将向您展示不同的步骤：

[ 0, 1, 1, 3, 3, 3, 3, 6, 8, 10, 11, 11 ]
                    *

[ x, x, x, x, x, x, x | 6, 8, 10, 11, 11 ]
                              *

[ x, x, x, x, x, x, x | 6, 8, | x, x, x ]
                           *

[ x, x, x, x, x, x, x | 6 | x | x, x, x ]
                        *

右边界位于索引7处。两个边界之间的差异是7 - 3 = 4，因此数字3在此数组中出现四次。

每个二分搜索需要4个步骤，所以总共这个算法需要8个步骤。 在仅有12个项的数组上获得的收益不是很大，但是数组越大，该算法的效率就越高。 对于具有1,000,000个项目的排序数组，只需要2 x 20 = 40个步骤来计算任何特定值的出现次数。

顺便说一句，如果你要查找的值不在数组中，那么rightBoundary()和leftBoundary()返回相同的值，因此它们之间的差值为0。

这是一个如何修改基本二分搜索以解决其它算法问题的示例。 当然，它需要先对数组进行排序。

查找最大／最小值(Select Minimum / Maximum)

目标：查找未排序数组中的最大/最小值。

最大值或最小值

我们有一个通用对象数组，我们迭代所有对象，跟踪遇到的最小/最大元素。

例子

假设我们想在未排序列表[8,3,9,4,6]中找到最大值。

选择第一个数字8，并将其存储作为目前为止的最大元素。

从列表中选择下一个数字3，并将其与当前最大值进行比较。 3小于8所以最大值8不会改变。

从列表中选择下一个数字9，并将其与当前最大值进行比较。 9大于8所以我们存储9作为最大值。

重复此过程，直到处理完列表中的所有元素。

代码

在Swift中的一个简单实现：

func minimum<T: Comparable>(_ array: [T]) -> T? {
  guard var minimum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    minimum = element < minimum ? element : minimum
  }
  return minimum
}

func maximum<T: Comparable>(_ array: [T]) -> T? {
  guard var maximum = array.first else {
    return nil
  }

  for element in array.dropFirst() {
    maximum = element > maximum ? element : maximum
  }
  return maximum
}

将代码放在 playground 测试：

let array = [ 8, 3, 9, 4, 6 ]
minimum(array)   // This will return 3
maximum(array)   // This will return 9

Swift的标准库

Swift库已经包含一个叫做SequenceType的扩展，它可返回序列中的最小/最大元素。

let array = [ 8, 3, 9, 4, 6 ]
array.minElement()   // This will return 3
array.maxElement()   // This will return 9

let array = [ 8, 3, 9, 4, 6 ]
//swift3
array.min()   // This will return 3
array.max()   // This will return 9

最大值和最小值

要同时查找数组中包含的最大值和最小值，为了最小化比较次数，我们可以成对比较。

例子

假设我们想要在未排序列表[8,3,9,6,4]中找到最小值和最大值。

选择第一个数字8，并将其存储为目前为止的最小和最大值。

因为我们有一个奇数项目，我们从列表中删除8，留下两队[3,9]和[6,4]。

从列表中选择下一对数字，[3,9]。 在这两个数字中，3是较小的数字，因此我们将3与当前最小值8进行比较，并将9与当前最大值8进行比较。 3小于8，所以新的最小值是3。 9大于8，所以新的最大值是9。

从列表中选择下一对数字，[6,4]。 这里，4是较小的一个，所以我们将4与当前最小3进行比较，并将6与当前最大9进行比较。 4大于3，所以最小值不会改变。 6小于9，因此最大值不会改变。

结果是最小值为3，最大值为9。

代码

在Swift中的一个简单实现：

func minimumMaximum<T: Comparable>(_ array: [T]) -> (minimum: T, maximum: T)? {
  guard var minimum = array.first else {
    return nil
  }
  var maximum = minimum

  // if 'array' has an odd number of items, let 'minimum' or 'maximum' deal with the leftover
  let start = array.count % 2 // 1 if odd, skipping the first element
  for i in stride(from: start, to: array.count, by: 2) {
    let pair = (array[i], array[i+1])

    if pair.0 > pair.1 {
      if pair.0 > maximum {
        maximum = pair.0
      }
      if pair.1 < minimum {
        minimum = pair.1
      }
    } else {
      if pair.1 > maximum {
        maximum = pair.1
      }
      if pair.0 < minimum {
        minimum = pair.0
      }
    }
  }

  return (minimum, maximum)
}

在playground测试：

let result = minimumMaximum(array)!
result.minimum   // This will return 3
result.maximum   // This will return 9

通过成对挑选元素并将其最大值和最小值与当前的最小值和最大值进行比较，我们将每2个元素的比较次数减少到3次。

性能

这些算法以O(n)运行。 将数组中的每个对象与当前的最小值/最大值进行比较，所花费的时间与数组长度成比例。

第k大元素问题(k-th Largest Element Problem)

你有一个整数数组a。 编写一个算法，在数组中找到第k大的元素。

例如，第1个最大元素是数组中出现的最大值。 如果数组具有n个元素，则第n最大元素是最小值。 中位数是第n/2最大元素。

朴素的解决方案

以下是半朴素的解决方案。 它的时间复杂度是 O(nlogn)，因为它首先对数组进行排序，因此也使用额外的 O(n) 空间。

func kthLargest(a: [Int], k: Int) -> Int? {
  let len = a.count
  if k > 0 && k <= len {
    let sorted = a.sorted()
    return sorted[len - k]
  } else {
    return nil
  }
}

kthLargest() 函数有两个参数：由整数组成的数组a，已经整数k。 它返回第k大元素。

让我们看一个例子并运行算法来看看它是如何工作的。 给定k = 4和数组：

[ 7, 92, 23, 9, -1, 0, 11, 6 ]

最初没有找到第k大元素的直接方法，但在对数组进行排序之后，它非常简单。 这是排完序的数组：

[ -1, 0, 6, 7, 9, 11, 23, 92 ]

现在，我们所要做的就是获取索引a.count - k的值：

a[a.count - k] = a[8 - 4] = a[4] = 9

当然，如果你正在寻找第k个最小的元素，你会使用a [k-1]。

更快的解决方案

有一种聪明的算法结合了二分搜索和快速排序的思想来达到O(n)解决方案。

回想一下，二分搜索会一次又一次地将数组分成两半，以便快速缩小您要搜索的值。 这也是我们在这里所做的。

快速排序还会拆分数组。它使用分区将所有较小的值移动到数组的左侧，将所有较大的值移动到右侧。在围绕某个基准进行分区之后，该基准值将已经处于其最终的排序位置。 我们可以在这里利用它。

以下是它的工作原理：我们选择一个随机基准，围绕该基准对数组进行分区，然后像二分搜索一样运行，只在左侧或右侧分区中继续。这一过程重复进行，直到我们找到一个恰好位于第k位置的基准。

让我们再看看初始的例子。 我们正在寻找这个数组中的第4大元素：

[ 7, 92, 23, 9, -1, 0, 11, 6 ]

如果我们寻找第k个最小项，那么算法会更容易理解，所以让我们采用k = 4并寻找第4个最小元素。

请注意，我们不必先对数组进行排序。 我们随机选择其中一个元素作为基准，假设是11，并围绕它分割数组。 我们最终会得到这样的结论：

[ 7, 9, -1, 0, 6, 11, 92, 23 ]
 <------ smaller    larger -->

如您所见，所有小于11的值都在左侧; 所有更大的值都在右边。基准值11现在处于最终排完序的位置。基准的索引是5，因此第4个最小元素肯定位于左侧分区中的某个位置。从现在开始我们可以忽略数组的其余部分：

[ 7, 9, -1, 0, 6, x, x, x ]

再次让我们选择一个随机的枢轴，让我们说6，然后围绕它划分数组。 我们最终会得到这样的结论：

[ -1, 0, 6, 9, 7, x, x, x ]

基准值6在索引2处结束，所以显然第4个最小的项必须在右侧分区中。 我们可以忽略左侧分区：

[ x, x, x, 9, 7, x, x, x ]

我们再次随机选择一个基准值，假设是9，并对数组进行分区：

[ x, x, x, 7, 9, x, x, x ]

基准值9的索引是4，这正是我们正在寻找的 k。 我们完成了！ 注意这只需要几个步骤，我们不必先对数组进行排序。

以下函数实现了这些想法：

public func randomizedSelect<T: Comparable>(_ array: [T], order k: Int) -> T {
  var a = array

  func randomPivot<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int) -> T {
    let pivotIndex = random(min: low, max: high)
    a.swapAt(pivotIndex, high)
    return a[high]
  }

  func randomizedPartition<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int) -> Int {
    let pivot = randomPivot(&a, low, high)
    var i = low
    for j in low..<high {
      if a[j] <= pivot {
        a.swapAt(i, j)
        i += 1
      }
    }
    a.swapAt(i, high)
    return i
  }

  func randomizedSelect<T: Comparable>(_ a: inout [T], _ low: Int, _ high: Int, _ k: Int) -> T {
    if low < high {
      let p = randomizedPartition(&a, low, high)
      if k == p {
        return a[p]
      } else if k < p {
        return randomizedSelect(&a, low, p - 1, k)
      } else {
        return randomizedSelect(&a, p + 1, high, k)
      }
    } else {
      return a[low]
    }
  }

  precondition(a.count > 0)
  return randomizedSelect(&a, 0, a.count - 1, k)
}

为了保持可读性，功能分为三个内部函数：

• randomPivot()选择一个随机数并将其放在当前分区的末尾（这是Lomuto分区方案的要求，有关详细信息，请参阅快速排序上的讨论）。
  

• randomizedPartition()是Lomuto的快速排序分区方案。 完成后，随机选择的基准位于数组中的最终排序位置。它返回基准值的数组索引。
  

• randomizedSelect()做了所有困难的工作。 它首先调用分区函数，然后决定下一步做什么。 如果基准的索引等于我们正在寻找的k元素，我们就完成了。 如果k小于基准索引，它必须回到左分区中，我们将在那里递归再次尝试。 当第k数在右分区中时，同样如此。

很酷，对吧？ 通常，快速排序是一种 O(nlogn) 算法，但由于我们只对数组中较小的部分进行分区，因此randomizedSelect()的运行时间为 O(n)。

注意： 此函数计算数组中第k最小项，其中k从0开始。如果你想要第k最大项，请用a.count - k。

选取样本（Selection Sampling）

目标：从n个项的集合中随机选择k个项。

假设你有一副52张牌，你需要随机抽取10张牌。 这个算法可以让你达成。

这是一个非常快的版本：

func select<T>(from a: [T], count k: Int) -> [T] {
  var a = a
  for i in 0..<k {
    let r = random(min: i, max: a.count - 1)
    if i != r {
      swap(&a[i], &a[r])
    }
  }
  return Array(a[0..<k])
}

正如洗牌算法经常发生的那样，它将数组划分为两个区域。 第一个区域包含所选项; 第二个区域是所有剩余的项。

一个例子。 假设一个数组是：

[ "a", "b", "c", "d", "e", "f", "g" ]

我们想选择3个项目，所以k = 3。 在循环中，i最初为0，因此它指向"a"。

[ "a", "b", "c", "d", "e", "f", "g" ]
   i

我们计算i和数组的大小a.count之间的随机数。 假设这个随机数是4。 现在我们将"a"与索引为4的"e"交换，然后向前移动i：

[ "e" | "b", "c", "d", "a", "f", "g" ]
         i

|栏表示两个区域之间的分割。 "e"是我们选择的第一个元素。 我们继续需要关注|栏右侧的所有内容。

再一次，我们要求i和a.count之间的随机数，但因为i已经移位，随机数永远不会小于1。所以我们再也不会交换"e"了。

假设随机数为6，我们将"b"与"g"交换：

[ "e" , "g" | "c", "d", "a", "f", "b" ]
               i

还有一个随机数，假设它是4。 我们将"c"与"a"交换，最终左边已经选择的项为：

[ "e", "g", "a" | "d", "c", "f", "b" ]

就是这样。 十分简单。 这个函数的性能是O(k)，因为只要我们选择了k元素，就结束了。

下面是一种替代算法，称为“水库抽样”(Reservoir Sampling)：

func reservoirSample<T>(from a: [T], count k: Int) -> [T] {
  precondition(a.count >= k)

  var result = [T]()      // 1
  for i in 0..<k {
    result.append(a[i])
  }

  for i in k..<a.count {  // 2
    let j = random(min: 0, max: i)
    if j < k {
      result[j] = a[i]
    }
  }
  return result
}

有两个步骤：

1. 使用原始数组中的第一个k元素填充result数组。 这被称为“水库”。

2. 用剩余池中的元素随机替换水库中的元素。

该算法的性能为 O(n)，因此它比第一算法慢一点。但是，它的最大优点是它可以用于太大而无法容纳在内存中的数组，即使你不知道数组的大小是多少（在Swift中这可能类似于读取文件元素的懒惰生成器）。

前两种算法有一个缺点：它们不保留原始顺序的元素。在输入数组中，"a"出现在"e"之前，但现在却是另一种顺序。如果要顺序不变，则无法使用上面的方法。

下面这种替代方法，可以保持原始顺序的完整性，但需要更多空间参与：

func select<T>(from a: [T], count requested: Int) -> [T] {
  var examined = 0
  var selected = 0
  var b = [T]()
  
  while selected < requested {                          // 1
    let r = Double(arc4random()) / 0x100000000          // 2
    
    let leftToExamine = a.count - examined              // 3
    let leftToAdd = requested - selected

    if Double(leftToExamine) * r < Double(leftToAdd) {  // 4
      selected += 1
      b.append(a[examined])
    }

    examined += 1
  }
  return b
}

该算法使用概率来决定是否在选择中包括一个数字。

1. 循环从头到尾逐步完成数组。 它一直持续到我们从n的集合中选择k个项。 这里，k是requested而n是a.count。
   

2. 计算0到1之间的随机数。我们想要0.0 <= r < 1.0。 上限是排他性的; 我们从不希望它是1。这就是为什么我们将结果从arc4random()除以0x100000000而不是更常见的0xffffffff。
   

3. leftToExamine是我们还没有看过的项数目。 leftToAdd是我们在完成之前还需要选择的项数。
   

4. 这就是魔术发生的地方。 基本上，我们正在翻转一枚硬币。 如果是heads，我们将当前数组元素添加到选择中; 如果是tails，我们就跳过。

有趣的是，即使我们使用概率，这种方法总是保证我们最终得到输出数组中的k项。

让我们再次讨论相同的例子。 输入数组是：

[ "a", "b", "c", "d", "e", "f", "g" ]

循环依次查看每个元素，因此我们从"a"开始。 我们得到一个介于0和1之间的随机数，假设它是0.841。 // 4处的公式将要检查的项目数乘以此随机数。 还有7个元素需要检查，结果是：

7 * 0.841 = 5.887

我们将此与3进行比较，因为我们想要选择3个项目。 由于5.887大于3，我们跳过"a"并继续移动动"b"。

再一次，我们得到一个随机数，比方说0.212。 现在只剩下6个要检查的元素，因此公式结果是：

6 * 0.212 = 1.272

小于3，我们在选择中添加"b"。 这是我们选择的第一个项，所以还剩下两个。

到下一个元素，"c"。 随机数为0.264，得出结果：

5 * 0.264 = 1.32

只要再选择2个项，因此这个数字必须小于2。它是，我们还在选择中加入"c"。 总选择是["b"，"c"]。

只要再选择1个项，但仍有4个候选项要查看。 假设下一个随机数是0.718。 该公式现在给出：

4 * 0.718 = 2.872

要选择此元素，数字必须小于1，因为只剩下1个项要选择。 2.872不是，所以我们跳过"d"。 只剩下三种可能性 - 我们会在耗尽元素之前选到它吗？

随机数为0.346。 该公式给出：

3 * 0.346 = 1.038

有点太高了。 我们跳过"e"。 只有两名候选项了......

请注意，现在字面上我们正在处理抛硬币：如果随机数小于0.5，我们选择"f"，我们就完成了。 如果它大于0.5，我们继续最后的元素。 假设我们得到0.583：

2 * 0.583 = 1.166

我们跳过"f"并查看最后一个元素。 无论我们在这里得到什么随机数，它应该总是选择"g"或者我们不会选择足够的元素而算法不起作用！

假设我们的最终随机数是0.999（记住，它永远不会是1.0或更高）。 实际上，无论我们在这里选择什么，公式总是会给出小于1的值：

1 * 0.999 = 0.999

因此，如果我们还没有足够多的选择，那么总是会选择最后一个元素。最后的选择是[ "b", "c", "g" ]。请注意，元素仍处于原始顺序，因为我们是从左到右查询数组。

也许你还不相信......如果我们总是将0.999作为随机值（最大可能值），那还能选择3项吗？ 好吧，让我们做数学：

7 * 0.999 = 6.993     小于3吗? no
6 * 0.999 = 5.994     小于3吗? no
5 * 0.999 = 4.995     小于3吗? no
4 * 0.999 = 3.996     小于3吗? no
3 * 0.999 = 2.997     小于3吗? YES
2 * 0.999 = 1.998     小于2吗? YES
1 * 0.999 = 0.999     小于1吗? YES

它总是有效！ 但这是否意味着靠近数组末尾的元素比一开始的元素更有可能被选中？ 不，所有元素同样可能被选中。 （如果不相信我的话：在playground 看一下快速测试，在实践中证明了这一点。）

以下是如何测试此算法的示例：

let input = [
  "there", "once", "was", "a", "man", "from", "nantucket",
  "who", "kept", "all", "of", "his", "cash", "in", "a", "bucket",
  "his", "daughter", "named", "nan",
  "ran", "off", "with", "a", "man",
  "and", "as", "for", "the", "bucket", "nan", "took", "it",
]

let output = select(from: input, count: 10)
print(output)
print(output.count)

第二种算法的性能是O(n)，因为它可能需要遍历整个输入数组。

注意： 如果k > n / 2，那么以相反的方式执行它并选择要删除的a.count - k项更有效。

代码基于发表于1993年10月Dobb博士的杂志的Algorithm Alley。

Union-Find

并查集

Union-Find is a data structure that can keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It is also known as disjoint-set data structure.
并查集是一种数据结构，可以跟踪分成多个不相交（非重叠）子集的一组元素。 它也被称为不相交集数据结构。

What do we mean by this? For example, the Union-Find data structure could be keeping track of the following sets:
这是什么意思呢？ 例如，并查集数据结构可以跟踪以下集合：

[ a, b, f, k ]
[ e ]
[ g, d, c ]
[ i, j ]

These sets are disjoint because they have no members in common.
这些集合是不相交的，因为它们没有共同的成员。

Union-Find supports three basic operations:
并查集支持上个基本操作：

1. Find(A): Determine which subset an element A is in. For example, find(d) would return the subset [ g, d, c ].
   

2. Union(A, B): Join two subsets that contain A and B into a single subset. For example, union(d, j) would combine [ g, d, c ] and [ i, j ] into the larger set [ g, d, c, i, j ].
   

3. AddSet(A): Add a new subset containing just that element A. For example, addSet(h) would add a new set [ h ].
   

4. Find(A)：确定元素A所在的子集。例如，find（d）将返回子集[g，d，c]。
   

5. Union(A, B)：将包含 A 和 B 的两个子集合并为一个子集。 例如，union(d, j) 将 [g, d, c] 和 [i,j] 组合成更大的集合 [g, d, c, i,j]。
   

6. AddSet(A)：添加仅包含该元素的新子集 A。 例如，addSet(h)会添加一个新的集合[h]。

The most common application of this data structure is keeping track of the connected components of an undirected graph. It is also used for implementing an efficient version of Kruskal's algorithm to find the minimum spanning tree of a graph.
该数据结构的最常见应用是跟踪无向图形的连通分量。 它还用于实现Kruskal算法的有效版本，以查找图的最小生成树。

Implementation

实施

Union-Find can be implemented in many ways but we'll look at an efficient and easy to understand implementation: Weighted Quick Union.

PS: Multiple implementations of Union-Find has been included in playground.
并查集可以通过多种方式实现，但我们将看一个高效且易于理解的实现：Weighted Quick Union。
PS：并查集 的多个实现已包含在playground .

public struct UnionFind<T: Hashable> {
  private var index = [T: Int]()
  private var parent = [Int]()
  private var size = [Int]()
}

Our Union-Find data structure is actually a forest where each subset is represented by a tree.
我们的并查集数据结构实际上是一个森林，其中每个子集由tree表示。

For our purposes we only need to keep track of the parent of each tree node, not the node's children. To do this we use the array parent so that parent[i] is the index of node i's parent.
出于我们的目的，我们只需要跟踪每个树节点的父节点，而不是节点的子节点。 为此，我们使用数组parent，以便parent[i]是节点i的父节点的索引。

Example: If parent looks like this,
示例：如果parent看起来像这样，

parent [ 1, 1, 1, 0, 2, 0, 6, 6, 6 ]
     i   0  1  2  3  4  5  6  7  8

then the tree structure looks like:
然后树结构看起来像：

      1              6
    /   \           / \ 
  0       2        7   8
 / \     /
3   5   4

There are two trees in this forest, each of which corresponds to one set of elements. (Note: due to the limitations of ASCII art the trees are shown here as binary trees but that is not necessarily the case.)
这片森林中有两棵树，每棵树对应一组元素。 （注意：由于ASCII艺术的限制，树在这里显示为二叉树，但情况不一定如此。）

We give each subset a unique number to identify it. That number is the index of the root node of that subset's tree. In the example, node 1 is the root of the first tree and 6 is the root of the second tree.
我们为每个子集提供唯一的编号以识别它。 该数字是该子集树的根节点的索引。 在示例中，节点1是第一棵树的根，6是第二棵树的根。

So in this example we have two subsets, the first with the label 1 and the second with the label 6. The Find operation actually returns the set's label, not its contents.
所以在这个例子中我们有两个子集，第一个带有标签1，第二个带有标签6。 Find操作实际上返回了set的标签，而不是其内容。

Note that the parent[] of a root node points to itself. So parent[1] = 1 and parent[6] = 6. That's how we can tell something is a root node.
请注意，根节点的parent []指向自身。 所以parent[1] = 1 和 parent [6] = 6。 这就是我们如何判断一些根节点的方法。

Add set

Let's look at the implementation of these basic operations, starting with adding a new set.
让我们看一下这些基本操作的实现，从开始添加新集。

public mutating func addSetWith(_ element: T) {
  index[element] = parent.count  // 1
  parent.append(parent.count)    // 2
  size.append(1)                 // 3
}

When you add a new element, this actually adds a new subset containing just that element.
添加新元素时，实际上会添加一个仅包含该元素的新子集。

1. We save the index of the new element in the index dictionary. That lets us look up the element quickly later on.
   

2. Then we add that index to the parent array to build a new tree for this set. Here, parent[i] is pointing to itself because the tree that represents the new set contains only one node, which of course is the root of that tree.
   

3. size[i] is the count of nodes in the tree whose root is at index i. For the new set this is 1 because it only contains the one element. We'll be using the size array in the Union operation.
   

4. 我们在index字典中保存新元素的索引。 这让我们可以在以后快速查找元素。
   

5. 然后我们将该索引添加到parent数组中，为该集合构建一个新树。 这里，parent[i]指向自身，因为表示新集合的树只包含一个节点，当然这是该树的根。
   

6. size[i]是树的节点数，其根位于索引i。 对于新集合，这是1，因为它只包含一个元素。 我们将在Union操作中使用size数组。

Find

Often we want to determine whether we already have a set that contains a given element. That's what the Find operation does. In our UnionFind data structure it is called setOf():
通常我们想确定我们是否已经有一个包含给定元素的集合。 这就是Find操作所做的。 在我们的UnionFind数据结构中，它被称为setOf()：

public mutating func setOf(_ element: T) -> Int? {
  if let indexOfElement = index[element] {
    return setByIndex(indexOfElement)
  } else {
    return nil
  }
}

This looks up the element's index in the index dictionary and then uses a helper method to find the set that this element belongs to:
这会在index字典中查找元素的索引，然后使用辅助方法来查找此元素所属的集合：

private mutating func setByIndex(_ index: Int) -> Int {
  if parent[index] == index {  // 1
    return index
  } else {
    parent[index] = setByIndex(parent[index])  // 2
    return parent[index]       // 3
  }
}

Because we're dealing with a tree structure, this is a recursive method.
因为我们正在处理树结构，所以这是一种递归方法。

Recall that each set is represented by a tree and that the index of the root node serves as the number that identifies the set. We're going to find the root node of the tree that the element we're searching for belongs to, and return its index.
回想一下，每个集合由树表示，并且根节点的索引用作标识集合的数字。 我们将找到我们要搜索的元素所属的树的根节点，并返回其索引。

1. First, we check if the given index represents a root node (i.e. a node whose parent points back to the node itself). If so, we're done.
   

2. Otherwise we recursively call this method on the parent of the current node. And then we do a very important thing: we overwrite the parent of the current node with the index of root node, in effect reconnecting the node directly to the root of the tree. The next time we call this method, it will execute faster because the path to the root of the tree is now much shorter. Without that optimization, this method's complexity is O(n) but now in combination with the size optimization (covered in the Union section) it is almost O(1).
   

3. We return the index of the root node as the result.

4. 首先，我们检查给定索引是否代表根节点（即“父”指向节点本身的节点）。 如果是这样，我们就完成了。
   

5. 否则，我们以递归方式在当前节点的父节点上调用此方法。 然后我们做了一个非常重要的事情：我们用根节点的索引覆盖当前节点的父节点，实际上将节点直接重新连接到树的根节点。 下次我们调用此方法时，它将执行得更快，因为树的根路径现在要短得多。 如果没有这种优化，这种方法的复杂性就是O(n)，但现在结合尺寸优化（在Union部分中说明）它几乎是O(1)。
   

6. 我们返回根节点的索引作为结果。

Here's illustration of what I mean. Let's say the tree looks like this:
这是我说明的意思。 让我们说树看起来像这样：

We call setOf(4). To find the root node we have to first go to node 2 and then to node 7. (The indices of the elements are marked in red.)
我们称之为setOf(4)。 要找到根节点，我们必须首先转到节点2然后转到节点7。 （元素的索引标记为红色。）

During the call to setOf(4), the tree is reorganized to look like this:
在调用setOf(4)期间，树被重组为如下所示：

Now if we need to call setOf(4) again, we no longer have to go through node 2 to get to the root. So as you use the Union-Find data structure, it optimizes itself. Pretty cool!
现在如果我们需要再次调用setOf(4)，我们就不再需要通过节点2来到根。 因此，当您使用Union-Find数据结构时，它会优化自身。 太酷了！

There is also a helper method to check that two elements are in the same set:
还有一个帮助方法来检查两个元素是否在同一个集合中：

public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool {
  if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) {
    return firstSet == secondSet
  } else {
    return false
  }
}

Since this calls setOf() it also optimizes the tree.
因为这会调用setOf()它也会优化树。

Union (Weighted)

The final operation is Union, which combines two sets into one larger set.
最后的操作是 Union，它将两组合并为一组更大的组合。

    public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T) {
        if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { // 1
            if firstSet != secondSet {                // 2
                if size[firstSet] < size[secondSet] { // 3
                    parent[firstSet] = secondSet      // 4
                    size[secondSet] += size[firstSet] // 5
                } else {
                    parent[secondSet] = firstSet
                    size[firstSet] += size[secondSet]
                }
            }
        }
    }

Here is how it works:
下面是它的工作原理：

1. We find the sets that each element belongs to. Remember that this gives us two integers: the indices of the root nodes in the parent array.
   

2. Check that the sets are not equal because if they are it makes no sense to union them.
   

3. This is where the size optimization comes in (Weighting). We want to keep the trees as shallow as possible so we always attach the smaller tree to the root of the larger tree. To determine which is the smaller tree we compare trees by their sizes.
   

4. Here we attach the smaller tree to the root of the larger tree.
   

5. Update the size of larger tree because it just had a bunch of nodes added to it.
   

6. 我们找到每个元素所属的集合。 请记住，这给了我们两个整数：parent数组中根节点的索引。
   

7. 检查这些集合是否相等，因为如果它们合并就没有意义。
   

8. 这是尺寸优化的来源（加权）。 我们希望保持树尽可能浅，所以我们总是将较小的树附加到较大树的根部。 为了确定哪个是较小的树，我们按照它们的大小比较树。
   

9. 这里我们将较小的树附加到较大树的根部。
   

10. 更新较大树的大小，因为它只添加了一堆节点。

An illustration may help to better understand this. Let's say we have these two sets, each with its own tree:
插图可能有助于更好地理解这一点。 假设我们有这两组，每组都有自己的树：

Now we call unionSetsContaining(4, and: 3). The smaller tree is attached to the larger one:
现在我们调用 unionSetsContaining(4, and:3)。 较小的树与较大的树相连：

Note that, because we call setOf() at the start of the method, the larger tree was also optimized in the process -- node 3 now hangs directly off the root.
请注意，因为我们在方法的开头调用setOf()，所以在该过程中也对优化的树进行了优化 - 节点3现在直接挂在根之上。

Union with optimizations also takes almost O(1) time.
具有优化的联盟也需要几乎 O(1) 时间。

Path Compression

private mutating func setByIndex(_ index: Int) -> Int {
    if index != parent[index] {
        // Updating parent index while looking up the index of parent.
        parent[index] = setByIndex(parent[index])
    }
    return parent[index]
}

Path Compression helps keep trees very flat, thus find operation could take ALMOST in O(1)
路径压缩有助于保持树非常平坦，因此在 O(1) 中查找操作可能需要 ALMOST

Complexity Summary

To process N objects

To process M union commands on N objects

See also

扩展阅读

See the playground for more examples of how to use this handy data structure.
有关如何使用此便捷数据结构的更多示例，请参阅 playground。

Union-Find at Wikipedia
并查集的维基百科

Written for Swift Algorithm Club by Artur Antonov, modified by Yi Ding.