直接插入排序基本算法.doc

:..直接插入排序基本算法#include<>#include<>#include<>constintn=100000。typedefstruct{ intkey。}RedType。typedefstruct{RedType*r。//r[n+1]。intlength。}SqList。intrandom(>。voidInsertSort(SqList&L>。voidmain(>{ SqListL。 =newRedType[n+1]。 =n。 for(inti=1。i<=n。i++> [i].key=random(>。 longt1,t2。 t1=clock(>。 InsertSort(L>。 t2=clock(>。 cout<<"时间:"<<float(t2-t1>/CLK_TCK<<endl。}intrandom(>{intA=48271。 intM=2147483646。 intQ=M/A。 intR=M%A。 staticintx=1。 intx1。 x1=A*(x%Q>-R*(x/Q>。 if(x1>=0>x=x1。 else x=x1+M。 returnx。}voidInsertSort(SqList&L>//直接插入排序__基本算法:{//对顺序表L作直接插入排序。 for(inti=2。i<=。++i> if(([i].key<[i-1].key> {//"<",[i]插入有序子表 [0]=[i]。//复制为哨兵 [i]=[i-1]。 for(intj=i-2。([0].key<[j].key>。--j> [j+1]=[j]。//记录后移 [j+1]=[0]。//插入到正确位置b5E2RGbCAP }}//InsertSort*/改进1#include<>#include<>#include<>constintn=100000。typedefstruct{ intkey。}RedType。typedefstruct{RedType*r。//r[n+1]。intlength。}SqList。intrandom(>。voidInsertSort(SqList&L>。voidmain(>{ SqListL。 =newRedType[n+1]。 =n。 for(inti=1。i<=n。i++> [i].key=random(>。 longt1,t2。 t1=clock(>。 InsertSort(L>。 t2=clock(>。 cout<<"时间:"<<float(t2-t1>/CLK_TCK<<endl。 }intrandom(>{intA=48271。 intM=2147483646。 intQ=M/A。 intR=M%A。 staticintx=1。 intx1。 x1=A*(x%Q>-R*(x/Q>。 if(x1>=0>x=x1。 else x=x1+M。 returnx。}voidInsertSor