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

这篇文章主要介绍了python实现希尔排序，已编程实现的希尔排序，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

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<=index<dk
 # index = index - dk
 # if 0<=index and index <dk:
 # break

 # position>index,要插入的数的下标必须得大于第一个下标
 while position > index and current_val < array[position-dk]:
 array[position] = array[position-dk] # 往后移动
 position = position-dk
 else:
 array[position] = current_val


def ShellSort(array, len_array): # 希尔排序
 dk = int(len_array/2) # 增量
 while(dk >= 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)) 

while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk
 index = index - dk
 if 0<=index and index <dk:
 break 

j = int(index / dk) # index与dk的商
index = index - j * dk 

时间复杂度:

希尔排序的时间复杂度是所取增量序列的函数，尚难准确分析。有文献指出，当增量序列为d[k]=2^(t-k+1)时，希尔排序的时间复杂度为 O(n^1.5), 其中t为排序趟数。

稳定性: 不稳定

希尔排序效果:

参考资料: 编程是我自己实现的。建议Debug看看运行过程

c++中八大排序算法

视觉直观感受若干常用排序算法

C#七大经典排序算法系列（下）

1.非系统的学习也是在浪费时间 2.做一个会欣赏美，懂艺术，会艺术的技术人

以上就是python实现希尔排序的实例详解的详细内容，更多请关注Gxl网其它相关文章！

查看更多关于python实现希尔排序的实例详解的详细内容...