shell.c

算法函数库 算法函数库

#include "stdio.h"
long n;
long j;
long number[100000000];
long nm(long n,long m)
{
    long temp=n;
    long sum=1;
    while(m!=0)
    {
        if(m&1==1){sum=sum*temp;}
        temp=temp*temp;   
        m>>=1; 
    }
    return sum;
}
long mysearch(long left,long right)
{
     long  middle;
     long temp;
     long mynm;
     while(left<=right)
     {
         middle=(left+right)/2;
         temp=nm(2,middle);
         if(4*temp*temp-3*temp>n-1){right=middle-1;}
         else{left=middle+1;}
     }
     return right;
}
int main()
{
    long i,j,z;
    long temp,x,mynm;
    long unsort,sort;
    printf("n=");scanf("%ld",&n);
    for(i=0;i<n;i++){scanf("%ld",&number[i]);}
    i=mysearch(0,n);mynm=nm(0,n);
    x=4*mynm*mynm-3*mynm+1;   
    while(x>=1)
    {
        sort=0;unsort=x;
        for(;unsort<n;unsort+=x,sort+=x)
        {
            for(j=sort;j>0;j-=x)
            {
                if(number[unsort]>number[j]){break;}
            }
            temp=number[unsort];
            for(z=unsort;z>j;z+=x){number[z]=number[z-x];}
            number[j]=temp;
        }
        mynm>>=1;
        x=4*mynm*mynm-3*mynm+1;
        for(z=0;z<n;z++){printf("%ld ",number[z]);if(z%10==0&&z!=0){printf("\n");}}
        system("pause");
    }
    for(i=0;i<n;i++){printf("%ld ",number[i]);if(i%10==0&&i!=0){printf("\n");}}
    system("pause");
    return 0;
}