C語言課程設(shè)計報告排序比較

PAGEPAGE12信息與控制學(xué)院課程設(shè)計 題目排序算法的比較學(xué)生姓名 學(xué)號 學(xué)院 專業(yè) 指導(dǎo)教師 二Ｏ一四年12月26日一、實驗?zāi)康念}目與要求編寫排序算法至少5種對排序算法進(jìn)行比較，（包括時間和比較次數(shù)）輸出結(jié)果本程序涉及的知識點變量的定義、輸入和輸出函數(shù)、產(chǎn)生隨機(jī)數(shù)函數(shù)、if語句、goto語句、冒泡排序，直接插入排序，選擇排序，希爾排序等。二、功能設(shè)計冒泡排序：將相鄰的兩個數(shù)比較，將較小的數(shù)調(diào)到前頭；有n個數(shù)就要進(jìn)行n-1趟比較，第一次比較中要進(jìn)行n-1次兩兩比較，在第j趟比較中，要進(jìn)行n-j次兩兩比較。插入排序：在得到要排序的數(shù)組以后，講數(shù)組分為兩個部分，數(shù)組的第一個元素為一個部分，剩下的元素為一部分，然后從數(shù)組的第二個元素開始，和該元素以前的所有元素比較，如果之前的元素沒有比該元素大的，那么該元素的位置不變，如果有元素的值比該元素大，那么記錄相愛他所在的位置；例如I，該元素的位置為k，則將從i到k位置上的所有元素往后移動一位，然后將k位置上的值移動到i位置上。這樣就找到了K所在的位置。每一個元素都這樣進(jìn)行，最終就會得到排好順序的數(shù)組。選擇排序：首先以一個元素為基準(zhǔn)，從一個方向開始掃描，比如從左到右掃描，以A[0]為基準(zhǔn)，接下來從A[0]….A[9]中找出最小的元素，將其與A[0]交換。然后將其基準(zhǔn)位置右移一位，重復(fù)上面的動作，比如，以A[1]為基準(zhǔn)，找出A[1]~A[9]中最小的，將其與A[1]交換。一直進(jìn)行到將基準(zhǔn)位置移到數(shù)組最后一個元素時排序結(jié)束。 計時：使用start_t=clock();計下開始時間使用end_t=clock();記下結(jié)束時間針對不同的排序在不同的位置插入計時語句，完成計時功能三、功能實現(xiàn)3.1、隨機(jī)數(shù)函數(shù)1）函數(shù)原形：rand()2)功能：rand()函數(shù)通過編程生成小于30000的隨機(jī)數(shù)列3）模塊代碼： for(i=1;i<n+1;i++){b:L.elem[i].key=rand(); printf("%10d",L.elem[i].key);if(L.elem[i].key>30000)gotob;++L.length;}} 3.2、冒泡排序函數(shù)1）函數(shù)原形：qipao(SqList&L)2)功能：通過相鄰比較，移位達(dá)到從小到大的數(shù)據(jù)排列。3）相關(guān)變量：SqList&L:接收帶排序的數(shù)組。4）模塊代碼及其相關(guān)注釋：voidqipao(SqList&L)//冒泡{start_t=clock();inti=1,j,bj=0,yd=0;while(i<L.length){for(j=1;j<L.length;j++){bj++;if(L.elem[j].key>L.elem[j+1].key){L.elem[0].key=L.elem[j].key;L.elem[j].key=L.elem[j+1].key;L.elem[j+1].key=L.elem[0].key;yd+=3;}}i++;}四、C程序設(shè)計源碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#defineLIST_INIT_SIZE50000intbj1,yd1,n;clock_tstart_t,end_t;typedefstruct{intkey;}ElemType;typedefstruct{ElemType*elem;intlength;}SqList;voidaddlist(SqList&L){inti;a:printf("請輸入你要輸入的個數(shù):");scanf("%d",&n);if(n>50000){printf("超出范圍重新輸入!!!\n");gotoa;}L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(0);L.length=0;for(i=1;i<n+1;i++){b:L.elem[i].key=rand(); printf("%10d",L.elem[i].key);if(L.elem[i].key>30000)gotob;++L.length;}}voidSelectSort(SqList&L)//選擇{start_t=clock();inti,j,k,bj=0,yd=0;for(i=1;i<L.length;i++){k=i;for(j=i+1;j<L.length;j++){bj++;if(L.elem[j].key<L.elem[k].key)k=j;}if(i!=k){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;yd+=3;}}end_t=clock();printf("排序結(jié)果為：\n");for(i=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}printf("比較次數(shù)為%d移動次數(shù)為%d\n",bj,yd);printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidqipao(SqList&L)//冒泡{start_t=clock();inti=1,j,bj=0,yd=0;while(i<L.length){for(j=1;j<L.length;j++){bj++;if(L.elem[j].key>L.elem[j+1].key){L.elem[0].key=L.elem[j].key;L.elem[j].key=L.elem[j+1].key;L.elem[j+1].key=L.elem[0].key;yd+=3;}}i++;}end_t=clock();printf("排序結(jié)果為：\n");for(i=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}printf("比較次數(shù)為%d移動次數(shù)為%d\n",bj,yd);printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidInsertSort(SqList&L)//直接插入{start_t=clock();inti,j,yd=0,bj=0;for(i=2;i<=L.length;i++){if(L.elem[i].key<L.elem[i-1].key){L.elem[0].key=L.elem[i].key;yd++;j=i-1;bj++;while(L.elem[0].key<L.elem[j].key){L.elem[j+1].key=L.elem[j].key;j--;yd++;bj++;}L.elem[j+1].key=L.elem[0].key;yd++;}}end_t=clock();printf("排序結(jié)果為：\n");for(i=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}printf("比較次數(shù)為%d移動次數(shù)為%d\n",bj,yd);printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidxier(SqList&L)//希爾{start_t=clock();inti,d=L.length/2,j,w=0,k,yd=0,bj=0;while(w<d){w=1;for(i=w;i<L.length;i=i+d){k=i;for(j=i+d;j<L.length;j=j+d){if(L.elem[i].key>L.elem[j].key){k=j;bj++;}}if(i!=k){L.elem[0].key=L.elem[i].key;L.elem[i].key=L.elem[k].key;L.elem[k].key=L.elem[0].key;yd+=3;}w++;}d=d/2;w=1;}end_t=clock();printf("排序結(jié)果為：\n");for(i=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}printf("比較次數(shù)為%d移動次數(shù)為%d\n",bj,yd);printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidBeforeSort(){yd1=0,bj1=0;}voiddisplay(intm,intn){printf("比較次數(shù)為%d移動次數(shù)為%d\n",m,n);}intPartition(SqList&L,intlow,inthigh)//快速排序{intpivotkey;L.elem[0]=L.elem[low];yd1++;pivotkey=L.elem[low].key;while(low<high){yd1++;while(low<high&&L.elem[high].key>=pivotkey)--high;L.elem[low]=L.elem[high];bj1++;yd1++;while(low<high&&L.elem[low].key<=pivotkey)++low;L.elem[high]=L.elem[low];bj1++;yd1++;}L.elem[low]=L.elem[0];yd1++;returnlow;}voidQSort(SqList&L,intlow,inthigh){intpivotloc;if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList&L){start_t=clock();BeforeSort();QSort(L,1,L.length);printf("排序結(jié)果為：\n");for(inti=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}display(yd1,bj1);end_t=clock();printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidMerge(ElemTypeR[],ElemTypeR1[],intlow,intm,inthigh)//歸并{inti=low,j=m+1,k=low;while(i<=m&&j<=high){if(R[i].key<=R[j].key){bj1++;R1[k]=R[i];yd1++;i++;k++;}else{bj1++;R1[k]=R[j];yd1++;j++;k++;}}while(i<=m){R1[k]=R[i];yd1++;i++;k++;}while(j<=high){R1[k]=R[j];yd1++;j++;k++;}}voidMergePass(ElemTypeR[],ElemTypeR1[],intlength,intn){inti=0,j;while(i+2*length-1<n){Merge(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1<n-1)Merge(R,R1,i,i+length-1,n-1);elsefor(j=i;j<n;j++)R1[j]=R[j];}voidMSort(ElemTypeR[],ElemTypeR1[],intn){intlength=1;while(length<n){MergePass(R,R1,length,n);length=2*length;MergePass(R1,R,length,n);length=2*length;}}voidMergeSort(SqList&L){start_t=clock();BeforeSort();MSort(L.elem,L.elem,L.length);printf("排序結(jié)果為：\n");for(inti=1;i<=L.length;i++){printf("%5d",L.elem[i].key);}display(yd1,bj1);end_t=clock();printf("排序用時為%f\n",float(end_t-start_t)/CLK_TCK);}voidmain(){SqListL;addlist(L);printf("\n冒泡排序:\n");qipao(L);addlist(L);printf("\n直插排序:\n");InsertSort(L);addlist(L);printf("\n選擇排序:\n");SelectSo