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

由于插入排序是兩層嵌套結構,時間復雜度大。
插入排序算是一個穩定排序的算法,可以在小規模數據比較時使用。
插入排序也有很多可以優化的點,比如采用二分法提高效率。