python 数据结构与算法 day04 希尔排序

 1. 希尔排序

思路：

希尔排序其实就是插入排序的一种，把原有序列分为gap个子序列，每一个子序列都执行插入排序的操作（是在原有序列上进行） 然后把gap变小，就有会生成gap个子序列，对每一个新的子序列继续执行插入排序操作，gap=1时 其实就是对原有长度序列执行的插入排序；

2. 代码实现

def shell_sort(L):
    """希尔排序"""
    n=len(L)
    gap = int(n/2)
    while gap>0:  # gap:4-->2--->1变化（可以自己设置gap的长度，每次减小）
        for i in range(gap):  # gap=4为例，原有序列会被拆成4个子序列进行处理，每一个子序列进行插入排序 （但是不改变原有序列，只是在原来的基础上进行）
            j=i+gap  # 比如对于第一个子序列，首先需要考虑i=0+4位置的元素，把它放在前面有序序列的哪个位置
            while j<n:
                for k in range(j,0,-gap):  # 就是把需要插入的元素跟前面有序序列的元素进行比较（从后往前） 看把待插入的元素放在哪个位置
                    if L[k]<L[k-gap]:
                        L[k],L[k-gap]=L[k-gap],L[k]
                    else:  # 如果待插入的元素比前面有序序列最后一个位置元素还大 就不需要在进行比较了，待插入元素直接就是放在前面有序序列的最后位置
                        break
                j=j+gap  # 进行下一个待插入元素的比较判断插入操作
        gap=int(gap/2)   # 不断减小gap gap=1其实对应的就是对整个序列进行插入排序的操作
    return L

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

运行结果：

3. 时间复杂度

希尔排序的时间复杂度仍然是O(n^2)  -----因为希尔排序的本质仍然是插入排序；

4. 稳定性

希尔排序是不稳定的，比如gap=4时 产生的四个子序列都需要进行插入排序的操作，如果原序列有两个12 有可能在后面的那个12在第一个子序列中执行完插入排序后排在了最前面，但是 前面的12 在第二个子序列执行插入排序有可能排在了最后，这种情况是跟子序列中其他元素大小相关的，相同的元素 位于后面的有可能在子序列中排在了前面，所以希尔排序是不稳定的~

5.优化（teacher）

自己写的那个代码效率太低（四层循环），其实每取一个gap都会对应产生gap个子序列，没必要分开对gap个子序列分别执行插入排序，可以同时进行，也就是可以挨个对后面的待插入的元素进行比较，但是比较的对象都是基于自身gap个间隔的对象元素~（说起来有点绕，一句话总结就是还跟之前插入排序的思路一样，对后续所有待插入的元素同时进行遍历，原本是1位置开始一直到最后，现在是gap位置开始，一直到最后，原本是对每一个待插入的元素跟前面所有元素进行比较执行插入排序，现在是对每一个带插入排序的元素跟前面相差gap的子序列进行比较执行插入排序！！！）

def shell_sort(L):
    """希尔排序"""
    n=len(L)
    gap=n//2
    while gap>0:  # 把原有序列根据gap间隔划分子序列，对每一个子序列进行插入排序，gap=1就是对原有长度的序列执行一次插入排序
        for i in range(gap,n):  # 首先从gap位置的元素开始，跟前面序列位置元素进行比较（相差gap） 执行插入排序
            for j in range(i,0,-gap):
                if L[j]<L[j-gap]:
                    L[j],L[j-gap]=L[j-gap],L[j]
                else:
                    break
        gap=gap//2
    return L

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

运行结果：