算法实验报告二

算法设计与分析实验学院：信息工程专业：计算机科学与技术算法实验报告二排序问题求解一、实验目的：1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现；3）熟练掌握快速排序算法的实现；4)理解常见的算法经验分析方法；二、实验要求：生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。实现直接插入排序算法.实现快速排序算法.三、实验主要步骤：#include<stdlib.h>#include<stdio.h>#include<time.h>#include<math.h>#defineRAND_MAX10000#defineMax1000intI_Change_count=0;//插入排序比较计数器intI_Move_count=0; //插入排序移动计数器intS_Change_count=0;//选择排序比较计数器intS_Move_count=0;//选择排序移动计数器intQ_Change_count=0;//快速排序比较计数器intQ_Move_count=0;//快速排序移动计数器voidmain(){ longnum; longArray[Max],Brray[Max],Crray[Max];//分别用来保存随机数作为两个排序的对象 intA_Length; intLow=0; intHigh; time_tt; voidInsertSort(longArray[],intA_Length); //voidSelectSort(longBrray[],intA_Length); voidQuickSort(longCrray[],intLow,intHigh); srand((unsigned)time(&t));/*用时间初始化随机函数*/ intT,i; printf("输入你想要比较的数的个数，本算法是按照2的次方来计算的:"); scanf("%d",&T); A_Length=(int)pow(2.,T); if(A_Length>1000) { exit(0);//如果比较次数大于100000，退出程序 } High=A_Length-1; printf("比较的个数为：%d\n",A_Length); printf("=======================原序列=========================\n"); for(i=0;i<A_Length;i++) { Array[i]=rand()%1000000;//产生1000000内的第一个随机数 Brray[i]=Array[i]; Crray[i]=Array[i]; printf("%ld\t",Array[i]); } printf("\n\n"); printf("=======================插入排序后的序列=========================\n"); InsertSort(Array,A_Length); for(i=0;i<A_Length;i++) { printf("%ld\t",Array[i]); } printf("\n=======================插入排序的时间复杂度========================="); printf("\n插入排序：比较次数=%d,移动次数=%d,时间复杂度=%d\n\n",I_Change_count,I_Move_count,I_Change_count+I_Move_count); /*printf("=======================选择排序后的序列=========================\n"); SelectSort(Brray,A_Length); for(inti=0;i<A_Length;i++) { printf("%ld\t",Brray[i]); } printf("\n=======================选择排序的时间复杂度========================="); printf("\n选择排序：比较次数=%d,移动次数=%d,时间复杂度=%d\n\n",S_Change_count,S_Move_count,S_Change_count+S_Move_count);*/ printf("=======================快速排序后的序列=========================\n"); QuickSort(Crray,Low,High); for(i=0;i<A_Length;i++) { printf("%ld\t",Crray[i]); } printf("\n=======================快速排序的时间复杂度========================="); printf("\n插入排序：比较次数=%d,移动次数=%d,时间复杂度=%d\n",Q_Change_count,Q_Move_count,Q_Change_count+Q_Move_count);}voidInsertSort(longArray[],intA_Length){ inti,j; longsignal;for(i=1;i<A_Length;i++)//依次插入Array[1]，…，Array[n-1]if(Array[i]<Array[i-1]||(I_Change_count++&&0))//比较失败时，比较计数器自加 { I_Change_count++;//比较成功时因为“||”后面的不执行所以比较计数器得自加signal=Array[i]; j=i-1;//signal是哨兵，且是Array[i]的副本do{//从右向左在有序区Array[1．．i-1]中查找Array[i]的插入位置I_Change_count++;//比较成功时直接执行所以比较计数器放在此处 Array[j+1]=Array[j];//将关键字大于Array[i]的记录后移I_Move_count++; j--;}while(signal<Array[j]);//当signal≥Array[j]时终止 I_Change_count++;//比较失败时，循环跳出比较计数器自加一次Array[j+1]=signal;//Array[i]插入到正确的位置上}//endif}voidSelectSort(longBrray[],intA_Length){ inti,j,k; longsignal; for(i=0;i<A_Length;i++) { k=i; for(j=i+1;j<A_Length;j++) { S_Change_count++;//因为不管比较成不成功都要比较A_Length-j次 //所以将比较计数器放在比较前 if(Brray[j]<Brray[k]) k=j; } if(k!=i) { signal=Brray[i]; Brray[i]=Brray[k]; Brray[k]=signal; S_Move_count++;//每次交换当做移动一次，因为其他赋值都是为了完成算法而写的 //我们认为两者的交换只要一次就实现 } }}voidQuickSort(longCrray[],intLow,intHigh){ intC_Low=Low,C_High=High; longsignal=Crray[Low]; if(Low>=High)return; while(C_Low!=C_High) { while(C_Low<C_High&&Crray[C_High]>=signal) C_High--; Crray[C_Low]=Crray[C_High]; while(C_Low<C_High&&Crray[C_Low]<=signal) C_Low++; Crray[C_High]=Crray[C_Low]; Q_Change_count++; } Crray[C_Low]=signal; Q_Move_count++; QuickSort(Crray,Low,C_Low-1); QuickSort(Crra