算法笔记(九):希尔排序和桶排序

2018-11-20 03:25:09来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

(一)希尔排序

先将整个待排记录序列分割成若干个子序列,然后分别进行直接插入排序,待整个序列中的数据基本有序时,再对全体记录进行一次直接插入排序。具体做法是:

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))

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Pyhon 中文编码问题(字符串前加‘U’)

下一篇:pandas数据结构之series操作