写点什么

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

用户头像
南风以南
关注
发布于: 2020 年 05 月 22 日
python 实现·十大排序算法之选择排序(Selection Sort)

简介


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

算法实现步骤


  1. 初始状态:无序区为,有序区为空;

  2. i趟排序开始时,当前有序区和无序区分别为。该趟排序从当前无序区中-选出关键字最小的记录 ,将它与无序区的第 1 个记录交换,使分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区;

  3. 趟结束,所有元素完成排序。

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 个元素,那么比较次数总是:

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

所以,选择排序的时间复杂度为

  • 空间复杂度

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

  • 稳定性

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

  • 综合评价

联系我们


个人博客网站: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
用户头像

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

评论

发布
暂无评论
python 实现·十大排序算法之选择排序(Selection Sort)