又哭又笑，这份面试宝典要是早遇到就好了

这份面试宝典要是早遇到就好了"/>

又哭又笑，这份面试宝典要是早遇到就好了

01、算法原理

选择排序(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] 交换位置，自此排序完成。

如果你想学习自动化测试，我这边给你推荐一套视频，这个视频可以说是B站播放全网第一的自动化测试教程，同时在线人数到达1000人，并且还有笔记可以领取及各路大神技术交流：798478386 

/?spm_id_from=333.337/?spm_id_from=333.337 

根据上面的步骤归纳总结：

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 ):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, 48,50, 115 ]

03、分析总结

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 值较小时，选择排序的交换操作远小于冒泡排序，此时应当使用选择排序。