Python版经典排序算法之选择排序
-
选择排序的原理是假定最小的索引是0,然后依次按照索引取出来值,两两比较,比较完之后,把最小的值放到最左边,一轮循环,找到了索引为0的正确的值,依此类推 -- (即每轮循环还得到一个最小的值放在左边)
-
再来对着动图解读一遍原理, 确定 index为0位置的正确元素,过程是始终拿该位置的值和后面的每个值依次比较,（GIF有帧数限制，抽针后有点快，可以看这个链接 https://www.runoob.com/w3cnote/selection-sort.html ）
比到最后一个元素,那此时即确定了该位置的元素.我们实现该过程的代码.
lst = [1,2,3,-1,1,5,9,10] # 以升序举例
min_index = 0 # 确定0位置
for i in range(1,len(lst)): # 那比的时候只需要从0位置后面的元素进行比较即可
if lst[min_index]>lst[i]: # 要升序嘛,所以左边小右边大,否则互换.
lst[min_index],lst[i]=lst[i ]>lst[min_index]
print(lst) # 此时 0 位置找到最小的值
-
那是不是该确定下一个位置index为1的正确值了呢,如果你不辞劳苦可以这么写
lst = [1,2,3,-1,1,5,9,10]
min_index = 0 # 确定0位置正确的元素
for i in range(1,len(lst)): # 那比的时候只需要从0位置后面的位置进行比较即可,即min_index+1
if lst[min_index]>lst[i]: # 要升序嘛,所以左边小右边大,否则互换.
lst[min_index],lst[i]=lst[i ],lst[min_index]
print(lst) # 此时 0 位置找到正确的值
min_index = 1 # 确定1位置正确元素
for i in range(2,len(lst)): # 那比的时候只需要从1位置后面位置的元素进行比较即可即min_index+1
if lst[min_index]>lst[i]: # 要升序嘛,所以左边小右边大,否则互换.
lst[min_index],lst[i]=lst[i ],lst[min_index]
print(lst) # 此时 1 位置找到正确的值 -
依此类推,总共执行N-1轮. N个数,N-1个数都在正确的,那剩余的一个数肯定也会在正确的位置.
循环嵌套的执行顺序是 外层走一个 内层走一圈
lst = [1,2,3,-1,1,5,9,10]
min_index = 0 # 确定0位置正确的元素
for j in range(0,len(lst)): # 依次确定 0 1 2 ..len-1位置的值
for i in range(min_index+1,len(lst)): # 那比的时候只需要从0位置后面的位置进行比较即可,即#min_index+1
if lst[min_index]>lst[i]: # 要升序嘛,所以左边小右边大,否则互换.
lst[min_index],lst[i]=lst[i ],lst[min_index]
min_index+=1 # 内层执行完后代码向下走,确定下一个位置的元素
print(lst) # 此时整个列表即实现了升序 -
总结:比较排序的核心遍历的时候一定要 构造索引 进行取值 ，因为你比完有可能要互换位置 ， 而列表位置的值互换必须牵扯到索引。
那今天讲的选择排序跟冒泡排序有什么区别呢？选择排序每走一轮选一个值在左边，依次从左边排，而冒泡排序每走一轮是放在右边。