C语言 通过输出排序次数来比较希尔排序和插入排序的优劣

在程序中出加入计数器来计算两者在执行过程中需要的插入次数

通过比较时间复杂度来比较效率

int shell(int a[],int n,int gap)
{
    int count=0;
    int key=a[n];
    while(n>=gap&&a[n-gap]>key)
    {
        a[n]=a[n-gap];
        n-=gap;
        count++;
    }
    a[n]=key;
    return count;
}
int shellSort(int a[],int n)
{
    int cnt=0;
    for(int gap=n/2;gap>0;gap/=2)
        for(int i=gap;i<n;i++)
            cnt+=shell(a,i,gap);
    return cnt;
}

int insert(int a[],int n)
{
    int key=a[n];
    int count=0;
    while(n>=0&&a[n-1]>key)
    {
        a[n]=a[n-1];
        n--;
        count++;
    }
    a[n]=key;
    return count;
}
int insertSort(int a[],int n)
{
    int cnt=0;
    for(int i=1;i<n;i++)
        cnt+=insert(a,i);
    return cnt;
}
int main(){
    int arr_1[10]={7,8,1,5,6,2,3,4,9,0};
    int arr_2[10]={7,8,1,5,6,2,3,4,9,0};
    int n=10;
    int cnt_1=shellSort(arr_1,n);
    int cnt_2=insertSort(arr_2,n);
    for(int i=0;i<n;i++)
        printf("%d\t",arr_1[i]);
    printf("\n\n");
    printf("shellSort‘number=%d\n",cnt_1);
    printf("\n\n----------------------------\n\n");
    for(int i=0;i<n;i++)
        printf("%d\t",arr_2[i]);
    printf("\n\n");
    printf("insertSort‘number=%d\n",cnt_2);
}

可以看出：

仅仅是10个数的插入算法就差不多显示出了近一倍的差距

 接下来，我们写一个creat函数，创建一个更大的数组，看一下两种算法的差异

#define MAXSIZE 100void CreatArr(int a[],int n)
{
    srand((unsigned int)time(0));
    for(int i=0;i<n;i++)
    {
        int number=rand()%1000+1;
        a[i]=number;
        printf("%d\t",a[i]);
    }
}
int shell(int a[],int n,int gap)
{
    int count=0;
    int key=a[n];
    while(n>=gap&&a[n-gap]>key)
    {
        a[n]=a[n-gap];
        n-=gap;
        count++;
    }
    a[n]=key;
    return count;
}
int shellSort(int a[],int n)
{
    int cnt=0;
    for(int gap=n/2;gap>0;gap/=2)
        for(int i=gap;i<n;i++)
            cnt+=shell(a,i,gap);
    return cnt;
}

int insert(int a[],int n)
{
    int key=a[n];
    int count=0;
    while(n>=0&&a[n-1]>key)
    {
        a[n]=a[n-1];
        n--;
        count++;
    }
    a[n]=key;
    return count;
}
int insertSort(int a[],int n)
{
    int cnt=0;
    for(int i=1;i<n;i++)
        cnt+=insert(a,i);
    return cnt;
}
int main(){
    int arr_1[MAXSIZE];
    int arr_2[MAXSIZE];
    int n=MAXSIZE;
    CreatArr(arr_1,n);
    memcpy(arr_2,arr_1,sizeof(int)*n);
    
    int cnt_1=shellSort(arr_1,n);
    int cnt_2=insertSort(arr_2,n);
    for(int i=0;i<n;i++)
        printf("%d\t",arr_1[i]);
    printf("\n\n");
    printf("shellSort‘number=%d\n",cnt_1);
    printf("\n\n----------------------------\n\n");
    for(int i=0;i<n;i++)
        printf("%d\t",arr_2[i]);
    printf("\n\n");
    printf("insertSort‘number=%d\n",cnt_2);
}

这里可以看到，为保证arr_1,arr_2两者相同，我调用了memcpy()函数（注意一定要引入头文件string.h），下一期有时间将讲解这个函数

memcpy是个很有意思的函数，相较于strcpy来说功能更大，无论是char,short,int,float。。。数组都可以通过地址

复制来实现数据的相同。

 这里就看得出巨大的差异了吧