[菜鸟疑问]希尔排序与直接插入排序的比较
想比较下两种排序需要的操作次数,就用C写了下,其中希尔排序具体操作我搞得太清楚,就分别按理解的两种方法各写了一个函数,代码如下。比较之后发现个很有趣的现象:A跟B的操作次数是完全一样的!!!!然后C的大概会是AB的三分之二的样子。
想不通为什么A和B会完全一样啊!!!明明就是不一样的算法啊……还请高手指点下
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int A(int b[],int n)
{
int i,j,k,m=0,a[n];
for(i=0;i<n;i++)
a[i]=b[i];
for(i=1;i<n;i++)
{
for(j=i;j>0;j--)
if(a[j]<a[j-1]) {k=a[j];a[j]=a[j-1];a[j-1]=k; m++;}
else break;
}
/* for(i=0;i<n;i++)
printf("%6d",a[i]);
printf("\n"); */
return m;
}
int B(int b[],int n)
{
int i,j,k,m=0,a[n],i1,j1;
for(i=0;i<n;i++)
a[i]=b[i];
for(i1=20;i1>=1;i1--)
for(j1=0;j1<i1;j1++)
for(i=1+j1*n/i1;i<n/i1+j1*n/i1;i++)
{
for(j=i+1;j>0;j--)
if(a[j]<a[j-1]) {k=a[j];a[j]=a[j-1];a[j-1]=k; m++;}
else break;
}
for(i=0;i<n;i++)
// printf("%6d",a[i]);
// printf("\n");
return m;
}
int C(int b[],int n)
{
int i,j,k,m=0,a[n],i1,j1;
for(i=0;i<n;i++)
a[i]=b[i];
for(i1=500;i1>=1;i1--)
for(j1=0;j1<i1;j1++)
for(i=1;i<n/i1;i++)
{
for(j=i*i1-1;j>i1-2;j-=i1)
if(a[j]<a[j-i1]) {k=a[j];a[j]=a[j-i1];a[j-i1]=k; m++;}
else break;
}
// for(i=0;i<n;i++)
// printf("%6d",a[i]);
// printf("\n");
return m;
}
int main(int argc, char *argv[])
{
int a[500],i,j;
srand(time(NULL));
for(i=0;i<500;i++)
a[i]=rand();
printf("compare in A mode is:%d\n",A(a,500));
printf("compare in B mode is:%d\n",B(a,500));
printf("compare in C mode is:%d\n",C(a,500));
/* for(i=0;i<500;i++)
printf("%6d",a[i]);
*/
system("PAUSE");
return 0;
}