时间:2021-05-22
这篇文章并不是介绍排序算法原理的,纯粹是想比较一下各种排序算法在真实场景下的运行速度。
算法由 Python 实现,可能会和其他语言有些区别,仅当参考就好。
测试的数据是自动生成的,以数组形式保存到文件中,保证数据源的一致性。
排序算法
直接插入排序
时间复杂度:O(n²)
空间复杂度:O(1)
稳定性:稳定
希尔排序
时间复杂度:O(n)
空间复杂度:O(n√n)
稳定性:不稳定
简单选择排序
时间复杂度:O(n²)
空间复杂度:O(1)
稳定性:不稳定
堆排序
时间复杂度:O(nlog₂n)
空间复杂度:O(1)
稳定性:不稳定
冒泡排序
时间复杂度:O(n²)
空间复杂度:O(1)
稳定性:稳定
快速排序
时间复杂度:O(nlog₂n)
空间复杂度:O(nlog₂n)
稳定性:不稳定
归并排序
时间复杂度:O(nlog₂n)
空间复杂度:O(1)
稳定性:稳定
基数排序
时间复杂度:O(d(r+n))
空间复杂度:O(rd+n)
稳定性:稳定
速度比较
from random import randomfrom json import dumps, loads# 生成随机数文件def dump_random_array(file='numbers.json', size=10 ** 4): fo = open(file, 'w', 1024) numlst = list() for i in range(size): numlst.append(int(random() * 10 ** 10)) fo.write(dumps(numlst)) fo.close()# 加载随机数列表def load_random_array(file='numbers.json'): fo = open(file, 'r', 1024) try: numlst = fo.read() finally: fo.close() return loads(numlst)from _datetime import datetime# 显示函数执行时间def exectime(func): def inner(*args, **kwargs): begin = datetime.now() result = func(*args, **kwargs) end = datetime.now() inter = end - begin print('E-time:{0}.{1}'.format( inter.seconds, inter.microseconds )) return result return inner如果数据量特别大,采用分治算法的快速排序和归并排序,可能会出现递归层次超出限制的错误。
解决办法:导入 sys 模块(import sys),设置最大递归次数(sys.setrecursionlimit(10 ** 8))。
@exectimedef bubble_sort(array): for i in range(len(array)): for j in range(i, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] return arrayarray = load_random_array()print(bubble_sort(array) == sorted(array))↑ 示例:测试直接插入排序算法的运行时间,@exectime 为执行时间装饰器。
算法执行时间
算法速度比较
总结
以上就是本文关于Python八大排序算法速度实例对比的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
Python3简单实例计算同花的概率代码
Python语言描述最大连续子序列和
Python实现调度算法代码详解
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了PHP排序算法之基数排序(RadixSort)。分享给大家供大家参考,具体如下:基数排序在《大话数据结构》中并未讲到,但是为了凑齐八大排序算法,我
如何用Python实现八大排序算法1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于
冒泡排序在八大排序中,冒泡排序是最为出名的排序算法之一!冒泡排序的代码还是相当简单的,两层循环,外层是冒泡轮数,里层是依次比较,这个算法的时间复杂度为O(n2)
Python实现八大排序算法,具体内容如下1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算
选择排序,作为八大经典算法之一,虽不如插入,快速,希尔等排序高效,但其结构简单,思路清晰,适合新手理解算法,了解排序,适合数据较少时的排序情况。如下是选择排序的