选择排序算法

Selection Sort

Posted by BlueFat on Thursday, August 11, 2022
  • 每次找到最小元素索引
  • 交换两个索引位置
  • 重复前面的步骤,直到排序完成
def selectSort(nums):
    length=len(nums)
    for i in range(length-1):
        min_idx=i # 假定i为最小值
        for j in range(i+1,length): # 第二位与前一位对比
            if nums[j] < nums[min_idx]:
                min_idx=j #得到最小值索引

        if i !=min_idx:
            #交换索引位置,继续下一轮for i循环
            nums[i],nums[min_idx]=nums[min_idx],nums[i]
        print(nums)

test=[9,3,7,1,6]
print("原:",test)
selectSort(test)

原: [9, 3, 7, 1, 6]
[1, 3, 7, 9, 6]
[1, 3, 7, 9, 6]
[1, 3, 6, 9, 7]
[1, 3, 6, 7, 9]
  • 假定索引max_index=0为最大值
  • for j 每轮与max_index对比,若大于max_index则更新(此时只更新max_index索引)
  • for i 每轮交换索引位置(只交换两个,其他不动)
num=[1,5,8,9]
length=len(num)

for i in range(length-1):
    max_index=i
    # 找出此次最大值,交换索引
    for j in range(i+1,length):
        if num[j] > num[max_index]:
            max_index=j
    if i != max_index:
        #交换两个值,其他保持不动
        num[i],num[max_index]=num[max_index],num[i]
    print(num)
    
原: [1, 5, 8, 9]
[9, 5, 8, 1]   # 第一轮max_index=9, 交换1与9位置
[9, 8, 5, 1]   # 第二轮max_index=8, 交换5与8位置
[9, 8, 5, 1]   # 第二轮max_index=5, 小于保持不动