[DS+Algo] 007 希尔排序及其代码实现

步骤

将数组列在一个表（一行多列）中，按特定的步长进行插入排序
步长从 length/2 到 1，每次除 2
将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序

算法性能

（根据步长序列的不同而不同）
最优时间复杂度：O(n^1.3)
最坏时间复杂度：O(n²)
稳定想：不稳定

Python 代码示例

def shell_sort(lst):

    n = len(lst)

    gap = n // 2

    while gap > 0:

        for i in range(gap, n, gap):

            while gap <= i and lst[i] < lst[i-gap]:

                lst[i], lst[i-gap] = lst[i-gap], lst[i]

                i -= gap

        gap //= 2

if __name__ == "__main__":

    lst = [randrange(10, 100) for _ in range(10)]

    print(">>> before sort:", lst)

    shell_sort(lst)

    print(">>> after sort :", lst)

巴特西

[DS+Algo] 007 希尔排序及其代码实现

步骤

算法性能

Python 代码示例

最新文章

热门文章