数据结构课程设计--多种排序

#includestdio.h#includestdlib.h//°üº¬srand()ºÍrand()#includetime.h//°üº¬time()#defineMIN0//×îСֵ#defineMAX100000//×î´óÖµ#defineMAXSIZE20#defineERROR0#defineTRUE1#defineLT(a,b)((a)(b))typedefintLElemtype;typedeflongintKeyType;typedefstruct{KeyTypekey;LElemtype*data;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;intInitList_Sq(SqList&L){L.r[0].data=(int*)malloc(MAXSIZE*sizeof(int));if(!L.r[0].data)exit(ERROR);L.length=0;returnTRUE;}voidprint(SqListL){printf(ÅÅÐòºóµÄ¼Ç¼Ϊ:\n);for(inti=1;i=L.length;i++){if(i%6==0)printf(\n);printf(%12d,L.r[i].key);}printf(\n);}//²åÈëÅÅÐòvoidInsertSort(SqListL){for(inti=2;i=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(intj=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}print(L);}//Ï£¶ûÅÅÐòvoidShellInsert(SqList&L,intdk){for(inti=dk+1;i=L.length;++i)if(LT(L.r[i].key,L.r[i-dk].key)){L.r[0]=L.r[i];for(intj=i-dk;j0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];L.r[j+dk]=L.r[0];}printf(asdfgh\n);}voidShellSort(SqListL){inti,j=0;intleng=1;intdlta[MAXSIZE],a[MAXSIZE];for(i=MAXSIZE/2;i==1;i=i/2,j++){printf(%d,i);printf(%d,leng);a[j]=i;printf(%d,a[j]);leng++;}for(i=0;i=leng;i++){dlta[i]=a[leng-i+1];}for(intk=0;kleng+1;++k)ShellInsert(L,dlta[k]);print(L);}/*voidShellSort(SqListL,intn){//Ï£¶ûÅÅÐò·¨inti,j,temp,gap;//gap×÷Ϊ¼ä¸ôÔöÁ¿gap=n/2;//ÔöÁ¿³õʼ»¯while(gap0){for(i=gap;in;i++){//¶ÔËùÓмä¸ôgapλÖõÄËùÓÐÔªËØ×é²ÉÓÃÖ±½Ó²åÈëÅÅÐò¡£temp=L.r[i].key;//temp×÷ΪÁÙʱ±äÁ¿£¬ÔÝʱ´æ·Åa[i]µÄÖµ£¬a[i]λÖÃΪ´ý²åÈë¿Õλj=i-gap;while(j=0&&tempL.r[j].key){//¶Ô¼ä¸ôgapλÖõÄÔªËØ×é½øÐÐÅÅÐòL.r[j+gap].key=L.r[j].key;j=j-gap;}L.r[j+gap].key=temp;j=j-gap;}gap=gap/2;//ÔöÁ¿¼ä¸ô¼õÉÙ}print(L);}*///ÆðÅÝÅÅÐò//¿ìËÙÅÅÐò/*intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];pivotkey=L.r[low].key;while(lowhigh){while(lowhigh&&L.r[high].key=pivotkey)--high;L.r[low]=L.r[high];while(lowhigh&&L.r[low].key=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow;}//¼òµ¥ÅÅÐòvoidSelectSort(SqList&L){for(i=1;iL.length;++i){j=SelectMinKey(L,i);if(i!j)L.r[i]½»»»L.r[j];}}//¶ÑÅÅÐòtypedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j=m;j*=2){if(jm&<(H.r[j].key,H.r[j+1].key))++j;if(!LT(rc.key,H.r[j].key))break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}voidHeapSort(HeapType&H){for(i=Hlength/2;i0;--i)HeapAdjust(H,i,H.length);for(i=H.length;i1;--i){H.r[1]½»»»H.r[i];HeapAdjust(H,1,i-1);}}*/voidproduce(SqList&L){srand((unsigned)time(NULL));printf(²úÉúµÄ¼Ç¼Ϊ:\n);for(inti=1;i=MAXSIZE;i++,L.length++){L.r[i].key=rand()%(MAX-MIN)+MIN;if(i%6==0)printf(\n);printf(%12d,L.r[i].key);}printf(\n);}voidmain(){intmethod,n;SqListL;InitList_Sq(L);produce(L);while(1){printf(ÇëÑ¡ÔñÄãÏëÒª½øÐеIJÙ×÷:\n1.²åÈëÅÅÐò2.Ï£¶ûÅÅÐò3.ÆðÅÝÅÅÐò\n4.¿ìËÙÅÅÐò5.Ñ¡ÔñÅÅÐò6.¶ÑÅÅÐò\n7.½áÊø³ÌÐò\n);scanf(%d,&method);switch(method){case1:InsertSort(L);break;case2:ShellSort(L);break;case3:produce(L);break;case4:produce(L);break;case5:produce(L);break;case6:produce(L);break;case7:printf(ллʹÓñ¾³ÌÐò,ÔÙ¼û!\n);gotothere;default:printf(ûÓдËÏî²Ù×÷\n);}}there:;}/*printf(¿ªÊ¼²úÉúËæ»úÊý?\n1.ÊÇ2.·ñ\n);scanf(%d,&ans);if(ans==2)printf(ллʹÓñ¾³ÌÐò,ÔÙ¼û!\n);*/