算法札记9——希尔排序

希尔排序

思想

希尔排序是插入排序的一种，也称之为缩小增量排序。希尔排序是非稳定排序算法，实现过程：

• 将记录按照下标的一定增量进行分组，对每个组进行插入排序
• 增量逐渐减少，当减少至1时，算法终止

栗子

假设步长为step，对[1, 8, 2, 9, 3, 7, 4, 6, 5]进行排序，步长一般是按照折半进行选取

• 步长取4：对[1, 3, 5],[8, 7],[2, 4],[9, 6]，对每个子序列分别进行插入排序
• 步长取2：对上述排序的序列，再按照类似的方法进行排序
• 步长取1：重复操作

时间复杂度

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

代码实现

def shell_sort(alist):

    # 希尔排序：核心是插入排序

    n = len(alist)

    # 折半：取整数解，防止小数:n=9,step=4

    step = n // 2

    i = 1

    

    # 步长变化到0之前即1，插入算法执行的次数 

    while step > 0:

        # 插入算法：与普通插入算法的区别就是步长step

        for j in range(step, n):

            # j = gap, gap+1, ..., n-1

            i = j

            while i > 0:

                if alist[i] < alist[i-step]:

                    # 比较的两个数下标相差为步长step

                    alist[i], alist[i-step] = alist[i-step], alist[i]

                    i -= step

                else:

                    break

        # 一个for循环结束则缩短步长step

        step //= 2

        

    return alist