本文是对 翻译的一篇文章。

是 网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。

?是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习?。当然也欢迎加⭐️，?????。

本文的翻译原文和代码可以查看?

目标：将数组从低到高（或从高到低）排序。

您将获得一系列需要按正确顺序排列的数字。 选择排序算法将数组分为两部分：数组的开头是排序的，数组的其余部分是仍然需要排序的数字。

[ ...sorted numbers... | ...unsorted numbers... ]复制代码

这类似于，但区别在于如何将新数字添加到已排序部分。

它的工作原理如下：

• 找到数组中的最小数字。 从索引0开始，遍历数组中的所有数字，并追踪最小数字的位置。
• 使用索引0处的数字交换最小数字。现在，已排序部分仅包含索引0处的数字。
• 转到索引1处。
• 找到数组其余部分中的最小数字。 从索引1开始查看。再次循环直到数组结束并追踪最小数字。
• 使用索引1处的数字交换最小数字。现在，已排序部分包含两个数字，索引0和索引1。
• 转到索引2处。
• 从索引2开始，找到数组其余部分中的最小数字，并将其与索引2处的数字交换。现在，数组从索引0到2已排序; 此范围包含数组中的三个最小数字。
• 并继续，直到没有数字需要排序。

这种排序方式之所以被称为“选择”排序，是因为在每个步骤中，都是在数组的其余部分里搜索选择下一个最小数字。

例子

假设要排序的数字是[5,8,3,4,6]。 用|符号表示数组的已排序部分的结束位置(讲述插入排序时也是如此表示的)。

最初，排序部分为空：

[| 5, 8, 3, 4, 6 ]复制代码

现在我们找到数组中的最小数字。 从|栏开始向右扫描数组，找到数字3。

要将此数字放入已排序的位置，将它与|旁边的数字5交换（然后把|向右移动一位）：

[ 3 | 8, 5, 4, 6 ]  *      *复制代码

排序部分现在是[3]，其余部分是[8,5,4,6]。

再一次，我们从|栏开始寻找最低的数字。 我们找到4并用8与之交换得到（同样把|向右移动一位）：

[ 3, 4 | 5, 8, 6 ]     *      *复制代码

每一步，|栏都会向右移动一个位置。 我们再次查看数组的其余部分，找到5是最小数字。 没有必要与自己交换，只需|栏前进：

[ 3, 4, 5 | 8, 6 ]        *复制代码

重复此过程，直到数组都排序了。 请注意，|栏左侧的所有内容始终按排序顺序排列，并且始终包含数组中的最小数字。 最后，我们最终得到：

[ 3, 4, 5, 6, 8 |]复制代码

选择排序是原地排序，因为所有内容都发生在同一个数组中而不使用额外的内存。您也可以将其实现为 稳定排序，以便相同的元素不会相互交换（请注意，下面给出的版本不稳定）。

代码

这是Swift中选择排序的一个实现：

func selectionSort(_ array: [Int]) -> [Int] {  guard array.count > 1 else { return array }  // 1  var a = array                    // 2  for x in 0 ..< a.count - 1 {     // 3    var lowest = x    for y in x + 1 ..< a.count {   // 4      if a[y] < a[lowest] {        lowest = y      }    }    if x != lowest {               // 5      a.swapAt(x, lowest)    }  }  return a}复制代码

将此代码放在 playground 测试：

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]selectionSort(list)复制代码

代码逐步说明：

1. 如果数组为空或仅包含单个元素，则无需排序。

2. 生成数组的副本。 这是必要的，因为我们不能直接在Swift中修改array参数的内容。 与Swift的sort()函数一样，selectionSort()函数将返回排完序的原始数组拷贝。

3. 函数内有两个循环。 外循环依次查看数组中的每个元素; 这就是向前移动|栏的原因。

4. 内循环实现找到数组其余部分中的最小数字。

5. 使用当前数组索引数字交换最小数字。 if判断是必要的，因为你不能在Swift中swap()同一个元素。

译注：Swift中的数组没有swap()方法，只有swapAt()方法，而且swapAt()交换同一个元素是没有问题的。这可能是Swift版本更新的问题。

总结：对于数组的每个元素，选择排序使用数组其余部分中的最小值交换位置。结果，数组从左到右排序。（你也可以从右到左进行，在这种情况下你总是寻找数组中最大的数字。试一试！）

注意： 外循环以索引a.count - 2结束。 最后一个元素将自动处于正确的位置，因为此时没有剩下其他较小的元素了。

源文件是一个使用泛型的函数版本，因此您也可以使用它来对字符串和其他数据类型进行排序。

性能

选择排序很容易理解，但执行速度慢 O(n^2)。它比更糟，但优于。查找数组其余部分中的最低元素很慢，特别是因为内部循环将重复执行。

使用与选择排序相同的原则，但使用了一种快速方法在数组的其余部分中查找最小值。 堆排序性能是 O(nlogn)。

扩展阅读

作者：Matthijs Hollemans