排序算法之插入排序Python

2020-10-23 11:36发布

介绍一种新的排序算法,插入排序。先想想一下在玩扑克牌时的动作,当刚开始发完牌时,每个人都需要整理手中的牌,那么我们排序时,就需要从乱序中的牌中拿出一张牌,将这张牌和已经排好序的牌进行比较,从而放到正确的位置。以此类推,直到排好所有的牌。
比如,手中有5张牌,无序。首先从这五张牌中随便拿出一张,因为最开始都没有序,所以就直接放(当然实际情况是把最左边的一张牌当做有序的,从四张牌中随便选出一张进行比较)。然后从四张牌中随便拿出一张,和已经排好序的一张牌进行比较,从而形成两张牌的有序列。之后再从三张牌中随便选取一张,和有序的两张牌进行比较排序。以此类推。

这是我写的代码。外循环的下标相当于是每次的有序列表(排好序)的最大下标,逐步增加一个。

def insert_sort(alist):

    for i in range(len(alist) - 1):

        temp = alist[i+1]
        for j in range(i, -1, -1):
            if alist[j] >= temp:
                alist[j+1] = alist[j]

            # 找到小于当前元素的位置,退出循环
            else:
                alist[j+1] = temp
                break
        # 循环正常结束,即已排好序的子集中都比当前元素大,所以需要最后加一步替换。
        else:
            alist[j] = temp
        # print(alist)

# alist = [2,7,5,84,10,1,3]
# alist = [1,1,2,1,3,5,4,2,1,3,10,6]
alist = [2,1,1,1,1,1,1,1,1]
insert_sort(alist)
print(alist)1234567891011121314151617181920212223

对比一下教程中的代码。(比较简洁),它的外层循环是剩余无序的列表的下标的最小下标。

def insert_sort(alist):

    for index in range(1, len(alist)):

        current_value = alist[index]  # 当前插入项
        position = index   # 循环比较时的下标

        while position > 0 and alist[position-1] > current_value:
            alist[position] = alist[position - 1]
            position -= 1

        # 退出循环,可能是找到了位置,也可能是都比当前元素大
        alist[position] = current_value

alist = [2,7,5,84,10,1,3]
# alist = [2,1,1,1,1,1,1,1,1]
insert_sort(alist)
print(alist)



作者:qq_42907161

链接:https://blog.csdn.net/qq_42907161/article/details/108347983

来源:CSDN
著作权归作者所有,转载请联系作者获得授权,切勿私自转载。