>: [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]
首先你得先会插入排序，不会你必然看不懂。
插入排序，即是对上图三个黄色框中的数进行插入排序。举个例子：13，55，38，76
直接看55，55<13, 不用移动。接着看38，38<55，那么55后移，数据变为[13，55，55，76]，接着比较13<38, 那么38替换55，变成[13，38，55，76]。其它同理，略。
这里有个问题，比如第二个黄色框[27，4，65]，4<27, 那27往后移，接着4就替换第一个，数据变成[4，27，65]，但是计算机怎么知道4就是在第一个啊??
我的做法是，先找出[27，4，65]第一个数的下标，在这个例子中27的下标为1。当要插入的数的下标大于第一个下标1时，才可以往后移，前一个数不可以往后移有两种情况，一种是前面有数据，且小于要插入的数，那你只能插在它后面。另一种，很重要，当要插入数比前面所有数都小时，那插入数肯定是放在第一个，此时要插入数的下标＝第一个数的下标。(这段话，感觉初学者应该不大懂……)
为了找到第一个数的下标，最开始想的是用循环，一直到最前面:
1 2 3 4
while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk index = index - dk if 0<=index and index <dk: break
在Debug时，发现用循环太浪费时间了，特别是当增量d=1时，直接插入排序为了插入列表最后一个数，得循环减1，直到第一个数的下标，后来我学聪明了，用下面的方法:
1 2
j = int(index / dk) # index与dk的商 index = index - j * dk
时间复杂度:
希尔排序的时间复杂度是所取增量序列的函数，尚难准确分析。有文献指出，当增量序列为d[k]=2^(t-k+1)时，希尔排序的时间复杂度为O(n^1.5), 其中t为排序趟数。
稳定性: 不稳定
希尔排序效果:
