插入排序存档!

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

#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;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航