C语言数据结构希尔排序算法和简单插入排序算法的对比

小鱼儿 2022-01-22 04:27 177阅读 0赞

/\*  
\*希尔排序 利用增量递减的规则  
\*简单插入排序的进阶版  
\*好处 可以有效降低时间复杂度  
\*希尔排序的核心是利用增量的变化 在简单排序的基础上 降低时间复杂度  
\*和简单插入函数之间进行对比  
\*/

#include<stdio.h>
    #include<stdlib.h>
    void ShellSort(int*s,int length);//希尔排序函数  （核心算法）
    void insert_sort(int *s,int n);//简单插入排序算法
    void main()
    {
        int i;
        int m;
        int n[100];//数组
        printf("请输入数据的个数：\n");
          scanf("%d",&m);
          printf("请依次输入数据:\n");
          for(i=0;i<m;i++)
          {
              scanf("%d",&n[i]);
          }
          printf("\t\t===========希尔排序===========\n");
          ShellSort(n,m);//希尔排序函数
            for(i=0;i<m;i++)
            {
                printf("%d\t",n[i]);
            }
           printf("\n");//换行
             printf("\t\t========简单插入排序===========\n");
                insert_sort(n,m);
              for(i=0;i<m;i++)
            {
                printf("%d\t",n[i]);
            }
    }
    void ShellSort(int*s,int length)//希尔排序函数  （核心算法）
    {
        int increment;//增量值
        int i,j;
        int temp;//中间值
        for(increment=length/2;increment>0;increment/=2)//控制增量的规律变化
           for(i=increment;i<length;i++)//利用增量的规则变化 继续使用简单插入排序
        {
            temp=s[i];
            for(j=i-increment;j>=0&&temp<s[j];j-=increment)//递增排序
            {
                s[j+increment]=s[j];
            }
            s[j+increment]=temp;
    
        }
    }
    //简单的插入排序
    void insert_sort(int *s,int n)
    {
        int temp;
        int i,j;
        for(i=1;i<n;i++)//递减排序
        {
            temp=s[i];
              for(j=i-1;j>=0&&temp>s[j];j--)
              {
                  s[j+1]=s[j];
              }
              s[j+1]=temp;
        }
    
    }