python实现希尔排序的实例详解

观察一下”插入排序“：其实不难发现她有个缺点：

　　如果当数据是”5, 4, 3, 2, 1“的时候，此时我们将“无序块”中的记录插入到“有序块”时，估计俺们要崩盘，每次插入都要移动位置，此时插入排序的效率可想而知。

　　shell根据这个弱点进行了算法改进，融入了一种叫做“缩小增量排序法”的思想，其实也蛮简单的，不过有点注意的就是：

增量不是乱取，而是有规律可循的。

def ShellInsetSort(array, len_array, dk): # 直接插入排序
 for i in range(dk, len_array): # 从下标为dk的数进行插入排序
 position = i
 current_val = array[position] # 要插入的数
 index = i
 j = int(index / dk) # index与dk的商
 index = index - j * dk

 # while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=indexindex,要插入的数的下标必须得大于第一个下标
 while position > index and current_val = 1):
 ShellInsetSort(array, len_array, dk)
 print(">>:",array)
 dk = int(dk/2)

if __name__ == "__main__":
 array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
 print(">:", array)
 ShellSort(array, len(array))

输出:

>: [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
>>: [13, 27, 49, 55, 4, 49, 38, 65, 97, 76]
>>: [4, 27, 13, 49, 38, 55, 49, 65, 97, 76]
>>: [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

首先你得先会插入排序，不会你必然看不懂。

while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index
在Debug时，发现用循环太浪费时间了，特别是当增量d=1时，直接插入排序为了插入列表最后一个数，得循环减1，直到第一个数的下标，后来我学聪明了，用下面的方法:

j = int(index / dk) # index与dk的商
index = index - j * dk
时间复杂度:
希尔排序的时间复杂度是所取增量序列的函数，尚难准确分析。有文献指出，当增量序列为d[k]=2^(t-k+1)时，希尔排序的时间复杂度为O(n^1.5), 其中t为排序趟数。
稳定性: 不稳定
希尔排序效果: 
 
c++中八大排序算法
视觉直观感受若干常用排序算法
C#七大经典排序算法系列（下）
1.非系统的学习也是在浪费时间 2.做一个会欣赏美，懂艺术，会艺术的技术人
以上就是python实现希尔排序的实例详解的详细内容，更多请关注 第一PHP社区 其它相关文章！