1 #-*-coding:utf8-*-
2 import random
3 a=
[]
4 b=
[]
5 def init_array():
6 for i
in range(10000
):
7 v = random.randint(1,10000
)
8 a.append(v)
9 b.append(v)
10
11 #冒泡
12 def sort_array(a):
13 for i
in range(len(a)):
14 for j
in range(i+1
,len(a)):
15 if a[i] >
a[j]:
16 i_v =
a[i]
17 a[i]=
a[j]
18 a[j]=
i_v
19
20
21 #快排
22 def quick_sort(a,left,right):
23 if left <
right:
24 key =
a[left]
25 low =
left
26 high =
right
27 while low<
high:
28 while low<high
and a[high]>=
key:
29 high-=1
30 a[low] =
a[high]
31 while low<high
and a[low]<=
key:
32 low+=1
33 a[high]=
a[low]
34 a[low]=
key
35 quick_sort(a,left,low-1
)
36 quick_sort(a,low+1
,right)
37
38
39 init_array()
40
41 print "a",len(a)
42 print "b",len(b)
43
44 sort_array(a)
45 quick_sort(b,0,len(b)-1
)
46
47 print a,len(a)
48 print b,len(b)以上保存为 sort.py,然后：python -m cProfile sort.py冒泡时间复杂度O(n^2)快排最差O(n^2),平均O(n*lgn)
转载于:https://www.cnblogs.com/yako/p/4928768.html
