1. 选择排序思想
将数组分为左右两部分,左边放置的是有序的元素,右边放置的是无序的元素,每次从无序的部分找出最小的元素放到左边有序的部分。【始终从右边未排序部分选择一个最小的放到左边已排序部分的末尾】
2. 选择排序实现步骤
2-1.第一次遍历
第一次排序- 第一次遍历,假设0号索引位置的元素是最小值【min_index = 0】
- 其他每个元素都与0号索引位置元素对比,如果值比0号索引位置元素小,则将min_index赋值为当前最小元素的索引【如上图min_index从0变为6】,因此游标 i需要从0索引位置走到n-1索引位置。用for循环表示为for i in range(1,n)
- 遍历完成后,交换0号元素和最小值元素的位置。经过第一次遍历后,便可以将数组中最小的元素排在数组0号索引位置
"""第一次遍历代码"""
n = len(target_list)
min_index = 0
for i in range(1,n):
if target_list[min_index] > target_list[i]:
min_index = i
target_list[0],target_list[min_index] = target_list[min_index],target_list[0]
2.2.多次遍历
第二次排序- 第二次遍历,因为0号索引已经排好,所以假设1号索引位置是最小值【min_index = 1】
- 重复上述交换min_value步骤,就可以把第二小的元素放到1号索引的位置
- 遍历完成后,左边排序好的元素便会增加一个次小的元素
- 经过上面的分析可以发现,每遍历一次,起始元素的索引都加1。另一方面,我们只需要确定n-1个数的位置,便可以确定所有元素的位置。【n-1个元素位置确定后,剩下一个位置的元素就可以确定】因此,我们假设起使游标的位置是 j,j只需要走到n-2索引的位置,便可以确定所有元素的位置。range()函数左闭右开,所以可以确定for j in range(0,n-1)
- 对应的,只需要将上面第一次遍历的代码部分的0索引改为j索引即可
def select_sort(target_list):
n = len(target_list)
# # j只需要走到n-2的位置
for j in range(0,n-1):
min_index = j
# i游标需要走完所有从j+1开始所有的索引位置
for i in range(j+1,n):
if target_list[min_index] > target_list[i]:
min_index = i
target_list[j],target_list[min_index] = target_list[min_index],target_list[j]
网友评论