#刚考完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)

由于插入排序是两层嵌套结构,时间复杂度大。
插入排序算是一个稳定排序的算法,可以在小规模数据比较时使用。
插入排序也有很多可以优化的点,比如采用二分法提高效率。