Python实现希尔排序

标签: 希尔  排序  Python    算法

希尔排序简介
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,也称分组插入排序。
希尔排序原理:
1、第1次希尔,两两分组,根据队列元素个数获取组内元素之间的偏移量
分组方式是:0-4、1-5、2-6、3-7
也就是说:i和i+4是一组,4称为下标偏移量
2、对组内元素间进行插入排序(即元素替换)
3、第2次希尔,四四一组,组内插入排序。即组内元素间偏移量是上一次标偏移量/2
分组方式:0-2-4-6、1-3-5-7
4、第3次希尔,八八一组,组内插入排序。偏移量同上
5、循环下去,直到所有元素为一组(即组内元素下标偏移量为1)。
一句话:
两两一组、四四一组、八八一组...,直到所有元素为一组,进行排序
特点:
下标增量分组,对小组元素进行插入排序
下标增量的特点:
第一次分组,gap=n/2 ,
从第二次分组,gap=gap/2,
最后一次分组gap=1
    整个分组过程就是:递归
示意图
原始队列:

第一次分组和插入排序:
分组特点:下标+4 为一组

第一次分组和插入排序后效果:

第二次分组和插入排序:
分组特点:下标+2 为一组

第二次分组和插入排序后效果:

第三次分组和插入排序:
分组特点:下标+1 为一组

最终排序效果:

整体感觉就是一个词:折腾
但是操作完毕后,我们隐隐的感觉到一个字,爽!!!
比如说:
插入排序:将队列末尾的17放到最前面,需要先进行7次循环,在第8次循环中,进行7次比较替换操作
希尔排序:将队列末尾的17放到最前面,需要先进行2次循环,在第3次循环中,进行1次比较替换操作

通过分析,整个希尔排序过程包括如下内容:
1、分组队列中元素比较替换                                  即"元素替换"
2、每次分组后,同时有几组在进行比较                即"比较次数"
3、需要进行多少次分组                                         即"分组次数"

def shell_sort(alist):
    n = len(alist)
    # 让步长从大变小,最后一步必须是1,获取gap的偏移值
    gap = n // 2
    # 只要gap在我们的合理范围内,就一直分组下去
    while gap >= 1:
        # 按照步长把数据分两半,从步长的位置遍历后面所有的数据,指定j下标的取值范围
        for j in range(gap, n):
            # 拿当前位置的数据,跟当前位置-gap 位置的数据进行比较
            while j-gap >= 0:
                # 组内大小元素进行替换操作
                if alist[j]<alist[j-gap]:
                    alist[j], alist[j - gap] = alist[j - gap], alist[j]
                    # 更新迁移元素的下标值为最新值
                    j -= gap
                else:
                    # 否则的话,不进行替换
                    break

        # 每执行完毕一次分组内的插入排序,对gap进行/2细分
        gap //= 2


if __name__ == '__main__':
    alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
    print(alist)
    shell_sort(alist)
    print(alist)

# 稳定性: 不稳定
# 时间复杂度:跟步长有关

关键点:    
    1、元素替换:
        下标范围:while (i - gap) >= 0:
        替换条件:if alist[i] < alist[i-gap]:
        过程跟踪:i = i - gap
    2、比较循环:
        元素的范围:for i in range(gap,n):
    3、递归分组循环
        偏移量初始值:gap = n // 2
        递归循环的退出条件:while gap >= 1
        gap偏移量规律:gap = gap // 2
时间复杂度
最优时间复杂度:根据步长序列的不同而不同
最内部的元素进行插入排序,我们知道插入排序的最优时间复杂度是O(n)
外部分组遇到了递归拆分,那么我们知道递归拆分的时间复杂度是O(logn)。
整体来说:最优的时间复杂度是 O(nlogn)
然而分组/2是一种情况,如果分组直接分成最细的粒度,也就是说每一个元素都是一个组,所以外部的时间复杂度就变成了是O(n)
所以整体时间复杂度就变成了O(n2)
结合两个方面:最优时间复杂度就是 O(nlogn)~O(n2)
最坏时间复杂度:O(n2)
我们知道希尔排序的本质就是插入排序,所以最坏也就是插入排序的最坏时间复杂度了,也就是O(n2)
稳定性:不稳定

本节内容小结:
1、希尔排序原理:两两-四四-八八-...-所有元素,插入排序。
2、希尔排序实践步骤:组内插入-一次希尔次数-希尔递归循环-异常考虑

 

 

 

 

 

 

 

 

 

 

 

 

 

原文链接:加载失败,请重新获取