比較插入排序與合并排序的運(yùn)行時間

HUST華中科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析實(shí)驗(yàn)一·實(shí)驗(yàn)報告姓名：XXXX學(xué)號：XXXX班級：XXXXXXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXX實(shí)驗(yàn)一比較插入排序與合并排序的運(yùn)行時間一、實(shí)驗(yàn)描述隨機(jī)生成n個數(shù)，分別用插入排序算法與合并排序算法進(jìn)行排序，測試m次，計算兩種算法的平均運(yùn)行時間，并進(jìn)行比較。二、實(shí)驗(yàn)設(shè)計算法一：插入排序1.從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描3.如果該元素（已排序）大于新元素，將該元素移到下一位置4.重復(fù)步驟3，直到找到已排序的元素小于或等于新元素的位置5.將新元素插入到下一位置中6.重復(fù)步驟2算法二：合并排序合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應(yīng)用。合并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。合并排序也叫歸并排序。XXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXX1.定義clock_t變量start和finish，用于記錄函數(shù)執(zhí)行前后的時間。2.定義函數(shù)：執(zhí)行時間即為：插入排序：在輸入規(guī)模較大時，算法耗時相對較長；適用于對少量元素進(jìn)行排序。合并排序：相比插入算法其耗時隨著規(guī)模的增加增長的慢了許多，其優(yōu)勢要在數(shù)據(jù)規(guī)模較大時才能體現(xiàn)。XXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXX代碼：#include<stdio.h>#include<stdlib.h>#include<time.h>#include<malloc.h>voidInsert_Sort(inta[],intn){inti,j,k;for(j=1;j<n;j++){k=a[j];i=j-1;while(k<a[i]&&i>0){a[i+1]=a[i];i--;}a[i+1]=k;}}//合并排序算法中的實(shí)現(xiàn)合并的子程序voidMerge(inta[],constintp,constintq,constintr){intL_Length,R_Length;int*L,*R,i,j,k;L_Length=q-p+1;R_Length=r-q;XXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXXL=(int*)malloc(L_Length*sizeof(int));R=(int*)malloc(R_Length*sizeof(int));if(L==0||R==0){printf("內(nèi)存分配失?。。?！");return;}for(i=0;i<L_Length;i++){L[i]=a[p+i];}for(j=0;j<R_Length;j++){R[j]=a[q+j+1];}i=0;j=0;for(k=p;k<=r;k++){if((i<L_Length)&&(j<R_Length)&&(L[i]<=R[j])||(j==R_Length)){a[k]=L[i];i++;}else{a[k]=R[j];j++;}}XXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXXfree(R);free(L);}//合并排序算法-主程序//n*lg(n),系數(shù)較小voidMerge_Sort(inta[],constintp,constintr){intq;if(p<r){q=(p+r)/2;Merge_Sort(a,p,q);Merge_Sort(a,q+1,r);Merge(a,p,q,r);}}voidmain(){doublecost11,cost1=0,cost21,cost2=0;clock_tstart,finish;intn,m,i;int*string1,*string2;printf("輸入:要排序的數(shù)字個數(shù),測試次數(shù)\n");scanf("%d,%d",&n,&m);for(i=1;i<=m;i++){srand((unsigned)time(NULL));string1=(int*)malloc(n*sizeof(int));string2=(int*)malloc(n*sizeof(int));for(i=0;i<n;i++)XXXXXXXXXX數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告·實(shí)驗(yàn)一XXXXXXXXXXXX{string1[i]=rand()%100+1;string2[i]=string1[i];}start=clock();Insert_Sort(string1,n);finish=clock();cost11=(double)(finish-start)/CLOCKS_PER_SEC;cost1=cost1+cost11;start=clock();Merge_Sort(string2,0,n-1);finish=clock();cost21=(double)(finish-start)/CLOCKS_PER_SEC;cost2=cost2+cost21;free(string1);