|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
# -*- coding:utf-8 -*-
__author__
=
'Abel Xu'
import
random
import
time
from
copy
import
deepcopy
def
insert_sort(list_an):
"""插入排序
"""
len_list
=
len
(list_an)
for
j
in
xrange
(
1
, len_list):
key
=
list_an[j]
i
=
j
-
1
while
i>
=
0
and
list_an[i] > key:
list_an[i
+
1
]
=
list_an[i]
i
=
i
-
1
list_an[i
+
1
]
=
key
return
list_an
def
merge_sort(list_an):
"""
归并排序
"""
if
len
(list_an) <
=
1
:
return
list_an
mid
=
len
(list_an)
/
2
left
=
merge_sort(list_an[:mid])
right
=
merge_sort(list_an[mid:])
return
merge(left, right)
def
merge(left, right):
result
=
[]
i, j
=
0
,
0
len_left
=
len
(left)
len_right
=
len
(right)
while
i<len_left
and
j<len_right:
if
left[i] <
=
right[j]:
result.append(left[i])
i
+
=
1
else
:
result.append(right[j])
j
+
=
1
result
+
=
left[i:]
result
+
=
right[j:]
return
result
if
__name__
=
=
'__main__'
:
list_an
=
[random.randint(
0
,
10000
)
for
_
in
xrange
(
10000
)]
list_bn
=
deepcopy(list_an)
list_cn
=
deepcopy(list_an)
print
(
'插入排序的耗时:'
)
insert_time
=
time.time()
list_an
=
insert_sort(list_an)
print
(time.time()
-
insert_time)
print
(
'list内置排序的耗时:'
)
list_time
=
time.time()
list_bn.sort()
print
(time.time()
-
list_time)
print
(
'归并排序的耗时:'
)
merge_time
=
time.time()
list_cn
=
merge_sort(list_cn)
print
(time.time()
-
merge_time)
|
运行结果:
插入排序的耗时:
3.22006893158
list内置排序的耗时:
0.00256586074829
归并排序的耗时:
0.0303440093994
结论:
Python的list自带sort函数性能优于插入排序和归并排序.
本文转自 许大树 51CTO博客，原文链接：http://blog.51cto.com/abelxu/1898606，如需转载请自行联系原作者
