Python排序算法之插入排序及其优化方案详解

第Python排序算法之插入排序及其优化方案详解一、插入排序

插入排序与我们平时打扑克牌非常相似，将新摸到的牌插入到已有的牌中合适的位置，而已有的牌往往是有序的。

1.1执行流程

（1）在执行过程中，插入排序会将序列分为2部分，头部是已经排好序的，尾部是待排序的。

（2）从头开始扫描每一个元素，每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

1.2逆序对

数组2,3,8,6,1的逆序对为：2,1,18,18,66,1，共5个逆序对。

插入排序的时间复杂度与逆序对的数量成正比关系，逆序对的数量越多，插入排序的消耗的时间就越多。

当逆序对的数量极少时，插入排序的效率特别高，甚至速度比Onlogn级别的快速排序还要快。

1.3代码实现

将一个元素插入到数组有序的前半部分中，那个插入的位置元素一定是比该元素大，而该位置前的元素比该元素小（或者是没有前一个元素）。所以我们可以通过比较，将该元素进行冒泡：如果前一个元素比我大，则交换位置，否则停止冒泡。

definsertion_sort_ver1(array):

n=len(array)

forrightinrange(1,n):

cur=right

whilecur0andarray[cur-1]array[cur]:

array[cur-1],array[cur]=array[cur],array[cur-1]

cur-=1

整体代码：

importnumpyasnp

importtime

#检查是否有序

deforderCheck(array):

foriinrange(len(array)-1):

ifarray[i]array[i+1]:

print('排序失败')

return

print('排序成功')

defsort(sort_algorithm,ori_array):

#先复制一份数组，再进行更改

array=np.copy(ori_array)

start=time.clock()

sort_algorithm(array)

end=time.clock()

total_time=float(end-start)

print(sort_algorithm.__name__+":%0.5f"%total_time)

orderCheck(array)

definsertion_sort_ver1(array):

n=len(array)

forrightinrange(1,n):

cur=right

whilecur0andarray[cur-1]array[cur]:

array[cur-1],array[cur]=array[cur],array[cur-1]

cur-=1

array=np.random.randint(0,10000,2000,dtype=int)

sort(insertion_sort_ver1,array)

消耗时间为0.82632秒。

1.4优化1

在冒泡中，交换前后cur和cur-1位置两个元素的位置，需要进行两次赋值，但如果冒泡仍要继续，cur-1位置的元素还是会被cur-2位置的元素覆盖，所以两次赋值中的一次其实是无意义的，为此我们可以先找到插入位置，然后将后方的元素作统一的移动；或者是在冒泡过程中只进行一次赋值（将前一个元素移动到后方），直到冒泡结束确定插入位置后，再进行待插入元素的插入。

#元素交换作优化

definsertion_sort_ver2(array):

n=len(array)

forrightinrange(1,n):

cur=right

elem=array[cur]

whilecur0andarray[cur-1]elem:

array[cur]=array[cur-1]

cur-=1

array[cur]=elem

消耗时间为0.45987秒，明显变快了。

1.5优化2

之前我们在寻找插入的位置时，采用的是从大到小依次遍历的方法，因为是在一个有序的数组上寻找插入的位置，我们肯定会想到一种查找的方法：二分查找。通过二分查找，我们可以通过O(logn)级别的比较与O(n)级别的元素移动完成排序任务，而之前我们进行的比较和移动，都是O(n)级别。

1.5.1普通二分查找

普通的二分查找十分简单，根据中间位置元素大小更新两端索引位置即可，在此两端的索引[left,right)采用左闭右开的方式，这样未查找到元素的条件就十分简单，因为区间左闭右开，当leftright时，表明区间内还有元素，仍旧可以进行查找；否则，区间里没有元素了，说明元素未查找到，代码如下。

defbinary_search(array,target):#[left,right)左闭右开

left=0

right=len(array)

whileleftright:#当leftright，表明区间中还有值，否则哪怕left==right,因right不可取，区间中还是无值

middle=(left+right)1

iftargetarray[middle]:

right=middle

elifarray[middle]target:

left=middle+1

else:

returnmiddle

return-1

1.5.2二分查找插入位置

查找插入位置的二分查找显然和普通二分不同，在此我们修改一下左右端点移动的条件与移动方式。在此左右端点依旧左闭右开，如果当array[middle]小于或等于插入元素target，那么显然middle不可能是插入位置，middle位置的元素也不再需要，left应该为middle+1；而当array[middle]大于target，那么middle有可能是插入的位置（插入位置大于target，前一个元素如果存在，应小于target），应该保留middle，所以right=middle。但是区间是左闭右开，right不可取到，哪怕right=middle，middle不还是无法取得吗？但由于array[middle]不论取何值（不管是大于、等于、小于），都将导致左右端点left、right的变化，且数组中左右端点代表区间的大小是不断减小的，最终左右端点重合，此时的位置就是插入的位置。

下面是查找的示例：

代码如下：

defbinary_search(array,index):

left=0

right=index

whileleftright:

middle=(left+right)1

ifarray[middle]array[index]:#大于目标，可能是插入的位置，用right保留

right=middle

else:#小于等于，不可能是插入位置，更新left为middle+1

left=middle+1

returnleft#最后插入的位置

1.5.3使用二分的插入排序

找到插入位置后，我们只需移动位置后面的元素，再将元素插入即可。

#利用二分查找找到插入的点，减少了比较的次数

definsertion_sort_ver3(array):

n=len(array)

forrightinrange(1,n):

index=binary_search(array,right)

elem=array[right]

foriinrange(right,index,-1):

array[i]=arr