想比较下两种排序需要的操作次数，就用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--)
      if(n%i1==0)
       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=20;i1>=1;i1--)
     if(n%i1==0)
       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;
}

希尔排序的时间复杂度和增量gap的取法有很大的关系，而且希尔排序的时间复杂度到现在为止仍尚无定论。

不知要是有人把这个问题解决了，是不是有可能获图灵奖呢？呵呵！

其实我是想知道为什么A跟B需要的数据对换次数是完全一样的
完全！！！！！！！！