使用python实现排序算法(Selection Sort)

选择排序(Selection sort)是一种简单直观的排序算法。选择排序算法通过不断地寻找未排序列表中的最小值,并将寻找到的最小值按顺序存放到排序列表中完成对所有元素的排序。

selection-sort

算法描述:

选择排序算法简单直观,具体步骤及描述如下:

1,在未排序的列表中选择一个数字,与列表中的所有数字进行逐一对比。
2,如果选择的数字大于列表中的数字,则将选择的数字替换为列表中较小的数字。
3,继续用替换后的数字与列表中的数字比较,直到对比完未排序列表中的所有数字。
4,将找到的最小数字从未排序列表中移除,并放入已排序列表中。
5,重复第一步到第四步,直到未排序列表中没有数字。

1

算法实现:

#导入随机数库
import random
#生成10个1-100之间的随机数
list=random.sample(range(1, 100), 10)

 

#查看生成的10个随机数
list
[99, 48, 33, 31, 36, 30, 23, 88, 73, 32]

 

def selection_sort(list):
    #把list赋值给unsorted用于排序操作
    unsorted=list[:]
    #如果数据序列中只有一个数字,则不进行排序,直接返回数据序列
    if len(unsorted)==1: 
        return print("list只有一个数字",unsorted)
    else:
        print("原始list:",unsorted)
        #创建新list用于存放排序后的数据
        sorted=[]
        #循环对比,直到list中没有数字
        while len(unsorted) > 0:
            #挑选list中的每个数字用于对比
            for index,value  in enumerate(unsorted):
                print("固定对比的位置:",index,"数值:",value)
                #顺序输出列表中的数字与前面挑选的数字进行对比
                for position, value_1 in enumerate(unsorted):
                    print("循环对比的位置:",position, "数值:",value_1)
                    #如果第一次挑选出的数据大于从列表中的数字
                    if unsorted[index] > unsorted[position]:
                        print("是否发现更小的数字",unsorted[index] > unsorted[position])
                        print("原位置",index,"原数值",value)
                        #交换这两个数字,用较小的数字继续对比
                        index,position=position,index
                        print("更新为新位置",index,"新数值",value_1)
                #将本次对比中较小的数字从未排序列表中移除,并赋值给smallest_num
                smallest_num=unsorted.pop(index)
                #将smallest_num添加到sorted的list中
                sorted.append(smallest_num)    
                print("本轮挑选的最小值是:",smallest_num)
                print("本次排序结果",sorted,"\n")

 

 

selection_sort(list)

 

原始list: [99, 48, 33, 31, 36, 30, 23, 88, 73, 32]
固定对比的位置: 0 数值: 99
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
是否发现更小的数字 True
原位置 0 原数值 99
更新为新位置 1 新数值 48
循环对比的位置: 2 数值: 33
是否发现更小的数字 True
原位置 1 原数值 99
更新为新位置 2 新数值 33
循环对比的位置: 3 数值: 31
是否发现更小的数字 True
原位置 2 原数值 99
更新为新位置 3 新数值 31
循环对比的位置: 4 数值: 36
循环对比的位置: 5 数值: 30
是否发现更小的数字 True
原位置 3 原数值 99
更新为新位置 5 新数值 30
循环对比的位置: 6 数值: 23
是否发现更小的数字 True
原位置 5 原数值 99
更新为新位置 6 新数值 23
循环对比的位置: 7 数值: 88
循环对比的位置: 8 数值: 73
循环对比的位置: 9 数值: 32
本轮挑选的最小值是: 23
本次排序结果 [23]

固定对比的位置: 1 数值: 48
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
循环对比的位置: 2 数值: 33
是否发现更小的数字 True
原位置 1 原数值 48
更新为新位置 2 新数值 33
循环对比的位置: 3 数值: 31
是否发现更小的数字 True
原位置 2 原数值 48
更新为新位置 3 新数值 31
循环对比的位置: 4 数值: 36
循环对比的位置: 5 数值: 30
是否发现更小的数字 True
原位置 3 原数值 48
更新为新位置 5 新数值 30
循环对比的位置: 6 数值: 88
循环对比的位置: 7 数值: 73
循环对比的位置: 8 数值: 32
本轮挑选的最小值是: 30
本次排序结果 [23, 30]

固定对比的位置: 2 数值: 33
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
循环对比的位置: 2 数值: 33
循环对比的位置: 3 数值: 31
是否发现更小的数字 True
原位置 2 原数值 33
更新为新位置 3 新数值 31
循环对比的位置: 4 数值: 36
循环对比的位置: 5 数值: 88
循环对比的位置: 6 数值: 73
循环对比的位置: 7 数值: 32
本轮挑选的最小值是: 31
本次排序结果 [23, 30, 31]

固定对比的位置: 3 数值: 36
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
循环对比的位置: 2 数值: 33
是否发现更小的数字 True
原位置 3 原数值 36
更新为新位置 2 新数值 33
循环对比的位置: 3 数值: 36
循环对比的位置: 4 数值: 88
循环对比的位置: 5 数值: 73
循环对比的位置: 6 数值: 32
是否发现更小的数字 True
原位置 2 原数值 36
更新为新位置 6 新数值 32
本轮挑选的最小值是: 32
本次排序结果 [23, 30, 31, 32]

固定对比的位置: 4 数值: 88
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
是否发现更小的数字 True
原位置 4 原数值 88
更新为新位置 1 新数值 48
循环对比的位置: 2 数值: 33
是否发现更小的数字 True
原位置 1 原数值 88
更新为新位置 2 新数值 33
循环对比的位置: 3 数值: 36
循环对比的位置: 4 数值: 88
循环对比的位置: 5 数值: 73
本轮挑选的最小值是: 33
本次排序结果 [23, 30, 31, 32, 33]

固定对比的位置: 0 数值: 99
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
是否发现更小的数字 True
原位置 0 原数值 99
更新为新位置 1 新数值 48
循环对比的位置: 2 数值: 36
是否发现更小的数字 True
原位置 1 原数值 99
更新为新位置 2 新数值 36
循环对比的位置: 3 数值: 88
循环对比的位置: 4 数值: 73
本轮挑选的最小值是: 36
本次排序结果 [23, 30, 31, 32, 33, 36]

固定对比的位置: 1 数值: 48
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 48
循环对比的位置: 2 数值: 88
循环对比的位置: 3 数值: 73
本轮挑选的最小值是: 48
本次排序结果 [23, 30, 31, 32, 33, 36, 48]

固定对比的位置: 2 数值: 73
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 88
循环对比的位置: 2 数值: 73
本轮挑选的最小值是: 73
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73]

固定对比的位置: 0 数值: 99
循环对比的位置: 0 数值: 99
循环对比的位置: 1 数值: 88
是否发现更小的数字 True
原位置 0 原数值 99
更新为新位置 1 新数值 88
本轮挑选的最小值是: 88
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73, 88]

固定对比的位置: 0 数值: 99
循环对比的位置: 0 数值: 99
本轮挑选的最小值是: 99
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73, 88, 99]

def selection_sort(list):
    unsorted=list[:]
    if len(unsorted)==1: 
        return print("list只有一个数字",unsorted)
    else:
        print("原始list:",unsorted)
        sorted=[]
        while len(unsorted) > 0:
            for index, _ in enumerate(unsorted):
                for position, _ in enumerate(unsorted):
                    if unsorted[index] > unsorted[position]:
                        index,position=position,index
                smallest_num=unsorted.pop(index)
                sorted.append(smallest_num)    
                print("本次排序结果",sorted)

 

selection_sort(list)

 

原始list: [99, 48, 33, 31, 36, 30, 23, 88, 73, 32]
本次排序结果 [23]
本次排序结果 [23, 30]
本次排序结果 [23, 30, 31]
本次排序结果 [23, 30, 31, 32]
本次排序结果 [23, 30, 31, 32, 33]
本次排序结果 [23, 30, 31, 32, 33, 36]
本次排序结果 [23, 30, 31, 32, 33, 36, 48]
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73]
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73, 88]
本次排序结果 [23, 30, 31, 32, 33, 36, 48, 73, 88, 99]

—【所有文章及图片版权归 蓝鲸(王彦平)所有。欢迎转载,但请注明转自“蓝鲸网站分析博客”。】—

Speak Your Mind

*