#include <iostream>
#include <cmath>
using namespace std;
void InsertSort(int a[],int n)
{
int i,j,k;
for(i=1;i<n;++i)
{
k=a[i];
for(j=i-1;j>-1;--j)
{
if(k <a[j])
a[j+1]=a[j];
else
break;
}
a[j+1]=k;
}
}
void BInsertSort(int a[],int n)
{
int mid,i,j,k;
for(i=1;i<n;++i)
{
k=a[i];
int begin=0,end=i-1;
while(begin<=end)
{
mid=(begin+end)/2;
if(a[mid]>k) //保证在[0,i-1]内 end右边都是大于k的值（如果存在）
end=mid-1;
else
begin=mid+1;
}
for(j=i-1;j>end;--j)
{
a[j+1]=a[j];
}
a[end+1]=k;
}
}
//希尔算法尚无最好的增量序列，
//当增量序列为 dlta[k]= 2^(t-k+1)-1是时间复杂度为O(n^(3/2)) ，其中t为排序的趟数 1<=k<=t<=[log2(n+1)](地板）
//增量有各种取法，但需注意，应该使增量序列中的值没有除1之外的公因子，并且最后一个增量必须等于1(互质）；
//eg: 2^(t-k+1) --- 9 5 3 2 1
void ShellSort(int a[],int n)
{
int t=(int)(log10(n+1)/log10(2));
int k,i,j;
for(k=1;k<=t;++k)
{
int dk=(int)(pow(2,t-k+1)-1.0);
for(i=dk;i<n;++i)
{
int comp=a[i];
for(j=i-dk;j>-1;j-=dk)
{
if(a[j] > comp)
a[j+dk]=a[j];
else
break;
}
a[j+dk]=comp;
}
}
}
int main()
{
int num[100];
int n,i;
cin>>n;
for(i=0;i<n;++i)
{
cin>>num[i];
}
//InsertSort(num,n);
//BInsertSort(num,n);
ShellSort(num,n);
for(i=0;i<n;++i)
{
cout<<num[i]<<" ";
}
cout<<endl;
return 0;
} 
|
本类阅读TOP10