• 欢迎访问圣洁的白莲!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

插入排序【python】

Python 菜根譚 2个月前 (09-06) 37次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

插入排序【python】

 

        插入排序就像摸牌一样,从一堆没有顺序的牌中随机摸取一张放在手中,此时我们就想象手中的这张牌就是有序的,然后再从无序的牌中摸取一张并和手中的牌比较大小,如果比手中的牌小就插在前面,比手中的牌大就插在后面,按此顺序摸到的牌再和手中的牌比较,从后向前比较,手中的牌也依次向后挪一个位置,直到找到适合摸起的那张牌的位置。

思路:

  o列表被分为有序区和无序区两个部分。最初有序区只有一个元素。

  o每次从无序区选择一个元素,插入到有序区的位置,直到无序区变空。

  o时间复杂度:O(n2)

代码实现:

import time
import random

# 统计排序所需时间
def cal_time(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print("running time: %s secs." % (end_time-start_time))
        return result
    return wrapper

@cal_time
def insert_sort(li):
    for i in range(1,len(li)):
        tmp = li[i] # 摸到手里的牌
        j = i -1    # 手中有序的牌的下标位置
        while j >= 0 and li[j] > tmp:  # 只要往后挪,2个条件必须满足
            # 如果 j = -1 就停止挪,如果li[j]小于tmp就停止挪
            li[j+1] = li[j] # 手中的牌向后挪一个位置
            j -= 1
        # j 位置在循环结束的时候要么是 -1 要么是一个比tmp小的值
        li[j+1] = tmp   # 将摸起的牌插入到适合的位置

li = list(range(100))    # 随机生成10个数

random.shuffle(li)  # 打乱排序
print('无序的数:',li)
insert_sort(li)
print('有序的数:',li)

浩瀚学海,虔诚分享!


圣洁的白莲 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:插入排序【python】
喜欢 (0)
[]
分享 (0)
关于作者:
浩瀚学海,虔诚分享!

您必须 登录 才能发表评论!