排序算法python版（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]