python 实现·十大排序算法之选择排序 (Selection Sort)

关注

发布于: 2020 年 05 月 22 日

简介

选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完成。

算法实现步骤

初始状态：无序区为 $R [1, \dots, n]$ ，有序区为空；
第i趟排序 $(i = 1, 2, 3, \dots, n - 1)$ 开始时，当前有序区和无序区分别为 $R [1, \dots, i - 1]$ 和 $R [i, \dots, n]$ 。该趟排序从当前无序区中-选出关键字最小的记录 $R [k]$ ，将它与无序区的第 1 个记录 $R$ 交换，使 $R [1, \dots, i]$ 和 $R [i + 1, \dots, n]$ 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区；
$n - 1$ 趟结束，所有元素完成排序。

Python 代码实现

# selection_sort 代码实现
from typing import List
def selection_sort(arr: List[int]):    """    选择排序    :param arr: 待排序的List    :return: 选择排序是就地排序(in-place)    """    length = len(arr)    if length <= 1:        return
    for i in range(length):        min_index = i        min_val = arr[i]        for j in range(i, length):            if arr[j] < min_val:                min_val = arr[j]                min_index = j        arr[i], arr[min_index] = arr[min_index], arr[i]

复制代码

# 测试数据
if __name__ == '__main__':    import random    random.seed(54)    arr = [random.randint(0,100) for _ in range(10)]    print("原始数据：", arr)    selection_sort(arr)    print("选择排序结果：", arr)

复制代码

# 输出结果
原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]选择排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

复制代码

动画演示

选择排序动画演示

算法分析

时间复杂度

选择排序的比较次数与序列的初始排序无关。假设待排序的系列有 n 个元素，那么比较次数总是：

\frac{n ( n - 1 )}{2}

而移动次数与初始排序状态有关，当初始为顺序时，移动次数最少为 0。当初始为逆序时，移动次数最多为：

\frac{3 n ( n - 1 )}{2}

所以，选择排序的时间复杂度为 $O (n^{2})$ 。

空间复杂度

空间复杂度就是在交换元素时那个临时变量所占的内存空间。平均的空间复杂度为： $O (1)$ ;

稳定性

排序过程中，相等元素的位置前后关系会发生任何变化，所以算法是不稳定的。

综合评价

联系我们

个人博客网站：http://www.bling2.cn/

Github 地址：https://github.com/lb971216008/Use-Python-to-Achieve

知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve

小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve

博客园：https://www.cnblogs.com/Use-Python-to-Achieve

发布于: 2020 年 05 月 22 日阅读数: 76

原文链接:【http://xie.infoq.cn/article/743f550d61896d168699d5811】。

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

发布

暂无评论

创作场景

python 实现·十大排序算法之选择排序 (Selection Sort)

简介

算法实现步骤

Python 代码实现

动画演示

算法分析

联系我们

南风以南

评论