本文實例講述了Python八大常見排序算法定義、實現及時間消耗效率分析。分享給大家供大家參考，具體如下：
昨晚上開始總結了一下常見的幾種排序算法，由于之前我已經寫了好幾篇排序的算法的相關博文了現在總結一下的話可以說是很方便的，這里的目的是為了更加完整詳盡的總結一下這些排序算法，為了復習基礎的東西，從冒泡排序、直接插入排序、選擇排序、歸并排序、希爾排序、桶排序、堆排序。快速排序入手來分析和實現，在最后也給出來了簡單的時間統計，重在原理、算法基礎，其他的次之，這些東西的熟練掌握不算是對之后的工作或者接下來的準備面試都是很有幫助的，算法重在理解內在含義和理論基礎，在實現的時候才能避開陷阱少出錯誤，這不是說練習的時候有錯誤不好而是說，有些不該出現的錯誤盡量還是少出現的好，畢竟好的編程習慣是離不開嚴格的約束的，好了，這里就不多說了，復習一下基礎知識，共同學習吧，下面是具體實現，注釋應該都很詳細，就不解釋了：
|
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
#!usr/bin/env python#encoding:utf-8'''''__Author__:沂水寒城功能：八大排序算法'''import timeimport randomtime_dict={}def time_deco(sort_func): ''''' 時間計算的裝飾器函數,可用于計算函數執行時間 ''' def wrapper(num_list): start_time=time.time() res=sort_func(num_list) end_time=time.time() time_dict[str(sort_func)]=(end_time-start_time)*1000 print '耗時為：',(end_time-start_time)*1000 print '結果為：', res return wrapperdef random_nums_generator(max_value=1000, total_nums=20): ''''' 隨機數列表生成器 一些常用函數： random隨機數生成 random.random()用于生成一個0到1之間的隨機數:0 <= n < 1.0； random.uniform(a, b)，用于生成一個指定范圍內的隨機符點數，兩個參數其中一個是上限，一個是下限。min(a,b) <= n <= max(a,b)； randdom.randint(a, b), 用于生成一個指定范圍內的整數，其中a是下限，b是上限： a<= n <= b； random.randrange(start, stop, step), 從指定范圍內，按指定基數遞增的集合獲取一個隨機數； random.choice(sequence), 從序列中獲取一個隨機元素； random.shuffle(x), 用于將一個列表中的元素打亂； random.sample(sequence, k), 從指定序列中隨機獲取指定長度的片斷； ''' num_list=[] for i in range(total_nums): num_list.append(random.randint(0,max_value)) return num_list#@time_decodef Bubble_sort(num_list): ''''' 冒泡排序，時間復雜度O(n^2)，空間復雜度O(1)，是穩定排序 ''' for i in range(len(num_list)): for j in range(i,len(num_list)): if num_list[i]>num_list[j]: #這里是升序排序 num_list[i], num_list[j]=num_list[j], num_list[i] return num_list#@time_decodef Insert_sort(num_list): ''''' 直接插入排序，時間復雜度O(n^2)，空間復雜度O(1)，是穩定排序 ''' for i in range(len(num_list)): for j in range(0,i): if num_list[i]<num_list[j]: #這里是升序排序,跟冒泡排序差別在于，冒泡是向后遍歷，這個是向前遍歷 num_list[i], num_list[j]=num_list[j], num_list[i] return num_list#@time_decodef Select_sort(num_list): ''''' 選擇排序，時間復雜度O(n^2)，空間復雜度O(1)，不是穩定排序 ''' for i in range(len(num_list)): min_value_index=i for j in range(i, len(num_list)): if num_list[j]<num_list[min_value_index]: min_value_index=j #乍一看，感覺冒泡，選擇，插入都很像，選擇跟冒泡的區別在于：冒泡是發現大 #小數目順序不對就交換，而選擇排序是一輪遍歷結束后選出最小值才交換，效率更高 num_list[i], num_list[min_value_index]=num_list[min_value_index], num_list[i] return num_list#@time_decodef Merge_sort(num_list): ''''' 歸并排序，時間復雜度O(nlog?n)，空間復雜度：O(1)，是穩定排序 ''' if len(num_list)==1: return num_list length=len(num_list)/2 list1=num_list[:length] list2=num_list[length:] result_list=[] while len(list1) and len(list2): if list1[0]<=list2[0]: result_list.append(list1[0]) del list1[0] #這里需要刪除列表中已經被加入到加過列表中的元素，否則最后比較完后列表 else: #中剩余元素無法添加 result_list.append(list2[0]) del list1[0] if len(list1): #遍歷比較完畢后列表中剩余元素的添加 result_list+=list1 else: result_list+=list2 return result_list#@time_decodef Shell_sort(num_list): ''''' 希爾排序，時間復雜度：O(n)，空間復雜度：O(n^2),不是穩定排序算法 ''' new_list = [] for one_num in num_list: new_list.append(one_num) count=len(new_list) step=count/2; while step>0: i=0 while i<count: j=i+step while j<count: t=new_list.pop(j) k=j-step while k>=0: if t>=new_list[k]: new_list.insert(k+1, t) break k=k-step if k<0: new_list.insert(0, t) #print '---------本輪結果為：--------' #print new_list j=j+step #print j i=i+1 #print i step=step/2 #希爾排序是一個更新步長的算法 return new_list#@time_decodef Tong_sort(num_list): ''''' 桶排序，時間復雜度O(1)，空間復雜度與最大數字有關，可以認為是O(n)，典型的空間換時間的做法 ''' original_list = [] total_num=max(num_list) #獲取桶的個數 for i in range(total_num+1): #要注意這里需要的數組元素個數總數比total_num數多一個因為下標從0開始 original_list.append(0) for num in num_list: original_list[num] += 1 result_list = [] for j in range(len(original_list)): if original_list[j] != 0: for h in range(0,original_list[j]): result_list.append(j) return result_listdef Quick_sort(num_list): ''''' 快速排序，時間復雜度：O(nlog?n)，空間復雜度：O(nlog?n)，不是穩定排序 ''' if len(num_list)<2: return num_list left_list = [] #存放比基準結點小的元素 right_list = [] #存放比基準元素大的元素 base_node = num_list.pop(0) #在這里采用pop()方法的原因就是需要移除這個基準結點，并且賦值給base_node這個變量 #在這里不能使用del()方法，因為刪除之后無法再賦值給其他變量使用，導致最終數據缺失 #快排每輪可以確定一個元素的位置，之后遞歸地對兩邊的元素進行排序 for one_num in num_list: if one_num < base_node: left_list.append(one_num) else: right_list.append(one_num) return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)def Heap_adjust(num_list, i, size): left_child = 2*i+1 right_child = 2*i+2 max_temp = i #print left_child, right_child, max_temp if left_child<size and num_list[left_child]>num_list[max_temp]: max_temp = left_child if right_child<size and num_list[right_child]>num_list[max_temp]: max_temp = right_child if max_temp != i: num_list[i], num_list[max_temp] = num_list[max_temp], num_list[i] Heap_adjust(num_list, max_temp, size) #避免調整之后以max為父節點的子樹不是堆def Create_heap(num_list, size): a = size/2-1 for i in range(a, -1, -1): #print '**********', i Heap_adjust(num_list, i, size)#@time_decodef Heap_sort(num_list): ''''' 堆排序，時間復雜度：O(nlog?n)，空間復雜度：O(1)，不是穩定排序 ''' size=len(num_list) Create_heap(num_list, size) i = size-1 while i > 0: num_list[0], num_list[i] = num_list[i], num_list[0] size -= 1 i -= 1 Heap_adjust(num_list, 0, size) return num_listif __name__ == '__main__': num_list=random_nums_generator(max_value=100, total_nums=50) print 'Bubble_sort', Bubble_sort(num_list) print 'Insert_sort', Insert_sort(num_list) print 'Select_sort', Select_sort(num_list) print 'Merge_sort', Merge_sort(num_list) print 'Shell_sort', Shell_sort(num_list) print 'Tong_sort', Tong_sort(num_list) print 'Heap_sort', Heap_sort(num_list) print 'Quick_sort', Quick_sort(num_list) # print '-----------------------------------------------------------------------------' # for k,v in time_dict.items(): # print k, v |
結果如下：
Bubble_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Insert_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Select_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Merge_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Shell_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Tong_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Heap_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
Quick_sort [34, 49, 63, 67, 71, 72, 75, 120, 128, 181, 185, 191, 202, 217, 241, 257, 259, 260, 289, 293, 295, 304, 311, 326, 362, 396, 401, 419, 423, 456, 525, 570, 618, 651, 701, 711, 717, 718, 752, 774, 813, 816, 845, 885, 894, 900, 918, 954, 976, 998]
這里沒有使用到裝飾器，主要自己對這個裝飾器不太了解，在快速排序的時候報錯了，也沒有去解決，這里簡單貼一下一個測試樣例使用裝飾器的結果吧：
Bubble_sort 耗時為： 0.0290870666504
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Insert_sort 耗時為： 0.0209808349609
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Select_sort 耗時為： 0.0259876251221
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Merge_sort 耗時為： 0.0138282775879
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Shell_sort 耗時為： 0.113964080811
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Tong_sort 耗時為： 0.0460147857666
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Heap_sort 耗時為： 0.046968460083
結果為： [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
None
Quick_sort [5, 45, 46, 63, 81, 83, 89, 89, 89, 90]
-----------------------------------------------------------------------------
<function Shell_sort at 0x7f8ab9d34410> 0.113964080811
<function Select_sort at 0x7f8ab9d34230> 0.0259876251221
<function Insert_sort at 0x7f8ab9d34140> 0.0209808349609
<function Heap_sort at 0x7f8ab9d34758> 0.046968460083
<function Merge_sort at 0x7f8ab9d34320> 0.0138282775879
<function Tong_sort at 0x7f8ab9d34500> 0.0460147857666
<function Bubble_sort at 0x7f8ab9d34050> 0.0290870666504
接下來有時間的話我想學一下裝飾器的東西，感覺對于模式化的東西裝飾器簡直就是一個神器，但是得明白會用會寫才行哈！
希望本文所述對大家Python程序設計有所幫助。
原文鏈接：https://blog.csdn.net/together_cz/article/details/76049122
