排序时间复杂度对比
2018-09-10 01:06:03来源:博客园 阅读 ()
1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 import random 4 import datetime 5 6 #插入式排序 7 def insert_sort(list,result): 8 cnt = len(list) 9 i=0 10 for i in range(cnt): 11 right = list[i] 12 result.append(right) 13 if len(result) == 1: 14 continue 15 for j in range(len(result)-1,0,-1): 16 if right < result[j-1]: 17 result[j] = result[j-1] 18 result[j-1] = right 19 else: 20 break 21 return result 22 23 #归并排序 24 def tog_sort(lists): 25 if len(lists) <= 1: 26 return lists 27 num = int(len(lists)/2) 28 left = tog_sort(lists[:num]) 29 right = tog_sort(lists[num:]) 30 return sort(left,right) 31 32 def sort(left,right): 33 l,r = 0,0 34 result = [] 35 while l<len(left) and r<len(right): 36 if left[l]<right[r]: 37 result.append(left[l]) 38 l += 1 39 else: 40 result.append(right[r]) 41 r += 1 42 result += left[l:] 43 result += right[r:] 44 return result 45 46 if __name__ == '__main__': 47 list = [] 48 result = [] 49 for i in range(20000): 50 list.append(random.randint(1, 200)) 51 print('BEFORE:') 52 print(list) 53 starttime = datetime.datetime.now() 54 insert_sort(list,result) 55 print('插入式排序:') 56 print(result) 57 endtime = datetime.datetime.now() 58 print((endtime - starttime).seconds,end='') 59 print('秒',end='') 60 print((endtime - starttime).microseconds,end='') 61 print('毫秒') 62 63 starttime = datetime.datetime.now() 64 result = tog_sort(list) 65 print('归并排序:') 66 print(result) 67 endtime = datetime.datetime.now() 68 print((endtime - starttime).seconds, end='') 69 print('秒', end='') 70 print((endtime - starttime).microseconds, end='') 71 print('毫秒')
两万个数据,两种排序的时间对比,如下图:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- pycharm 新建py文件写时有作者和时间 2019-08-13
- Python3字典排序 2019-07-24
- 2.时间戳转换时间字符串函数 2019-07-24
- 1.日期时间字符串转时间戳 2019-07-24
- 牺牲空间来优化时间 2019-07-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash