python注释与代码风格

希尔排序

希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更搞笑的改进版本，希尔排序是非稳定排序算法。

希尔排序过程

希尔排序的基本思想是：将数组列在一个表中并对列分别进行Haru排序，重复这过程，不过没用更长的列来进行，最后整个表就只有一列了，将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n²)
• 稳定性：不稳定

# -*- coding:utf-8 -*-
def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2        # 间距
    while gap > 0:
        # 按步长进行插入排序
        for j in range(gap, n):
            i = j
            while i > 0:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        # 缩短gap步长
        gap //= 2


if __name__ == '__main__':

    li = [2, 4, 6, 2, 45, 34, 12]
    print(li)
    # [2, 4, 6, 2, 45, 34, 12]
    shell_sort(li)
    print(li)
    # [2, 2, 4, 6, 12, 34, 45]

---

转载请注明来源，欢迎指出任何有错误或不够清晰的表达。可以邮件至gxnucgb@qq.com