Python实现选择排序算法的第二个版本是怎样的？

本文共计1236个文字，预计阅读时间需要5分钟。

选择排序法动态图如下：

选择排序算法思路：

选择排序算法思路就是：1、从第一个元素开始，从剩余未排序元素中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序算法思路就是：1、从第一个元素开始，从剩余未排序元素中找到最小的数，与第一个元素交换；2、从第二个元素开始，从剩余未排序元素中找到最小的数，与第二个元素交换；以此类推，直到最后一个元素。

• 选择排序法动态图如下：
• 选择排序算法的思路：
  选择排序算法的思路就是：
  1、从第一个数开始遍历找到最小的数，然后将最小的数与第一个数交换
  2、从第二个数开始遍历找到最小的数，将此时最小的数与第二个数交换
  3、从第三个数开始遍历找到最下的数，将此事最小的数与第三个数交换
  …
  循环n次之后，即完成了从小到大的排序

代码如下：最坏的情况下

def select_sort(datas):
for i in range(len(datas)):
min_index=i
for j in range(i+1,len(datas)):
if datas[j]<datas[min_index]:
min_index=j
if min_index != i:
datas[min_index],datas[i]=datas[i],datas[min_index]
print(f"经过第 {i+1} 次选择排序后的结果：",datas)
return datas

if __name__=="__main__":
datas=[10,9,8,7,6,5,4,3,2,1,0]
datas=select_sort(datas)

执行结果如下：

经过第 1 次选择排序后的结果： [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
经过第 2 次选择排序后的结果： [0, 1, 8, 7, 6, 5, 4, 3, 2, 9, 10]
经过第 3 次选择排序后的结果： [0, 1, 2, 7, 6, 5, 4, 3, 8, 9, 10]
经过第 4 次选择排序后的结果： [0, 1, 2, 3, 6, 5, 4, 7, 8, 9, 10]
经过第 5 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 6 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 7 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 8 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 9 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 10 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 11 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

最好的情况下：

def select_sort(datas):
for i in range(len(datas)):
min_index=i
for j in range(i+1,len(datas)):
if datas[j]<datas[min_index]:
min_index=j
if min_index != i:
datas[min_index],datas[i]=datas[i],datas[min_index]
print(f"经过第 {i+1} 次选择排序后的结果：",datas)
return datas

if __name__=="__main__":
datas=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
datas=select_sort(datas)

执行结果如下：可以看出，即使已经有序了，选择排序仍然需要一次次去找最小的数，即在最好的情况系，时间复杂度仍然n2

经过第 1 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 2 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 3 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 4 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 5 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 6 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 7 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 8 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 9 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 10 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
经过第 11 次选择排序后的结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]