排序时间复杂度对比
- 2020 年 1 月 19 日
- 笔记
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('毫秒')
两万个数据，两种排序的时间对比，如下图：
