选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,
然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
'''
#第一步:预定义列表的第一个元素是最小值,坐标为0
#第二:循环这个列表比较预最小值与每个元素的大小
#第三:当预最小值大于某个元素时,最小值的坐标改变,交换这两个元素的位置,让最小值在最前面
 
 算法思路:
第一步:在列表的第一个位置存放此队列的最小值
声明一个变量min_index等于列表的第一个坐标值0
从第一个位置0坐标开始,和它后边所有的元素一一比对,如果发生了后边的值min_index坐标的对应的值更小,则min_index值改为后边那个数的坐标,然后用min_index坐标对应的值再跟后边的数比较,完成全部比对以后,将列表的第一个数和min_index坐标对应的数做 
一个交换
第一次用3和5比较,3小,min_index不变,用3和后边的2比,2小,min_index改为2,用2跟1比,1小,min_index改为3,用1跟7比较,1小,min_index不变,用1和4比较,1小,min_index不变,比完了,把坐标2对应的值和第一个值交换
min_index=2
a=[3,5,2,1,7,4],最小的1放到最前边,
第二步:从坐标1开始,把刚才的逻辑再来一遍:
a=[2,5,3,1,7,4]
第三步:从坐标2开始,把刚才的逻辑再来一遍
a=[1,5,3,2,7,4]
第四步:从坐标3开始,把刚才的逻辑再来一遍
a=[1,5,3,2,7,4]
第五步:从坐标4开始,把刚才的逻辑再来一遍
a=[1,5,3,2,7,4]

a=[3,5,2,1,7,4]

分析:
'''

预定义3为最小的元素,坐标为min_index=0

#找到最小元素,放到列表的起始位置
[3,5,2,1,7,4]   ----->>从第一个元素和第二个元素开始比较,3<5,位置不变
[2,5,3,1,7,4]   ----->>比较第一个元素和第三个元素,3和2比较,3>2,坐标位置交换
[1,5,3,2,7,4]   ----->>比较一个元素和第四个元素,2和1比较,2>1,交换位置
[1,5,3,2,7,4]   ----->>比较第一个元素和第五个元素,1和7比较,1<7,坐标位置交换
[1,5,3,2,7,4]   ----->>比较第一个元素和第六个元素,1和4比较,1<4,坐标位置交换-------->>找到了最小的元素

#找到第二小元素,因为最小元素已经找到了,所以1在本次比较中可以剔除,从第二个元素开始,以此类推。。。

[1,5,3,2,7,4]
[1,3,5,2,7,4]
[1,2,5,3,7,4]
[1,2,5,3,7,4]
[1,2,5,3,7,4]

[1,2,5,3,7,4]
[1,2,3,5,7,4]
[1,2,3,5,7,4]
[1,2,3,5,7,4]

[1,2,3,5,7,4]
[1,2,3,5,7,4]
[1,2,3,4,7,5]

[1,2,3,4,7,5]
[1,2,3,4,5,7]


'''

#找到并交换某一个元素的排序
min = a[0]
min_index =0
for j in range(1,len(a)):
    if a[min_index] >a[j]:  #当预设最小值大于某个值时,记录实际最小的坐标,然后交换两个值的位置
        min_index = j
        a[0],a[min_index] = a[min_index],a[0]
    print(a)


print("*****")
print(a)

E:>py -3 a.py
[3, 5, 2, 1, 7, 4]
[2, 5, 3, 1, 7, 4]
[1, 5, 3, 2, 7, 4]
[1, 5, 3, 2, 7, 4]
[1, 5, 3, 2, 7, 4]
*****
[1, 5, 3, 2, 7, 4]

#整个流程:

for i in range(len(a)):
    min = a[i] #记录当前最小值
    min_index = i  #记录最小值的坐标
    for j in range(i+1,len(a)):
        if a[j]<min:  #当我遇到更小的,比较的基准变为了更小的值
            min = a[j]
            min_index = j  #并且把坐标记录下来
    #能否找到最小值和它所在的坐标?
    a[i],a[min_index]=a[min_index],a[i] #是不是实现了将最小值放到第一个位置

print(a)

E:>py -3 a.py
[1, 2, 3, 4, 5, 7]

选择排序的时间复杂度 n * log n,速度比二分查找要慢
比如有4个元素的列表,时间复杂度位4*log4 = 4*2 = 8
每次在当前列表查找最小元素,需要查找4轮
原文地址:https://www.cnblogs.com/wenm1128/p/11771554.html