【数据结构】排序算法（三）—— 希尔排序_希尔排序法是怎么排的

作者：从前慢现在也慢 | 2024-04-20 03:41:45

踩

希尔排序法是怎么排的

【数据结构】排序算法（三）—— 希尔排序

一、算法思想

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序。

先将待排序表分割成若⼲形如 $L [i, i + d, i + 2 d, \dots, i + k d]$ 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。

二、算法过程

在这里插入图片描述

第⼀趟： $d_1=n/2=4$

在这里插入图片描述

对上述的四个子表分别进行排序，排序结果图如下：

在这里插入图片描述

第⼆趟： $d_2=d_1/2=2$

在这里插入图片描述
对上述的两个子表分别进行排序，排序结果图如下：

在这里插入图片描述

第三趟： $d_3=d_2/2=1$

当 $d = 1$ 时，整个表已呈现出“基本有序”，对整体再进⾏⼀次“直接插⼊排序”

在这里插入图片描述

过程总结：

在这里插入图片描述

算法实现

//希尔排序
void Shellsort(int A[ ] ,int n){
    int d, i, j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d= n/2; d>=1; d=d/2)
    {//步长变化
        for( i=d+1; i<=n; ++i)
        {
            if(A[i]<A[i-d] ){ //需将A[i]插入有序增量子表
                A[0]=A[i];  //暂存在A[0]
                for(j= i-d; j>0 && A[0]<A[jl; j-=d)
                    A[j+d]=A[j]; //记录后移，查找插入的位置
                A[j+d]=A[0];//插入   
            }//if
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

算法性能分析

在这里插入图片描述

时间复杂度：和增量序列 $d_1, d_2, d_3…$ 的选择有关，⽬前⽆法⽤数学⼿段证明确切的时间复杂度
最坏时间复杂度为 $O(n^2)$ ，当n在某个范围内时，可达 $O(n^1.3)$

在这里插入图片描述

稳定性：不稳定！

在这里插入图片描述

适⽤性：仅适⽤于顺序表，不适⽤于链表

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/455196