本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
?andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习?。当然也欢迎加⭐️，?????。
本文的翻译原文和代码可以查看?swift-algorithm-club-cn/Selection Sort
目标：将数组从低到高（或从高到低）排序。
您将获得一系列需要按正确顺序排列的数字。 选择排序算法将数组分为两部分：数组的开头是排序的，数组的其余部分是仍然需要排序的数字。
[ ...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)
复制代码代码逐步说明：
-
如果数组为空或仅包含单个元素，则无需排序。
-
生成数组的副本。 这是必要的，因为我们不能直接在Swift中修改
array参数的内容。 与Swift的sort()函数一样，selectionSort()函数将返回排完序的原始数组拷贝。 -
函数内有两个循环。 外循环依次查看数组中的每个元素; 这就是向前移动
|栏的原因。 -
内循环实现找到数组其余部分中的最小数字。
-
使用当前数组索引数字交换最小数字。
if判断是必要的，因为你不能在Swift中swap()同一个元素。
译注：Swift中的数组没有
swap()方法，只有swapAt()方法，而且swapAt()交换同一个元素是没有问题的。这可能是Swift版本更新的问题。
总结：对于数组的每个元素，选择排序使用数组其余部分中的最小值交换位置。结果，数组从左到右排序。（你也可以从右到左进行，在这种情况下你总是寻找数组中最大的数字。试一试！）
注意： 外循环以索引
a.count - 2结束。 最后一个元素将自动处于正确的位置，因为此时没有剩下其他较小的元素了。
源文件SelectionSort.swift是一个使用泛型的函数版本，因此您也可以使用它来对字符串和其他数据类型进行排序。
性能
选择排序很容易理解，但执行速度慢 O(n^2)。它比插入排序更糟，但优于冒泡排序。查找数组其余部分中的最低元素很慢，特别是因为内部循环将重复执行。
堆排序使用与选择排序相同的原则，但使用了一种快速方法在数组的其余部分中查找最小值。 堆排序性能是 O(nlogn)。