Python使用二分插入排序竟然比直接插入排序快99倍!

简介: Python使用二分插入排序竟然比直接插入排序快99倍!之前发布同一个算法,C++竟然比C快8倍!  , 有同学提出是因为C++中使用了二分插入排序,于是用python比较了下两种排序差距有多大。


Python使用二分插入排序竟然比直接插入排序快99倍!

之前发布同一个算法,C++竟然比C快8倍!  , 有同学提出是因为C++中使用了二分插入排序,于是用python比较了下两种排序差距有多大。


测试结果如下:


Python insertion sort took time: 1:39:42.448904
Python insertion sort with binary search took time: 0:01:13.263267


代码如下:


import datetime
import bisect

def insertion_sort(l):
    for i in xrange(1, len(l)):
        j = i-1 
        key = l[i]
        while (l[j] > key) and (j >= 0):
           l[j+1] = l[j]
           j -= 1
        l[j+1] = key

def insertion_sort_bin(seq):
    for i in range(1, len(seq)):
        bisect.insort(seq, seq.pop(i), 0, i)

a=[]
for x in range(200000):
	a.append(x)

a.reverse()

start = datetime.datetime.now()
insertion_sort(a)
end = datetime.datetime.now()
print "Python insertion sort took time: %s" % (end-start)

a.reverse()

start2 = datetime.datetime.now()
insertion_sort_bin(a)
end2 = datetime.datetime.now()
print "Python insertion sort with binary search took time: %s" % (end2-start2)


同样是python,算法不一样,速度差百倍!


目录
相关文章
|
6月前
|
Python
Python基础【素数判断、插入字符串、插入排序】
Python基础【素数判断、插入字符串、插入排序】
|
5月前
|
Python
【Python 训练营】N_18 插入排序
【Python 训练营】N_18 插入排序
25 0
|
6月前
|
搜索推荐 Python
Python实现插入排序算法
Python实现插入排序算法
23 1
|
6月前
|
搜索推荐 Python
python实现插入排序算法。
python实现插入排序算法。
44 4
|
6月前
|
搜索推荐 Python
Python 插入排序:原理、使用场景与实现方法
本文主要介绍了Python 插入排序:原理、使用场景与实现方法
114 6
|
6月前
|
搜索推荐 算法 Python
【Python排序算法系列】—— 插入排序
【Python排序算法系列】—— 插入排序
44 0
|
算法 搜索推荐 Python
Python算法——插入排序
Python算法——插入排序
116 0
|
算法 搜索推荐 Python
python算法 - 插入排序算法
python算法 - 插入排序算法
|
机器学习/深度学习 算法 搜索推荐
【排序算法】冒泡排序,选择排序,插入排序算法原理及Python代码实现
【排序算法】冒泡排序,选择排序,插入排序算法原理及Python代码实现
|
搜索推荐 算法 Python
玩转Python插入排序,从基础到进阶
插入排序是一种简单但有效的排序算法。它的基本思想是将待排序的元素逐个插入已排序序列中的正确位置,直到所有元素都被插入完成。插入排序的算法复杂度为O(n^2),适用于小规模的数据排序。本文将介绍插入排序的原理、具体实现和优化,并提供相关的Python代码示例。
173 0