本文共 1094 字,大约阅读时间需要 3 分钟。
简介:
传统的插入法思想为:
1.从头开始,构建有序数列;
2.再将之后需要排序的数据从头至尾(或从尾至头)进行比较,插入到其相应的位置。
而二分插入排序法第一步与传统插入法相同,第二步而是采用二分查询的原理,一半一半去缩小需要寻找插入的位置使插入的最大循环步骤从n-1缩小至log2(n),对于大量数据的排序,相较于插入法速度可提升70%左右。
代码如下:
import mathimport timeimport randomlist_a=[random.randint(0,10000) for i in range(10000) ]# list_a=[random.randint(0,9) for i in range(100000) ]# list_a=[5,1,7,9,8,6,2,4,3]start_t=time.time()print('开始时间:',start_t)for i in range(1,len(list_a)): temp=list_a[i] # 阶段性初始化最大最小和中间值 min = 0 max = i - 1 mid = int((max + min) / 2) while True: if temp<=list_a[0]: # 待插入数据和头数据比较 for j in range(i,0,-1): list_a[j]=list_a[j-1] list_a[min]=temp break if temp>=list_a[i-1]: # 待插入数据和尾数据比较 break if max-min==1: # 插入位置终结条件,最大和最小值序号差值为1 for j in range(i,max,-1): list_a[j] = list_a[j - 1] list_a[max] = temp break if temp>list_a[mid]: # 插入值比中间值大时,重置中间值和最小值 min=mid mid=int((min+max)/2) elif temp
PS:
由于示例需要展示运算过程并以便转换为其它代码,本例并未使用如insert等Python专有函数。
转载地址:http://hszfd.baihongyu.com/