python实现选择排序 -- 详细思路分析

---

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]