数据结构实验之排序六：希尔排序

爱被打了一巴掌 2022-05-16 01:44 174阅读 0赞

### 算法内容转载自：**[https://blog.csdn.net/weixin\_37818081/article/details/79202115][https_blog.csdn.net_weixin_37818081_article_details_79202115]** ###

## 1，有关插入排序 ##

（1）*插入排序的**基本方法**是：每步将一个待排序的元素，按其排序码大小插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。*  
（2）*可以**选择不同的方法**在已经排好序的有序数据表中寻找插入位置，依据查找方法的不同，有多种插入排序方法。下面是常用的三种。*  
1>**直接插入排序**  
2>**折半插入排序**  
3>**希尔排序**  
（3）直接插入排序**基本思想**：当插入第i（i>1）个元素时，前面的data\[0\],data\[1\]……data\[i-1\]已经排好序。这时用data\[i\]的排序码与data\[i-1\],data\[i-2\],……的排序码顺序进行比较，找到插入位置即将data\[i\]插入，原来位置上的元素向后顺序移动。  
（4）折半插入排序**基本思想**：设元素序列data\[0\],data\[1\],……data\[n-1\]。其中data\[0\],data\[1\],……data\[i-1\]是已经排好序的元素。在插入data\[i\]时，利用**折半搜索法**寻找data\[i\]的插入位置。  
（5）希尔排序的过程相比前两种有些不同，下面我们主要介绍希尔排序的过程实现。

## 2，希尔排序 ##

（1）*希尔排序（shell sort）这个排序方法又称为**缩小增量排序**，是1959年D·L·Shell提出来的。该方法的**基本思想**是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。*  
（2）*由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。*  
（3）希尔排序举例：  
1>下面给出一个数据列：  
![这里写图片描述][SouthEast]  
2>第一趟取increment的方法是：n/3向下取整+1=3（关于increment的取法之后会有介绍）。将整个数据列划分为间隔为3的3个子序列，然后对每一个子序列执行直接插入排序，相当于对整个序列执行了部分排序调整。图解如下：  
![这里写图片描述][SouthEast 1]  
3>第二趟将间隔increment= increment/3向下取整+1=2，将整个元素序列划分为2个间隔为2的子序列，分别进行排序。图解如下：  
![这里写图片描述][SouthEast 2]  
4>第3趟把间隔缩小为increment= increment/3向下取整+1=1，当增量为1的时候，实际上就是把整个数列作为一个子序列进行插入排序，图解如下：  
![这里写图片描述][SouthEast 3]  
5>直到increment=1时，就是对整个数列做最后一次调整，因为前面的序列调整已经使得整个序列部分有序，所以最后一次调整也变得十分轻松，这也是希尔排序性能优越的体现。

举个栗子：[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2572/pid/3403][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2572_pid_3403]

AC代码如下：

#include<bits/stdc++.h>
    using namespace std;
    int n,a[11234];
    void shell(int dk)
    {
        int temp;
        int j;
        for(int i=dk;i<n;i++)
        {
            temp=a[i];
            for(j=i;j>=dk&&a[j-dk]>temp;j-=dk)
                a[j]=a[j-dk];
            a[j]=temp;
        }
        for(int i=0;i<n;i++)
        {
            if(i==n-1)
                cout<<a[i]<<endl;
                else
                    cout<<a[i]<<' ';
    
        }
    }
    int main()
    {
        while(cin>>n)
        {
            memset(a,0,sizeof(a));
            for(int i=0;i<n;i++)
                cin>>a[i];
            shell(n/2);
            shell(1);
        }
    }

[https_blog.csdn.net_weixin_37818081_article_details_79202115]: https://blog.csdn.net/weixin_37818081/article/details/79202115
[SouthEast]: /images/20220516/22a892f261e943a2b06f27eca9108751.png
[SouthEast 1]: /images/20220516/4423175fbc954f09a8870cb778a4f3ed.png
[SouthEast 2]: /images/20220516/65a0bf55f5c142dcbd192c7365629527.png
[SouthEast 3]: /images/20220516/b924b6536d2647a188ab9d07ff233074.png
[https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2572_pid_3403]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2572/pid/3403