(一)希尔排序
先将整个待排记录序列分割成若干个子序列,然后分别进行直接插入排序,待整个序列中的数据基本有序时,再对全体记录进行一次直接插入排序。具体做法是:
1) 算出增量序列
2) 根据增量序列对待排记录进行直接插入排序
1 #希尔排序
2 def shellSort(A):
3 k = len(A)
4 incremental = []
5 #算出增量序列
6 while (k > 1):
7 k = k // 2
8 incremental.append(k)
9 dk = 0 #增量序列incremental的初始索引值
10 while(dk < len(incremental)):
11 #根据增量序列对列表进行插入排序
12 for i in range(0,len(A),incremental[dk]) :
13 key = A[i]
14 j = i - incremental[dk]
15 while j >= 0 and key < A[j]:
16 A[j+incremental[dk]] = A[j]
17 j -= incremental[dk]
18 A[j+incremental[dk]] = key
19 dk += 1
20 return A
(二)桶排序
1 #桶排序
2 def bucketSort(A):
3 n = max(A)
4 B = [0]* (n+1) #创建新的列表
5 for i in A: #B[i] 的值+1
6 B[i] += 1
7 A = [] #清空列表A
8 #根据列表B,依次输出元素,添加到列表A中
9 for i in range(len(B)):
10 if B[i] != 0 :
11 for k in range(B[i]):
12 A.append(i)
13 return A
14
15
16 A = [1,12,720,328,278,356,789,234,123,113,113,9999,789,999,8999]
17
18 print(bucketSort(A))