选择排序

发表于 | 分类于

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置/末尾位置，再从剩余未排序元素中继续寻找最小（或最大）元素，以此类推，直到所有元素均排序完毕。

算法描述

具体算法描述如下：

  1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置（或末尾位置）。
  2. 再从剩余未排序元素中继续寻找最小（或最大）元素，重复第一步。
  3. 以此类推，直到所有元素均排序完毕。

以列表 [54, 26, 93, 17, 77, 31, 44, 55, 20] 为例，选择排序的示例图如下：

  • 前 9 个数字中的最大值 93 在第 3 位，与第 9 位（即最后一位）交换。
  • 前 8 个数字中的最大值 77 在第 5 位，与第 8 位交换。
    …
  • 前 2 个数字中的最大值 20 在第 1 位，与第 2 位交换。
  • 排序完成。

Python 实现

算法的 Python 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(var):
    for index in range(len(var) - 1, 0, -1):
        pos_of_max = 0
        for pos in range(1, index + 1):
            if var[pos] > var[pos_of_max]:
                pos_of_max = pos
        var[pos_of_max], var[index] = var[index], var[pos_of_max]


a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a)
print(a)  # output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 平均时间复杂度：$O(n^2)$
  • 最坏时间复杂度：$O(n^2)$