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('毫秒')两万个数据，两种排序的时间对比，如下图：
