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

作者: 于饼喵 | 来源:发表于2020-06-26 20:24 被阅读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]
    

    相关文章

      网友评论

        本文标题:python实现选择排序 -- 详细思路分析

        本文链接:https://www.haomeiwen.com/subject/zwqufktx.html