选择排序(Selection sort)是一种简单直观的排序算法。
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
有无序列表
[3,44,38,5,47,115,36,26,27,2,46,4,19,50,48]
进行选择排序，步骤如下：
-
第一轮从第一个元素开始与下一个元素进行比较，记录较小的元素，再和下下个元素进行比较，记录较小的元素，进行 14 次比较后找到整个列表中的最小数 ls[min]，将它与 ls[0] 交换位置。
-
第二轮第二个元素开始与下一个元素进行比较，记录较小的元素，再和下下个元素进行比较，记录较小的元素，进行 13 次比较后找到从第二个元素开始的列表中的最小数 ls[min]，将它与 ls[1] 交换位置。
-
第三轮…
-
第十四轮第十四个元素开始与下一个元素进行比较，找到最后两个元素中的最小数将它与 ls[1] 交换位置，自此排序完成。
根据上面的步骤归纳总结：
n 个元素的列表，需要 n-1 轮选择排序。每轮选择排序需要的比较次数为 n-1-轮次
02、 代码实现def selection_sort(l):
n = len(l)
for i in range(n - 1): # 进行n-1轮选择排序
min_index = i # 预设最小值索引为未排序部分的第一个数
for j in range(i + 1, n - 1):
if l[min_index] > l[j]:
min_index = j
# 将最小元素放到每次排序的第一个位置
l[i], l[min_index] = l[min_index], l[i]
ls = [3, 44, 38, 5, 47, 115, 36, 26, 27, 2, 46, 4, 19, 50, 48]
selection_sort(ls)
print(ls)
运行结果：
[2, 3, 4, 5, 19, 26, 27, 36, 38, 44, 46, 47, 50, 115, 48]
1. 时间复杂度
-
在选择排序中，其交换操作介于 0（已排序数组）到 n-1（逆序数组）之间，时间复杂度为 O(n)
-
比较操作跟数组的初始状态无关，不论待排序数组是有序的还是逆序的，比较操作的次数都是 n-1+…+3+2+1=n*(n-1)/2，时间复杂度为 O(n2)
2、空间复杂度
- 在选择排序算法过程中，临时占用存储空间大小不变，空间复杂度为 O(1)
3、稳定性分析
- 序列 5，8，5，2，9 经过一遍选择后，第一个元素 5 回合 2 交换，那么原序列中两个 5 的相对前后顺序就破坏了，所以选择排序是一个不稳定的排序。
4、应用分析
- 交换操作所需 CPU 时间比比较所需的 CPU 时间多，当 n 值较小时，选择排序的交换操作远小于冒泡排序，此时应当使用选择排序。
最后：推荐一个软件测试学习交流群：785128166，里面有各类软件测试学习资源，还有大佬为你答疑解惑，如果你不想再体验一次自学时找不到资料，没人解答问题，坚持几天便放弃的感受的话，那就一起加入我们吧~
精彩推荐在职阿里6年，一个29岁女软件测试工程师的心声
拒绝B站邀约，从月薪3k到年薪47W，我的经验值得每一个测试人借鉴
公司新来的阿里p8，看了我做的APP和接口测试，甩给了我这份文档
