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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
| import random, time
def generate_random_array(size, lrange, rrange):
return [random.randint(lrange, rrange) for i in range(size)]
def is_order_asc(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
def sort(name):
def decoration(sort_func):
def wrapper(*dargs, **dkw):
start_time = time.time()
sort_func(*dargs, **dkw)
if is_order_asc(*dargs):
print(name + '：数组排序所需时间为:' + str((time.time() - start_time) * 1000) + '毫秒')
else:
print(name + '：数组排序失败')
return wrapper
return decoration
@sort('冒泡排序')
def bubble_sort(arr):
length = len(arr)
for i in range(length - 1):
for j in range(length - 1):
if arr[j + 1] < arr[j]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
@sort('选择排序')
def select_sort(arr):
for i in range(len(arr) - 1):
min = i
for j in range(i + 1,len(arr)):
if arr[j] < arr[min]:
min = j
arr[min], arr[i] = arr[i], arr[min]
@sort('插入排序')
def insert_sort(arr):
for i in range(1, len(arr)):
insert_value = arr[i]
for j in range(i, -1, -1):
if arr[j - 1] <= insert_value:
break
arr[j] = arr[j - 1]
arr[j] = insert_value
@sort('希尔排序')
def shell_sort(arr):
h = 1
while h * 3 + 1 < len(arr):
h = h * 3 + 1
while h > 0:
for i in range(h, len(arr)):
insert_value = arr[i]
for j in range(i, -1, -h):
if (arr[j - h] <= insert_value):
break
arr[j] = arr[j - h]
arr[j] = insert_value
h = int((h - 1) / 3)
@sort('统计排序')
def count_sort(arr):
min_value = arr[0]
max_value = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_value:
max_value = arr[i]
elif arr[i] < min_value:
min_value = arr[i]
else:
pass
count = [0 for i in range(max_value - min_value + 1)]
for i in arr:
count[i - min_value] += 1
index = 0
for i in range(len(count)):
for j in range(count[i]):
arr[index] = i + min_value
index += 1
@sort('快速排序')
def quick_sort(arr):
quick(arr, 0, len(arr) - 1)
def quick(arr, start, end):
if start >= end:
return
pivot_index = partition(arr, start, end)
quick(arr, start, pivot_index - 1)
quick(arr, pivot_index + 1, end)
def partition(arr, start, end):
pivot = arr[start]
mark = start
for i in range(start + 1, end + 1):
if arr[i] <= pivot:
mark += 1
arr[i], arr[mark] = arr[mark], arr[i]
arr[start], arr[mark] = arr[mark], arr[start]
return mark
@sort('归并排序')
def merge_sort(arr):
merge_sort2(arr, 0, len(arr) - 1)
def merge_sort2(arr, start, end):
if start >= end:
return
middle = int((end - start) / 2) + start
merge_sort2(arr, start, middle)
merge_sort2(arr, middle + 1, end)
merge(arr, start, middle, end)
def merge(arr, start, middle, end):
copy = [arr[i] for i in range(start, end + 1)]
left = start
right = middle + 1
index = start
while left <= middle and right <= end:
if copy[left - start] <= copy[right - start]:
arr[index] = copy[left - start]
left+=1
else:
arr[index] = copy[right - start]
right+=1
index+=1
while left <= middle:
arr[index] = copy[left - start]
left+=1
index+=1
while right <= end:
arr[index] = copy[right - start]
right+=1
index+=1
if __name__ == '__main__':
bubble_sort(generate_random_array(10000, 0, 1000000))
select_sort(generate_random_array(10000, 0, 1000000))
insert_sort(generate_random_array(10000, 0, 1000000))
shell_sort(generate_random_array(10000, 0, 1000000))
count_sort(generate_random_array(10000, 50, 100))
quick_sort(generate_random_array(10000, 0, 1000000))
merge_sort(generate_random_array(10000, 0, 1000000))
|
