算法-选择排序

选择排序实现

以下是用kotlin写的选择排序。

让我们来一行行地分析。我会先摘出代码片段，然后给出解释。

这个外层的循环代表每一轮检查。在一轮检查之初，我们会先记住目前的最小值的索引。

因此每轮开始时lowestNumberIndex都会是该轮的起点索引i。注意我们实际上记录的是最小值的索引，而非最小值本身。于是，第1轮开始时最小值的索引是0，到第2轮则是1，以此类推。

此行代码发起一个以i + 1开始的内层循环。

循环内逐个检查数组未排序的格子，若遇到比之前记录的本轮最小值还小的格子值，就将lowestNumberIndex更新为该格子的索引。

内层循环结束时，会得到未排序数值中最小值的索引。

然后再看看这个最小值是否已在正确位置，即该索引是否等于i。如果不是，就将i所指的值与最小值交换。

选择排序效率

选择排序的步骤可分为两类：比较和交换，也就是在每轮检查中把未排序的值跟该轮已遇到的最小值做比较，以及将最小值与该轮起点的值交换以使其位置正确。

在之前5个元素的例子里，我们总共进行了10次比较。每轮分别如下。

于是4 + 3 + 2 + 1=10次比较。

推广开来，若有N个元素，就会有 (N -1) + (N -2) + (N -3) + … + 1次比较。

但每轮的交换最多只有1次。如果该轮的最小值已在正确位置，就无须交换，否则要做1次交换。相比之下，冒泡排序在最坏情况（完全逆序）时，每次比较过后都要进行1次交换。

下表为冒泡排序和选择排序的并列对比。

从表中可以清晰地看到，选择排序的步数大概只有冒泡排序的一半，即选择排序比冒泡排序快一倍。