python实现选择排序 -- 详细思路分析
2020-06-26 本文已影响0人
于饼喵
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号索引的位置
- 遍历完成后，左边排序好的元素便会增加一个次小的元素
第n-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]
