算法-排序算法：希尔排序（Shell Sort）【O(n^2)】

逃离我推掉我的手 2023-10-04 04:50 10阅读 0赞

**希尔排序**（Shell Sort）：1959年Shell发明，第一个突破O(n2)的排序算法，是**插入排序的改进版**。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫**缩小增量排序**。

## 一、希尔排序-算法描述： ##

先将整个待排序的序列A按照一个“增量”(gap)分割成为若干子序列，然后分别进行直接插入排序，具体算法描述：

*  选择一个增量序列(gap 序列)  t 1 , t 2 , … , t i , t j , … , 1 \{t\_1, t\_2, …, t\_i, t\_j, …,1\} t1,t2,…,ti,tj,…,1，其中ti>tj，此增量序列元素总数为n；
 *  按增量序列(gap序列)元素总数n，对序列进行n趟“直接插入排序”；
 *  每趟排序，根据对应的增量(gap=ti)，将待排序列分割成若干长度为m 的子序列，分别对子序列进行直接插入排序。仅增量因子为1(gap=1) 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

## 二、希尔排序-过程分析 ##

*  在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这一系列增量选择我们可以用一个序列来表示，\{n/2,(n/2)/2…1\}，称为增量序列。
 *  希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为**希尔增量**，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

## 三、希尔排序-动图演示 ##

![在这里插入图片描述][20201027110211884.gif_pic_center]  
![在这里插入图片描述][20210430161403200.gif_pic_center]

## 四、希尔排序-代码实现 ##

def shell_sort(alist):
        n = len(alist)
        # 初始步长
        gap = n // 2
        while gap > 0:
            # 插入排序，与普通的插入排序的区别就是gap步长替代1
            for i in range(gap, n):
                j = i
                # 插入排序
                while j >= gap and alist[j - gap] > alist[j]:
                    alist[j - gap], alist[j] = alist[j], alist[j - gap]
                    j -= gap
            # 缩短gap步长，得到新的步长
            gap = gap // 2
    
    
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shell_sort(alist)
    print(alist)

## 五、希尔排序-时间复杂度 ##

*  最优时间复杂度：O(n1.3)
 *  最坏时间复杂度：O(n2) ，此时gap就直接取1
 *  稳定想：不稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020102710311759.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20201027110211884.gif_pic_center]: https://img-blog.csdnimg.cn/20201027110211884.gif#pic_center
[20210430161403200.gif_pic_center]: https://img-blog.csdnimg.cn/20210430161403200.gif#pic_center