这篇文章主要介绍了python实现希尔排序，已编程实现的希尔排序，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
观察一下”插入排序“：其实不难发现她有个缺点：
如果当数据是”5, 4, 3, 2, 1“的时候，此时我们将“无序块”中的记录插入到“有序块”时，估计俺们要崩盘，每次插入都要移动位置，此时插入排序的效率可想而知。
shell根据这个弱点进行了算法改进，融入了一种叫做“缩小增量排序法”的思想，其实也蛮简单的，不过有点注意的就是：
增量不是乱取，而是有规律可循的。
立即学习“Python免费学习笔记（深入）”；
希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。
首先要明确一下增量的取法(这里图片是copy别人博客的，增量是奇数，我下面的编程用的是偶数)：
第一次增量的取法为： d=count/2;
第二次增量的取法为: d=(count/2)/2;
最后一直到: d=1;
好，注意看图了，第一趟的增量d1=5, 将10个待排记录分为5个子序列，分别进行直接插入排序，结果为(13, 27, 49, 55, 04, 49, 38, 65, 97, 76)
第二趟的增量d2=3, 将10个待排记录分为3个子序列，分别进行直接插入排序，结果为(13, 04, 49, 38, 27, 49, 55, 65, 97, 76)
第三趟的增量d3=1, 对整个序列进行直接插入排序，最后结果为(04, 13, 27, 38, 49, 49, 55, 65, 76, 97)
重点来了。当增量减小到1时，此时序列已基本有序，希尔排序的最后一趟就是接近最好情况的直接插入排序。可将前面各趟的"宏观"调整看成是最后一趟的预处理，比只做一次直接插入排序效率更高。
本人是学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<=indexindex,要插入的数的下标必须得大于第一个下标 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))
输出:
>: [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]
首先你得先会插入排序，不会你必然看不懂。
bee餐饮点餐外卖小程序是针对餐饮行业推出的一套完整的餐饮解决方案，实现了用户在线点餐下单、外卖、叫号排队、支付、配送等功能，完美的使餐饮行业更高效便捷！功能演示：1、桌号管理登录后台，左侧菜单 “桌号管理”，添加并管理你的桌号信息，添加以后在列表你将可以看到 ID 和 密钥，这两个数据用来生成桌子的二维码2、生成桌子二维码例如上面的ID为 308，密钥为 d3PiIY，那么现在去左侧菜单微信设置
插入排序，即是对上图三个黄色框中的数进行插入排序。举个例子：13，55，38，76
直接看55，55
这里有个问题，比如第二个黄色框[27，4，65]，4但是计算机怎么知道4就是在第一个啊??
我的做法是，先找出[27，4，65]第一个数的下标，在这个例子中27的下标为1。当要插入的数的下标大于第一个下标1时，才可以往后移，前一个数不可以往后移有两种情况，一种是前面有数据，且小于要插入的数，那你只能插在它后面。另一种，很重要，当要插入数比前面所有数都小时，那插入数肯定是放在第一个，此时要插入数的下标＝第一个数的下标。(这段话，感觉初学者应该不大懂……)
为了找到第一个数的下标，最开始想的是用循环，一直到最前面:
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为排序趟数。
稳定性: 不稳定
希尔排序效果:
参考资料: 编程是我自己实现的。建议Debug看看运行过程
c++中八大排序算法
视觉直观感受若干常用排序算法
C#七大经典排序算法系列（下）
1.非系统的学习也是在浪费时间 2.做一个会欣赏美，懂艺术，会艺术的技术
