#刚考完python二级,终于有空来记录记录学的那些乱七八糟的东西了。
插入排序
大体就是插入已排序的序列的合适位置,
方法是序列最前增加一个0,称之为哨兵,放入待比较值和它后面已排好的序列比较,找到合适的插入点。
实现代码:
nums = [2,3,5,8,9,1,7,5]nums = [0] + m_list[0]sentinel,*origin = numscount_swap = 0count_iter = 0length = len(nums)for i in range(2,length):2开始 nums[0] = nums[i] j = i -1 count_iter +=1 if nums[j] > nums[0] while nums[j] > nums[0]: nums[j+1]=nums[j] j -=1 count_swap +=1 nums[j+1] = nums[0]print(nums,count_swap,count_iter)
由于插入排序是两层嵌套结构,时间复杂度大。
插入排序算是一个稳定排序的算法,可以在小规模数据比较时使用。
插入排序也有很多可以优化的点,比如采用二分法提高效率。