标签：height def 程序 shel 数据 maxsize 意思 算法 ++
在程序中出加入计数器来计算两者在执行过程中需要的插入次数
通过比较时间复杂度来比较效率
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)
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)
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)
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)
printf("%d\t",arr_2[i]);
printf("\n\n");
printf("insertSort‘number=%d\n",cnt_2);
}
可以看出：
仅仅是10个数的插入算法就差不多显示出了近一倍的差距
接下来，我们写一个creat函数，创建一个更大的数组，看一下两种算法的差异
#define MAXSIZE 100
void CreatArr(int a[],int n)
{
srand((unsigned int)time(0));
for(int i=0;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)
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)
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)
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)
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。。。数组都可以通过地址
复制来实现数据的相同。
这里就看得出巨大的差异了吧
C语言 通过输出排序次数来比较希尔排序和插入排序的优劣
标签：height def 程序 shel 数据 maxsize 意思 算法 ++
原文地址：https://www.cnblogs.com/oldfish123/p/13138506.html