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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
|
from __future__ import print_function
import random
def func(a, b, reversed):
return a < b if reversed else a > b
def insertSort(unsorted_list, reversed=False):
'''
直接插入排序
把 n 个待排序的元素看成一个有序表和一个无序表，
开始时有序表中只有一个元素，无序表中有 n-1 个元素。
排序过程即每次从无序表中取出第一个元素，
将它插入到有序表中，使之成为新的有序表，重复 n-1 次完成整个排序过程。
'''
print("raw: ", unsorted_list)
for i in range(1, len(unsorted_list)):
j = i-1
cmp = unsorted_list[i]
while j > -1 and func(unsorted_list[j], cmp, reversed):
unsorted_list[j+1], unsorted_list[j] = unsorted_list[j], cmp
j -= 1
print("NO.%d:" % i, unsorted_list)
print("last:", unsorted_list)
return unsorted_list
def shellSort(unsorted_list, reversed=False):
'''
希尔排序是一种插入排序算法，又称作缩小增量排序。是对直接插入排序算法的改进。其基本思想是：
先取一个小于 n 的整数作为第一个增量，把全部数据分成个组。所有距离为的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
1 2 3 4 5 6 7 8 9 10 11
-----------
-----------
-----------
'''
print("raw: ", unsorted_list)
n = len(unsorted_list)/2
num = 1
while n:
for ni in range(n):
group = range(ni, len(unsorted_list), n)
for i in range(1, len(group)):
j = i-1
cmp = unsorted_list[group[i]]
while j > -1 and func(unsorted_list[group[j]], cmp, reversed):
unsorted_list[group[j+1]], unsorted_list[group[j]] = unsorted_list[group[j]], cmp
j -= 1
print("NO.%d:" % num, unsorted_list)
n /= 2
num += 1
print("last:", unsorted_list)
return unsorted_list
def selectSort(unsorted_list, reversed=False):
'''
每一趟从待排序的数据元素中选出最小（最大）的元素，
顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。
一共需要 n-1 趟
'''
print("raw: ", unsorted_list)
for loc in range(len(unsorted_list)-1):
for i in range(loc, len(unsorted_list)):
if func(unsorted_list[loc], unsorted_list[i], reversed):
unsorted_list[i], unsorted_list[loc] = unsorted_list[loc], unsorted_list[i]
print("NO.%d:" % loc, unsorted_list)
print("last:", unsorted_list)
return unsorted_list
def heapSort(unsorted_list, reversed=False):
'''
堆排序涉及到的概念
- 堆排序是利用 堆进行排序的
- 堆是一种完全二叉树
- 堆有两种类型: 大根堆 小根堆
- 两种类型的概念如下：
- 大根堆：每个结点的值都大于或等于左右孩子结点
- 小根堆：每个结点的值都小于或等于左右孩子结点
首先将待排序的数组构造出一个大根堆
取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，
然后把剩下的元素再构造出一个大根堆。
重复第二步，直到这个大根堆的长度为 1，此时完成排序。
例子：
1 2 3 4 5 6 7 8 9 10
[3, 4, 10, 6, 8, 2, 5, 1, 7, 9]
3
4 10
6 8 2 5
1 7 9 x x x x x
规律：
- 如何找到 6 这个节点：(length-1)/2 => (10-1)/2=4
- https://www.jianshu.com/p/d174f1862601
'''
def heap_adjust(L, start, end):
temp = L[start]
i = start
j = 2 * i
while j <= end:
if (j < end) and func(L[j+1], L[j], reversed):
j += 1
if func(L[j], temp, reversed):
L[i], i, j = L[j], j, 2*j
else:
break
L[i] = temp
print("raw: ", unsorted_list)
unsorted_list.insert(0, 0)
L_length = len(unsorted_list) - 1
first_Sort_count = L_length / 2
for i in range(first_Sort_count):
heap_adjust(unsorted_list, first_Sort_count - i, L_length)
print("Heap:", unsorted_list[1:])
for i in range(L_length - 1):
unsorted_list[1], unsorted_list[L_length -
i] = unsorted_list[L_length - i], unsorted_list[1]
heap_adjust(unsorted_list, 1, L_length - i - 1)
print("No.%d:" % i, unsorted_list[1:])
unsorted_list.pop(0)
print("last:", unsorted_list)
return unsorted_list
def bubbleSort(unsorted_list, reversed=False):
'''
S1：从待排序序列的起始位置开始，从前往后依次比较各个位置和其后一位置的大小并执行 S2。
S2：如果当前位置的值大于其后一位置的值，就把他俩的值交换
（完成一次全序列比较后，序列最后位置的值即此序列最大值，所以其不需要再参与冒泡）。
S3：将序列的最后位置从待排序序列中移除。若移除后的待排序序列不为空则继续执行 S1，否则冒泡结束。
'''
print("raw: ", unsorted_list)
num = 0
while len(unsorted_list)-num:
for i in range(0, len(unsorted_list)-num-1):
if func(unsorted_list[i], unsorted_list[i+1], reversed):
unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]
print("No.%d:" % num, unsorted_list)
num += 1
print("last:", unsorted_list)
def quickSort(unsorted_list, base_loc=0, reversed=False):
'''
快速排序是对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此实现整个数据变成有序序列。
'''
print("raw: ", unsorted_list)
num = [0]
def _sort(l, r):
if l < r:
if num[0]:
print("No.%d:" % num[0], unsorted_list)
num[0] += 1
if base_loc:
q = partition_final(unsorted_list, l, r)
else:
q = partition_first(unsorted_list, l, r)
_sort(l, q - 1)
_sort(q + 1, r)
def partition_final(unsorted_list, l, r):
x = unsorted_list[r]
i = l - 1
for j in range(l, r):
if x > unsorted_list[j]:
i += 1
unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
unsorted_list[i+1], unsorted_list[r] = unsorted_list[r], unsorted_list[i+1]
return i+1
def partition_first(unsorted_list, l, r):
x = unsorted_list[l]
i = r + 1
for j in range(r, l, -1):
if x < unsorted_list[j]:
i -= 1
unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
unsorted_list[i-1], unsorted_list[l] = unsorted_list[l], unsorted_list[i-1]
return i-1
_sort(0, len(unsorted_list)-1)
print("last:", unsorted_list)
def mergeSort(unsorted_list, reversed=False):
'''
合并两个已排序好的列表，产生一个新的已排序好的列表
归并排序的算法我们通常用递归实现。
先把待排序区间[s,t]以中点二分，接着把左边子区间排序，
再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
'''
print("raw: ", unsorted_list)
def _sort(unsorted_list):
if len(unsorted_list) <= 1:
return unsorted_list
mid = len(unsorted_list) / 2
left = _sort(unsorted_list[:mid])
right = _sort(unsorted_list[mid:])
result = merge(left, right)
return result
def merge(left, right):
result = []
left = left[::-1]
right = right[::-1]
while left and right:
left_num = left.pop()
right_num = right.pop()
if func(right_num, left_num, reversed):
result.append(left_num)
right.append(right_num)
else:
result.append(right_num)
left.append(left_num)
return result+left[::-1]+right[::-1]
unsorted_list = _sort(unsorted_list)
print("last:", unsorted_list)
return unsorted_list
def bucketSort(unsorted_list, reversed=False):
'''
桶排序
'''
print("raw: ", unsorted_list)
buckets = [0] * ((max(unsorted_list)-min(unsorted_list))+1)
for num in unsorted_list:
buckets[num-min(unsorted_list)] += 1
unsorted_list = sum([[i+min(unsorted_list)]*num for i, num in enumerate(buckets)], [])
print("last:", unsorted_list)
def radixSort(unsorted_list, reversed=False):
'''
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
'''
import math
for i in range(int(math.log10(max(unsorted_list)))+1):
bucket = [[] for _ in range(10)]
for val in unsorted_list:
bucket[int(val % (10 ** (i+1)) / (10 ** i))].append(val)
unsorted_list = sum(bucket, [])
if reversed:
unsorted_list = unsorted_list[::-1]
print(unsorted_list)
return unsorted_list
unsorted_list = range(10, 0, -1)
random.shuffle(unsorted_list)
|
