七种常用排序算法：冒泡排序，选择排序，插入排序，希尔排序，堆排序，归并排序，快速排序
七种常用排序算法的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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import time
import random
import copy
def calc_time(fn):
def wrapper(self, *args, **kwargs):
t_start = time.time()
fn(self, *args, **kwargs)
self.sort_suc()
print "{0} used time ======> {1}s".format(fn.__name__, (time.time()-t_start))
return wrapper
class MySort(object):
"""docstring for MySort"""
def __init__(self, lis):
super(MySort, self).__init__()
self.r = copy.copy(lis)
self.n = len(lis)
def bubble_sort(self):
arr = self.r
n = self.n
flag = 1
for i in range(n - 1, 1, -1):
for j in range(0, i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
flag = 0
if flag:
break
flag = 1
def select_sort(self):
arr = self.r
n = self.n
for i in xrange(n-1):
index_of_min = i
for j in xrange(i+1, n):
if arr[j] < arr[index_of_min]:
index_of_min = j
if index_of_min != i:
arr[i], arr[index_of_min] = arr[index_of_min], arr[i]
def insert_sort(self):
arr = self.r
n = self.n
for i in xrange(1,n):
#前面的序列已升序排好，当前值如果比前面序列的最后一个值大，则保持当前值的位置，直接跳到下一个值
if arr[i] < arr[i-1]:
tmp = arr[i]
j = i - 1
while j >= 0 and arr[j] > tmp:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = tmp
def shell_sort(self):
arr = self.r
n = self.n
increment = 1
while increment < n/3:
increment = increment * 3 +1 # 1,4,13,...
while increment >= 1:
# print 'increment >>>>>>>> ', increment
# 对每组进行插入排序：每次从数组第increment个元素开始，每个元素与自己组内的数据进行直接插入排序
for i in xrange(increment, n):
if arr[i] < arr[i-increment]:
tmp = arr[i]
j = i - increment
while j >= 0 and arr[j] > tmp:
arr[j+increment] = arr[j]
j -= increment
arr[j+increment] = tmp
increment/=3
def heap_sort(self):
arr = self.r
n = self.n
# 以最小堆方式堆化数组
# 叶子节点可以认为是合法的堆了，从序号最大的非叶子节点(n/2-1)开始调整
for i in xrange(n/2-1,-1,-1):
self.min_heap_fix_down(i, n)
# 使用最小堆排序得到递减数组
for i in xrange(n-1, 0, -1):
arr[0],arr[i] = arr[i],arr[0]
self.min_heap_fix_down(0, i)
# 最小堆：父结点（（i-1）/2）的键值总是小于或等于任何一个子节点的键值
# 从第i个节点开始调整（下沉），count为节点总数， 第i个节点的左右字节点：2i+1,2i+2(i>=0)
def min_heap_fix_down(self, i, count):
a = self.r
tmp = a[i]
j = 2*i+1
while j < count:
if j+1 < count and a[j+1] < a[j]:
j+=1
if a[j] >= tmp:
break
a[i] = a[j]
i = j
j = 2*i +1
a[i] = tmp
def merge_sort(self):
tmp_list = [None] * self.n
# self.g_ncount = 0 # 逆序数对
last = self.n -1
self.msort(0, last, tmp_list)
# print self.g_ncount
def msort(self, first, last, tmp_list):
if first < last:
mid = (first + last) / 2
self.msort(first, mid, tmp_list) # 递归左边有序
self.msort(mid+1, last, tmp_list) # 递归右边有序
self.merge_list(first, mid, last, tmp_list)
# 将有二个有序数列a[first...mid]和a[mid+1...last]合并
def merge_list(self, first, mid, last, tmp_list):
a = self.r
i = first
j = mid+1
k = 0
while i <= mid and j <= last:
if a[i] <= a[j]:
tmp_list[k] = a[i]
i += 1
k += 1
else:
tmp_list[k] = a[j]
j += 1
k += 1
# self.g_ncount += (mid + 1 - i) # a[j]和前面未取出的每一个数都能组成逆序数对
while i <= mid :
tmp_list[k] = a[i]
i += 1
k += 1
while j <= last:
tmp_list[k] = a[j]
k += 1
j += 1
for x in xrange(k):
a[first+x] = tmp_list[x]
def quick_sort(self):
left = 0
right = self.n - 1
if left < right:
self.qsort(left, right)
def qsort(self, low, high):
if low < high :
a = self.r
pivot_key = a[low]
i = low
j = high
while i < j:
while i < j and a[j] > pivot_key:
j-=1
if i < j:
a[i] = a[j]
i+=1
while i < j and a[i] <= pivot_key:
i+=1
if i < j:
a[j] = a[i]
j-=1
a[i] = pivot_key
self.qsort(low, i-1)
self.qsort(i+1, high)
def sort_suc(self):
print '<<<<<<<<<< end >>>>>>>>>>'
def main():
mylist = []
for x in xrange(1,10000):
mylist.append(random.randint(1,1000000))
MySort(mylist).bubble_sort()
MySort(mylist).insert_sort()
MySort(mylist).select_sort()
MySort(mylist).shell_sort()
MySort(mylist).heap_sort()
MySort(mylist).merge_sort()
MySort(mylist).quick_sort()
if __name__ == '__main__':
main()