声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
目标：将一个数组按从小到大或从大到小的顺序排序好。
当我们得到一个数组，然后需要将数组内容按照一定顺序排序好，选择排序算法可以将该数组分成两部分，一边是排序好的部分，另一边是还没排序好的部分。
[ ...已排序数字... | ...未排序数字... ]
这一部分与插值排序算法类似，而不同之处是如何将新的数字放到已排序的部分。
选择排序算法具体流程如下：
1.从index=0开始，遍历整个数组，找到数组中的最小值
2.将最小值与index=0的数字交换位置。现在，在已排序部分中只包含了index=0的数字
3.从index=1开始，遍历剩余整个数组，找到数组中的最小值
4.将最小值与index=1的数字交换位置。现在，在已排序部分中包含了index为0，1的两个数字
5.从index=2开始，遍历剩余整个数组，找到最小值并与index=2的数字交换位置。
6.重复上述过程直到完成数组排序。
这里的选择排序算法中的选择，指的就是每个步骤中，从未排序数组中选择出最小值这个过程。
例子
假设我们需要整理数组[ 5, 8, 3, 4, 6 ]。我们用|区分已排序和未排序部分。
在最开始阶段，已排序数组为空，如下：
[| 5, 8, 3, 4, 6 ]
我们开始寻找此时数组中的最小值。从左到右，最小值为3，将3与index=0的5交换位置，并移动|得到已排序部分，如下：
[ 3 | 8, 5, 4, 6 ]
* *
此时已排序部分为[3]，未排序部分为[8, 5, 4, 6]. 我们从|右侧开始重新寻找最小值，得到4并与index=1的8交换位置，同时移动|，如下：
[ 3, 4 | 5, 8, 6 ]
* *
此时已排序部分为[3,4]，未排序部分为[5, 8, 6]. 我们从|右侧开始重新寻找最小值，得到5，同时移动|，如下：
[ 3, 4, 5 | 8, 6 ]
*
重复上述过程直到整个数组整理完毕。我们得到：
[ 3, 4, 5, 6, 8 |]
总体来说，选择排序是一种就地排序，因为整个过程都发生在同一个数组内，没有用到更多的内存。
代码
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
swap(&a[x], &a[lowest])
}
}
return a
}
在playgroun中测试:
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)
每一行代码解释：
1.如果数组为空，或者只有一个数字，无需整理，直接返回
2.拷贝一份数组。这是一个必要过程，因为我们无法在swift里直接修改array参数。与swift提供的sort()函数相同，selectionSort()函数也会返回一个通过原数组整理好的数组备份
3.这里一共有两个循环。外循环按顺序遍历整个数组，其对应的x就是|的位置
4.内循环，用来寻找未排序数组中的最小值
5.判断寻找到的最小值是否刚好在调整位置上，如果是，则直接进行下一个位置的最小值寻找，否则交换位置。注意，加位置判断是因为swift中swap()函数不能交换元素自己本身。
总结：对于数组中的每个元素，选择算法均从未排序部分中寻找到最小值并交换到已排序部分的最右端，所以得到的数组顺序是从小到大。当然我们可以根据需要修改为从大到小。当然，我们也可以修改数据类型，对其他数据，如字符进行排序。
性能分析
选择排序算法十分简单易懂，但是它的效率比较低，是O(n^2)。它比插值排序更低效但比冒泡排序更高效。在未排序数组中寻找最小值的过程很慢，而这个过程又是不断被重复的。
值得一提的是，堆排序算法的原理与选择排序相同，但是它在寻找最小值的速度上快于选择排序，它的性能是O(n log n)。 接下来我们会提到。
网友评论