[数据结构与算法]【python & 选择排序算法】

1、算法原理

选择排序对冒泡排序进行了改进，保留了其基本的多趟比对思路，每趟都使当前最大项就位。
令但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最大项的所在位置，最后再跟本趟最后一项交换。

原理图示：

2、 简单排序代码示例

'''
@ time ：2021年10月21日
@ author ： wupke
@ description: 使用选择排序算法
'''


import time

# # #    
start1 = time.clock()
def selectionSort(alist:str):
    # 取到列表的最大元素索引值
    for fillslot in range(len(alist)-1,0,-1):
        poaition_Of_Max = 0
        # 进行比较，每一轮比较完，只是记住最大数的索引值，最后再调换位置
        for location in range(1,fillslot+1):
            if alist[location] > alist[poaition_Of_Max]:
                poaition_Of_Max = location
        
        temp = alist[fillslot]
        alist[fillslot] = alist[poaition_Of_Max]
        alist[poaition_Of_Max] = temp

alist = [22,33,44,55,21,31,45,76,88,54,3,5,7,2]
selectionSort(alist)
print(alist)
end1 = time.clock()
print("%s排序用时%s" %(alist,(end1-start1)))

3、复杂度分析

选择排序的时间复杂度比冒泡排序稍优