Day 06：选择排序(selection sort)

先前看到了常见执行时间的图形，线条越平代表演算法速度越快，越陡则代表越慢。

我们会发现O(log n)的二分搜寻其实算是数一数二快速的演算法，不过二分搜寻的条件是只能在有序阵列中施行，这也代表阵列是否有排序有时相当重要，所以也有许多的演算法在解决排序(sorting)的问题。

如果今天有七张盖起来的扑克牌，随意放在桌上，一次只能打开一张检查。要怎麽样让这些牌由小到大排好呢？

最直接的方法，可能就是一张一张找出最小的牌。我们打开最左边第一张，接着依序打开後面的牌跟它比较，如果发现比较小的牌，就交换位置，把较小的牌换到第一张，接这用这张牌继续比较，如下面的例子：

3, 6, 2, 7, 1, 4, 5
// 打开第一张，3即是目前最小的牌。以3依序跟後面的数字比，比到2时发现2较小，把2换到第一个。

2, 6, 3, 7, 1, 4, 5
// 接这用2继续跟7比，再跟1比，发现1较小，把1换到第一个位置。

1, 6, 3, 7, 2, 4, 5
// 接着用1继续跟最後的4和5比，1仍然是最小，留在第一位。

用这样的方式比较完一轮後，可以确定的是最小的牌会在第一个位置，那麽可以说第一个位置已经排序完成，不用再检查或移动了。接着从第二个位置开始，进行跟刚刚一样的比较，全部比完後，第二个位置也排好了，再从第三个位置开始...

1, 2, 6, 7, 3, 4, 5
// 第二轮比完後的状态

1, 2, 3, 7, 6, 4, 5
// 第三轮比完後的状态

像这样比较下来，等於每一轮会排好一个数字，那麽比到最後一轮剩下一个数字时，就会完成排序。

这样的演算法叫做选择排序，它的步骤其实就是不断地从未排序的元素中选出最小(或最大)的，排在排序好的数列末尾，直到所有数字都排序完成。

不过从刚刚的例子中大概也可以感觉得出来，这种直观的演算法速度颇慢。可以把它想成当总共有n个元素，就得比较n轮，每一轮又得全部元素都检查一遍，所以它的执行时间是O(n²)。[注1]

而且选择排序还有一个缺点。因为一次只能检查一个位置，所以任何数列都只能经过每一轮逐一比较，才能知道结果。也就是说，就算你给电脑一个有序阵列，选择排序还是无法加快，无论如何得经过n²次操作，等於执行时间最糟是O(n²)，最佳还是Ω(n²)。

以下是选择排序的动画，红色是当前最小的元素，黄色是已经排序好的元素：

同样是排序，下一回我们会看到思考方式不太一样的泡沫排序演算法。

[注1]严格来说，因为每一轮会排好一个数字，所以每一轮需要检查的元素会减一，总共检查的次数是n+(n-1)+(n-2)+...+1，这个总和是(n²+n)/2，执行时间仍是O(n²)。