[数据结构与算法]python排序算法（六）、希尔排序

插入排序：

假如有一个列表[5, 7, 4, 6, 3, 1, 2, 9, 8]，将此列表当作桌子上的牌，最开始我们手里有一张牌5， 此时我们依次从剩余的牌[7, 4, 6, 3, 1, 2, 9, 8]中摸出牌来与手中的牌进行对比，手里的牌只要大于摸到的牌则往右走，最后将摸到的牌插入到合适的位置

插入排序代码：

def insert_sort(li):
    for i in range(1, len(li)):  # i 代表我即将摸到牌的下标[7, 4, 6, 3, 1, 2, 9, 8]
        tmp = li[i]  # 代表我当前摸到的牌
        k = i - 1  # 表示我现在手里的牌的数量[0 - k]
        while k >= 0 and li[k] > tmp:  # 循环从右遍历手里的牌，如果当前手里的牌大于摸到的牌，则将手里的牌放到摸到的牌的位置
            li[k + 1] = li[k]
            k -= 1
        li[k + 1] = tmp # 最后对比完手里的牌将摸到的牌放到合适的位置

而希尔排序（shell Sort）是一种分组插入排序算法。

希尔排序的具体思路步骤：(n等于列表的长度)

• 首先取一个整数d1 = n // 2 ，将元素分为d1个组，每组相邻元素之间的距离为d1,在各组内进行插入排序
• 取第二个整数d2 = d1 // 2 ，重复上述分组排序，则到di =1时，即所有元素在同一组内进行插入排序即可完成排序
• 希尔排序每趟并不是使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序

这里取列表 [5, 7, 4, 6, 3, 1, 2, 9, 8]?

第一次分组d1 = 9 // 2 = 4 ，分成4组，依次对[5, 3, 8],? [7, 1],? [4,2], [6,9] 进行插入排序? ? ? ? ?

这里我们可以将 5，7，4，6看成手里的牌， 即将摸到的牌为 3，1，2，9，8。5与3比较，7与1比较，4 与 2 比较， 6 与 9 比较。元素之间间隔4个下标。 依次下一列比较

第一次分组插入排序后：[3, 1, 2, 6, 5, 7, 4, 9, 8]

第二次分组 d2 = d1 // 2 =2, 依次对[3,2,5,4,8]、[1,6,7,9]进行插入排序

第二次分组插入排序后：[ 2,1,3,6,4,7,5,9,8 ]

第三次分组 d3 = d2 // 2 =1 则对?[ 2,1,3,6,4,7,5,9,8 ]进行插入排序，排序后[1, 2, 3, 4, 5, 6, 7, 8, 9]

代码?

def insert_sort_gap(li, gap): # gap 代表分成机组
    for i in range(gap, len(li)):
        tmp = li[i]  # 第一组中即将摸的牌
        k = i - gap  # 第一组中手里有的牌
        while k >= 0 and li[k] > tmp:  # 摸到的牌大于手里的牌
            li[k + gap] = li[k] # 手里的牌交换到摸到的牌的位置
            k -= gap
        li[k + gap] = tmp # 将摸到的牌放到合适的位置
    print(li)


def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2


li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
shell_sort(li)
print(li)

插入排序和希尔排序对比

import random
import time
import copy


def cal_time(func):
    def inner(*args, **kwargs):
        strat = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print('%s执行时间:%s' % (func.__name__, end - strat))
        return result

    return inner


@cal_time
def insert_sort(li):
    for i in range(1, len(li)):  # i 代表我即将摸到牌的下标[7, 4, 6, 3, 1, 2, 9, 8]
        tmp = li[i]  # 代表我当前摸到的牌
        k = i - 1  # 表示我现在手里的牌的数量[0 - k]
        while k >= 0 and li[k] > tmp:  # 循环从右遍历手里的牌，如果当前手里的牌大于摸到的牌，则将手里的牌放到摸到的牌的位置
            li[k + 1] = li[k]
            k -= 1
        li[k + 1] = tmp  # 最后对比完手里的牌将摸到的牌放到合适的位置


def insert_sort_gap(li, gap):  # gap 代表分成机组
    for i in range(gap, len(li)):
        tmp = li[i]  # 第一组中即将摸的牌
        k = i - gap  # 第一组中手里有的牌
        while k >= 0 and li[k] > tmp:  # 摸到的牌大于手里的牌
            li[k + gap] = li[k]  # 手里的牌交换到摸到的牌的位置
            k -= gap
        li[k + gap] = tmp  # 将摸到的牌放到合适的位置
    # print(li)


@cal_time
def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2


#
# li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
# shell_sort(li)
# print(li)
li = list(range(10000))
random.shuffle(li)

li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)

shell_sort(li1)
insert_sort(li2)

# 结果
shell_sort执行时间:0.013513565063476562
insert_sort执行时间:1.416457176208496

插入排序的时间复杂度为：O（n2）

希尔排序的时间复杂度为：

? ? ? ? 最坏：O（n2）

? ? ? ? 平均情况：O(n2) -- O(n)