希尔排序 ALDS1_2_D

拼搏现实的明天。 2023-03-04 08:24 4阅读 0赞

这个算法实现起来花了一些时间，主要错误出在临近问题上，有运行时错误调试了不短的时间。

这个算法对比之前的几类算法，运行复杂度是都有所降低，如果去g=3\*g+1，这个算法的复杂度维持在O(N^1.25)左右，对比之下，这是一个高效的算法，十分值得学习与借鉴。

有利于对数据进行灵活的排序处理

#include <iostream>
    #include <cstdio>
    #include <vector>
    
    using namespace std;
    
    const int max_n=1e6;
    
    int a[max_n];
    int n,m,cnt;
    
    vector<int> G;
    
    void Insert_sort(int g)
    {
        
        for(int i=g;i<n;++i)
        {
        
            int tmp=a[i];
            int j;
            for(j=i-g;j>=0 && tmp<a[j];j-=g)
            {
        
                a[j+g]=a[j];
                ++cnt;
            }
            a[j+g]=tmp;
        }
    }
    
    void Shell_sort()
    {
        
        // 首先,要生成数列G.
        int g=1;
        m=0;
        while(g<=n)
        {
        
            G.push_back(g);
            ++m;
            g=3*g+1;
        }
    
        cnt=0;
        for(int i=G.size()-1;i>=0;--i)
        {
        
            Insert_sort(G[i]);
        }
    }
    
    
    int main()
    {
        
        // 输入数据
        scanf("%d",&n);
        for(int i=0;i<n;++i)
        {
        
            scanf("%d",&a[i]);
        }
        // 希尔排序
        Shell_sort();
    
        printf("%d\n",m);
        for(int i=m-1;i>0;--i)
        {
        
            printf("%d ",G[i]);
        }
        printf("%d\n",G[0]);
    
        printf("%d\n",cnt);
        for(int i=0;i<n;++i)
        {
        
            printf("%d\n",a[i]);
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关希尔排序 ALDS1_2_D

这个算法实现起来花了一些时间，主要错误出在临近问题上，有运行时错误调试了不短的时间。这个算法对比之前的几类算法，运行复杂度是都有所降低，如果去g=3\g+1，这个算法的复杂

拼搏现实的明天。/ 2023年03月04日 08:24/ 0 赞/ 5 阅读

相关排序——希尔排序

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_si

缺乏、安全感/ 2022年09月10日 11:22/ 0 赞/ 234 阅读

相关希尔排序

希尔排序算法描述：希尔排序也叫“缩小增量排序”，是由shell创立，也是插入排序的一种变异。每次设置一定的步长，一般设置delta=Array.leng

柔光的暖阳◎/ 2022年05月27日 23:46/ 0 赞/ 203 阅读

相关排序——希尔排序

排序——希尔排序 include <iostream> using namespace std; void shell_sort(int a

男娘i/ 2022年05月21日 12:05/ 0 赞/ 282 阅读

相关希尔排序

希尔排序也是基于插入排序的一种策略，两个代码相似插入排序： include <stdio.h> int main(){ int a[]={1,1

布满荆棘的人生/ 2022年02月20日 15:09/ 0 赞/ 309 阅读

相关希尔排序

希尔排序希尔排序像是插入排序的升级版把数组分组以后再进行插入排序分组的次数是:increasement=sizeof(arr)/3+1 分组排序以后序列

待我称王封你为后i/ 2022年02月04日 08:53/ 0 赞/ 290 阅读

相关希尔排序

之前一直只了解希尔排序的过程，没具体写过代码，今天补上。基本思路： 1.选定步长gap,比较元素a\[i\]和a\[i+gap\]的大小，并调整顺序，逐步调整gap值

灰太狼/ 2021年09月26日 14:52/ 0 赞/ 407 阅读

相关希尔排序

插入排序的问题 ![18721752-7da6fa07c682dd24.png][] image.png Introduce ![18721752-13b82d

刺骨的言语ヽ痛彻心扉/ 2021年09月18日 07:10/ 0 赞/ 451 阅读

相关希尔排序

希尔排序： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L

亦凉/ 2021年09月17日 00:14/ 0 赞/ 414 阅读

相关希尔排序

一算法一个由h个有序子数组组成的数组。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

布满荆棘的人生/ 2021年07月24日 17:06/ 0 赞/ 512 阅读