各种内部排序性能比较数据结构课程设计.doc

数据结构课程设计报告 课程设计题目：各种内部排序性能比较 学生姓名： 专 业： 班 级： 学 号： 指导教师： 年 月 日目录试验分析需求分析说明3总体设计3详细设计 4试验内容4代码6程序测试22总结241、 需求分析说明：排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：选择法、冒泡法、直接插入法、快速法、两路合并法）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。2、 总体设计： 本程序主要包括六个功能： 1、选择法排序 2、冒泡法排序 3、直接插入法排序 4、快速法排序 5、二分法排序 6、希尔排序 7、堆排序 8、统计各种排序的时间复杂度 因此在类Sort定义中主要包括这七个函数。以及需要用到的变量。 主函数中包括产生待排序序列、提示用户选择排序方法或比较各种排序的时间复杂度。并使用while循环使用户可以连续选择想要程序做的操作，直到选择退出程序为止。选择法排序select 冒泡法排序bubble Main（）插入法排序straight Qsort（）快速法排序quick Merge（）二分法排序 binary 希尔排序 Shell 堆排序 Heap SUB_MENUE(): 输出各菜单产生随机数序列提示用户选择菜单 若选择1，则重新输入数据进行排序，并再次选择排序方法。若选择2，则调用BIS_INT（）函数进行二分法排序，并输出各趟排序结果若选择3，则调用STINSORT（）函数进行直接排序，并输出各趟排序结果若选择4，则调用SHELL（）函数进行希尔排序，并输出各趟排序结果若选择5，则调用QUICK（）函数进行快速法排序，并输出各趟排序结果若选择6，则调用SELECT（）函数进行选择排序，并输出各趟排序结果若选择7，则调用BUBBLE（）函数进行冒泡法排序，并输出各趟排序结果 若选择8，则调用HEAPSORT（）函数进行堆排序，并输出各趟排序结果若选择9，则调用系统函数exit（）退出循环，退出程序。3、 详细设计：一、函数 void SELECT () 用选择法对序列排序并输出各趟排序结果； void BUBBLE ()用冒泡法对序列排序并输出各趟排序结果； void STINSORT ()用直接插入法对序列排序并输出各趟排序结果；void QUICK ()用快速法对序列排序并输出各趟排序结果；void HEAPSORT()用堆排序对序列排序并输出各趟排序结果；void SHELL()用希尔法对序列排序并输出各趟排序结果；void BIS_INT()用折半法对序列排序并输出各趟排序结果。 定义变量int Compar，intExch用于记录排序的元素比较、移动次数；选择排序： 将初始序列（A0An-1）作为待排序序列，第一趟在待排序序列中找出最小值元素，与该序列中第一个元素交换，下一趟排序在序列（A1An-1）中进行，依次循环，完成排序。该算法执行时间与元素的初始排列无关。不论初始序列如何，该算法都必须执行n-1趟，每趟执行n-i-1次元素之间的比较。总的比较次数为n(n-1)/2；因此，此种排序的最好、最坏和平均情况的时间复杂度都为O（n2）；需要移动元素次数为3（n-1）；该排序算法经过一趟排序后，就能确定一个元素的最终位置，是不稳定的排序方法。冒泡法排序：此种排序是通过交换两个元素实现的。第一趟在序列（A0An-1）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束后，最大元素被置于最后（即沉底），下一趟排序只需在序列（A0An-2）中进行；如果在某一趟排序中没有交换元素，说明子序列已经有序，无需再往下进行。具体代码中通过定义变量last来确定排序的趟数。一进入while循环，last的值就被置为0，并且只有在for循环中有元素的交换时才被修改为新值，如果某趟排序没有交换元素，则last保持为0，再由i=last决定循环结束，排序完成。因此，冒泡排序最多执行n-1趟，第i趟比较n-1次，总共移动元素次数3n(n-1)/2，由此可看出，冒泡排序比较偏爱基本有序的序列。直接插入法排序：将序列中第一个元素作为一个有序序列，将剩下的n-1个元素插入该有序序列中，插入后保持该序列有序。在将一个元素插入到有序表中时，首先将其存入临时变量temp中，然后从后往前查找插入位置，当temp小于表中元素时，就将该元素后移，继续比较移动，直到temp大于等于表中元素或者到了有序表中第一个元素时结束，这时就可将temp存入刚后移的元素的位置了。次种排序法必须执行n-1趟，最好情况下，每趟排序只比较一次，移动两次。最坏情况下，最多比较i次，移动i+2次。快速排序：此排序算法是一个递归算法。定义函数Qsort(),实现具体排序过程。每趟排序的结果是将当前序列分割为两个子序列：左边的元素全部小于分割元素，右边的子序列全部大于分割元素。再对两个子序列进行快速排序，依次循环，直到子序列为空或只有一个元素时结束。定义变量left和right分别指向原始序列的第一个和最后一个元素，i和j为游动指针，初始化i=left；j=right+1;设待排序序列的第一个元素为分割元素。i从左向右扫描，找到第一个大于或等于分割元素的元素时结束，j从右往左扫描，找到第一个小于或等于分割元素的元素时结束，若i=j时结束。再交换Aleft和Aj，完成一趟排序。再调用本函数对低端序列和高端序列快速排序。在函数quicksort()中，定义变量int h来保存原始序列的元素个数，以便后面输出每趟排序结果时使用。再调用函数Qsort（）。二分法排序：根据插入排序的基本思想，在找第i个记录的插入位置时，前i-1个记录已排序，将第i个记录的排序码keyi和已排序的前i-1个的中间位置记录的排序码进行比较,如果keyi小于中间位置记录排序码,则可以在前半部继续使用二分法查找,否则在后半部继续使用二分法查找,直到查找范围为空,即可确定keyi的插入位置。堆排序：堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（1）用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆,此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意： 只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止4、 代码：#include #include #include #include #include #include #define MAXSIZE 100typedef int RedType;typedef struct SqList RedType INTMAXSIZE+1; int length; SqList; SqList L;void TIME() /获得系统时间 static char *week7=日,一,二,三,四,五,六; time_t t; struct tm *tp; t=time(NULL); tp=localtime(&t); printf(t n); printf(tt 现在是:%d年%d月%d日,tp-tm_year+1900,tp-tm_mon+1,tp-tm_mday); printf( %d:%d:%d ,tp-tm_hour,tp-tm_min,tp-tm_sec,tp-tm_wday); printf(星期%sn,weektp-tm_wday);void PRINT(SqList *L) /打印排序结果 int i; printf(tt); for(i=1;ilength;i+) printf(%d ,L-INTi); printf(n);void STINSORT(SqList *L) /直接插入排序 int i,j; for(i=2;ilength;i+) L-INT0=L-INTi; j=i-1; while(L-INTjL-INT0) L-INTj+1=L-INTj; j-; L-INTj+1=L-INT0; /*/void BIS_INT(SqList *L) /折半插入排序 int i,j,low,high,mid; int intCompar = 0; /intCompar 比较次数 int intExch = 0; /intExch 交换次数 for(i=2;ilength;+i) if(L-INTiINTi-1)/开始比较(前一项大于后一项时) L-INT0 = L-INTi;/交换+1intExch+;high=i-1; low=1;while(lowINT0INTmid)/比较+1 high=mid-1; else low=mid+1; intExch+; for(j=i-1;j=high+1;-j) L-INTj+1=L-INTj; /交换+1 intExch+; L-INThigh+1=L-INT0; /交换+1 intExch+; intCompar+;printf(本次排序中一共比较了%d次，交换了%d次,intCompar,intExch);void SHELL(SqList *L) /希尔排序 int i,j,d; d=L-length/2; while(d=1) for(i=d+1;ilength;i+) L-INT0=L-INTi; j=i-d; while(L-INTjL-INT0&j0) L-INTj+d=L-INTj; j=j-d; L-INTj+d=L-INT0; d=d/2; void QUICK(SqList *L,int low,int high) /快速排序 int i,j,temp; i=low; j=high; temp=L-INTlow; while(ij) while(ij&tempINTj) j-; if(iINTi=L-INTj; i+; while(iINTi=temp) i+; if(iINTj=L-INTi; j-; L-INTi=temp; if(lowi) QUICK(L,low,i-1); if(ihigh) QUICK(L,j+1,high); void SELECT(SqList *L) /选择排序 int i,j,small; for(i=1;ilength-1;i+) small=i; for(j=i+1;jlength;j+) if(L-INTjINTsmall) small=j; if(small!=i) L-INT0=L-INTi; L-INTi=L-INTsmall; L-INTsmall=L-INT0; void BUBBLE(SqList *L) /冒泡优化排序 int i,j,flag=1; for(i=0;ilength-1&flag=1;i+) flag=0; for(j=0;jlength-i;j+) if(L-INTjL-INTj+1) flag=1; L-INT0=L-INTj; L-INTj=L-INTj+1; L-INTj+1=L-INT0; void BUILDHEAP(SqList *L,int k,int m) /建立堆 int i,x; x=L-INTk; for(i=2*k;i=m;i=i*2) if(iINTiINTi+1) i+; if(xL-INTi) break; L-INTk=L-INTi; k=i; L-INTk=x; void HEAPSORT(SqList *L) /堆排序 int i,n,temp; n=L-length; for(i=n/2;i0;i-) BUILDHEAP(L,i,n); for(i=n;i1;i-) temp=L-INT1; L-INT1=L-INTi; L-INTi=temp; BUILDHEAP(L,1,i-1); void RAND(SqList *L) /随机生成数字 int i; srand(unsigned)time(NULL); L-length=(rand()%(14)+2; for(i=0;ilength;i+) L-INTi=(rand()%(100)+1; void DisPlay(SqList *L) /数组回显 int i; for(i=1;ilength;i+) printf(%d ,L-INTi); printf(n);void INIT(SqList *L) /初始化排序的数据 int i; char c;loop:; TIME(); printf(t n); printf(nttt请输入待排序数据的数量【=2】: ); while (scanf(%d, &L-length)!=1) /检测是否为正确输入数 while (c=getchar()!=n); printf(ntt【】Error:错误的输入,请按任意键重新输入ntttt); getch(); system(cls); goto loop; if(L-lengthlengthMAXSIZE) printf(ntttt 【】Error:ntt待排序数据数目小于2或超出最大输入量,请按任意键重新输入ntttt); getch(); system(cls); goto loop; printf(n); for(i=1;ilength;i+) printf(ttt 请输入第%d个数据: ,i);lable:; while (scanf(%d,&L-INTi)!=1) while (c=getchar()!=n); printf(n【】Error:数据输入出错,请重新输入); goto lable; printf(nnnnttt数据初始化成功,按任意键继续n); getch(); system(cls);void PRIN() /格式化输出 int i; printf(tt); for(i=0;iL.length;i+) printf(); printf(n);int MENUE() int input_data; char c; TIME();printf(t n); printf(t 各种排序的基本操作实现 n); printf(t n); printf(t 1、手动(Hand)输入数据 n); printf(t n);printf(t 2、随机(Rand)生成数据 n); printf(t n); printf(t 3、退 出 . n); printf(t n); printf(t 请正确选择:); while(scanf(%d, &input_data)!=1) while (c=getchar()!=n); return input_data; fflush(stdin); return input_data;void SUB_MENUE() char c; for(;) TIME(); printf(t n); printf(t 各种排序的基本操作实现 n); printf(t n); printf(t 1、重新(Again)输入数据 n); printf(t 2、折半(Binary)排序 n); printf(t 3、直接(Straight)排序 n);printf(t 4、希尔(Shell)排序 n);printf(t 5、快速(Quick)排序 n);printf(t 6、选择(Select)排序 n);printf(t 7、冒泡(Bubble)排序 n);printf(t 8、堆 (Heap)排序 n);printf(t 9、随机(Rand)生成 n); printf(t Q、退 出 . n); printf(t n); printf(t 【共%d个数据】如下:n,L.length); PRIN(); PRINT(&L); PRIN(); printf(t 请选择:); scanf(%s,&c); switch(c) case 1: system(cls); INIT(&L); system(cls); break; case 2: BIS_INT(&L); printf(nttt 排序成功!nttt ); DisPlay(&L); system(pause); system(cls); break; case 3: STINSORT(&L); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 4: SHELL(&L); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 5: QUICK(&L,1,L.length); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 6: SELECT(&L); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 7: BUBBLE(&L); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 8: HEAPSORT(&L); printf(nttt 排序成功!nttt ); system(pause); system(cls); break; case 9: RAND(&L); printf(nttt 随机生成成功!nttt ); system(pause); system(cls); break; case q: case Q: system(cls); printf(nnnnttt 谢 谢 使 用 , 再 见!n); printf(nttt 任 意 键 退 出!nttt); getch(); exit(0); default : printf(ntttt 【】Error:nttt 输入有误,请重新选择!n); getch(); system(cls); break; break; void main(void) int input_data; do input_data=MENUE(); switch(input_data) case 1: system(cls); INIT(&L); SUB_MENUE(); break; case 2: system(cls); RAND(&L); SUB_MENUE(); break; case 3: system(cls); printf(nnnnttt 谢 谢 使 用 , 再 见!n); printf(nttt 任 意 键 退 出!nttt); getch(); exit(0); break; default: printf(ntttt 【】Error:nttt 输入有误,请重新选择!n); getch(); system(cls); break; while(input_data!=3); 5、 程序测试：1、程序测试： 因为排序算法性能的比较不仅是根据各种排序的算法设计决定的，还与待排序序列的元素个数和原始序列是否有序有关。而此程序所产生的序列是完全随机的，为了公平的比较，得到较合理的数据，需多运行几次，得到多组数据，并测试。现就选择其中较有代表性的两组数据进行分析：运行程序，所得界面如下：排序结果：2、 分析测试结果：由运行结果可知，对于选择法排序，无论原始序列如何，它需要比较的次数总是n(n-1)/2次，移动元素次数总是3（n-1）次；而冒泡排序则不同，此种排序比较偏爱基本有序的序列；直接插入法和选择法一样必须进行n-