图片化加手动推导深刻记忆希尔排序全过程

希尔排序原理：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，最后在基本有序后最后做一次直接插入排序。

时间复杂度：O(nlogn) 最坏是O(n ** s)(1<s<2) 不稳定的排序方法；

空间复杂度：O(1)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jul 18 03:42:18 2019

@author: honorwh
"""
#希尔排序
def ShellSort(A):
    count = len(A)
    step = count // 2
    while step > 0:
        for i in range(0, step):
            j = i + step
            while j < count:
                k = j - step
                key = A[j]
                while k >= 0:
                    if A[k] > key:
                        A[k + step] = A[k]
                        A[k] = key
                    k -= step
                j += step
        step //= 2
    return A
A = [3, 4, 2, 8, 9, 5, 1]
A = ShellSort(A)
print(A)

希尔排序有个重点是对于增量（increment）的选择，这里选择是step = len(A) // 2, step //= 2

结合以上图片给出每一步的数值转移：

A = [3, 4, 2, 8, 9, 5, 1]

3 4 2 8 9 5 1(以step = len(A) // 2为步长) 第一次比较的是3 8；8 1; 3 1

即3 4 2 8 9 5 1 --> 3 4 2 1 9 5 8 --> 1 4 2 3 9 5 8

所以，1 4 2 3 9 5 8是第一次比较的结果；同理，在以step = len(A) // 2的步长比较之后，step //= 2

即第二次（在本例已经是最后一次，因为step = 1），所以同理即可得到结果。

这个编辑比较麻烦，有兴趣可以自己每一步的详细过程推一推，更容易理解。