排序算法（二）：选择排序

2018-08-11 本文已影响22人 zhipingChen

选择排序算法维护一个待排序集合和一个已排序集合，每轮迭代，从待排序集合中选择一个最小（最大）元素，添加到已排序集合中，通过多次迭代，最终完成排序。

选择排序与上一章的冒泡排序很相似，两者都维护了待排序集合和已排序集合，每次迭代结束都会产生一个已排序元素。不同之处在于冒泡排序的极值元素是通过不断的比较和交换位置产生的，选择排序则是不断比较和一次交换位置产生，所以相对冒泡排序，性能上具有优势。

算法过程

以递增排序为例，初始集合即为待排序集合，已排序集合初始为空

声明变量 $index$ 并指定初始值为待排序集合第一个元素的下标，通过遍历待排序集合，比较并更新 $index$ ，若 $index$ 指向不为待排序集合最后一个元素，则交换 $index$ 指向的值和待排序集合最后一个元素；
标记待排序集合最后一个元素为已排序；
重复步骤 1,2，直到待排序集合只有一个元素

演示示例

初始状态：0 次排序
待排序集合：[6,3,4,0,2,1,8,5,9,7]
已排序集合：[]

初始状态为：

根据算法过程：

步骤一， $index$ 初始值设为 0，指向元素 6，从下标为 1 的元素开始，比较 $index$ 指向的值和 3，比较大小后，选择下一个元素，比较 $index$ 指向的值和 4，比较大小，直到选择 8，比较大小并更新 $index$ 值为 6，即元素 8 的下标，依次遍历比较待排序集合后，若 $index$ 值不为待排序集合的尾元素下标，则交换 $index$ 指向的值和待排序集合的尾元素；
步骤二，标记待排序集合中的最后一个元素为已排序，从待排序集合中移除该元素

1 次排序后
待排序集合：[6, 3, 4, 0, 2, 1, 8, 5, 7]
已排序集合：[9]

根据算法过程步骤三，待排序集合中不止一个元素，所以重复执行步骤一、二：

步骤一， $index$ 初始值设为 0，指向元素 6，从下标为 1 的元素开始，比较 $index$ 指向的值和 3，比较大小后，选择下一个元素，比较 $index$ 指向的值和 4，比较大小，直到选择 8，比较大小并更新 $index$ 值为 6，即元素 8 的下标，依次遍历比较待排序集合后，若 $index$ 值不为待排序集合的尾元素下标，则交换 $index$ 指向的值和待排序集合的尾元素；
步骤二，标记待排序集合中的最后一个元素为已排序，从待排序集合中移除该元素

2 次排序后
待排序集合：[6, 3, 4, 0, 2, 1, 7, 5]
已排序集合：[8, 9]

...
...
...

9 次排序后
待排序集合：[0]
已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]

观察以上过程可知，每次排序后会有一个元素变为已排序，即有一个元素处于正确的位置上。所以 $N$ 个元素的序列，经过 $N-1$ 次排序后，则有 $N−1$ 个元素处于已排序状态，则剩下的一个元素不再需要进行排序。

算法示例

def selectionSort(arr):
    for i in range(1, len(arr)):  # 迭代次数
        index = 0
        for j in range(1, len(arr) - i + 1):  # 遍历比较待排序集合中的元素
            if arr[index] < arr[j]:
                index = j
        if not index == j:
            arr[index],arr[j] = arr[j],arr[index]

代码分析：

以上代码中，第一层循环为需要进行的迭代次数，元素个数为 $N$ 的集合，最多需要 $N-1$ 次迭代即可确定 $N-1$ 个元素的位置，即完成排序；
第二层循环为比较元素值更新 $index$ 指向位置的操作，随着迭代次数的增加，待排序元素个数减少；
每一次循环后，判断 $index$ 指向的是否为待排序集合最后一个元素，若不是则交换元素值。

算法分析

在每一轮排序过程中，选择出极值后，是通过直接交换元素位置的方式生成已排序元素的，所以选择排序是一种非稳定排序。对于 $N$ 个元素的序列，需要进行 $N-1$ 次迭代才能完成排序，每一次都需要遍历比较待排序集中所有元素来确定极值位置，即第 $i$ 次迭代，遍历的元素个数为 $N-i$ 。所以算法的比较复杂度为 $O(n^2)$ ，交换复杂度为 $O(n)$ 。