pyhton实现插入排序

插入排序就像打扑克牌那样， 调整手中扑克牌的顺序。

我最开始写的版本

list_ = [2,1,7,4,9,3,5]

new_list = []
for n in list_:
    if new_list:
        for j in range(len(new_list)):  # 此处不能把new_list 做为循环对象， 
                                        # 因为下文会修改new_list,改循环len（）
            if n < new_list[j]:
                new_list.insert(j, n)
                break
            if j == len(new_list) -1:
                new_list.insert(j+1, n)
    else:
        new_list.append(n)

print(new_list)

参考书上的第二版本

l = [2,1,7,4,9,3,5]


def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i-1
        while j >=0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists


if __name__ == "__main__":
    new_l = insert_sort(l)
    print(new_l)

第二种写法中， 用在原列表的位置互相交换元素的方法替代insert方法， 效率是要高很多的， 因为， 后面的元素不要往后移。

还有一种写法是，是我尝试把while 循环改称for 循环的例子

l = [2,1,7,4,9,3,5]


def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        for j in range(i-1):
            if key < lists[j]:
                lists[j], key = key, lists[j]
    return lists


if __name__ == "__main__":
    new_l = insert_sort(l)
    print(new_l)