本文共 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/