存储管理、查找和排序 实验6

存储管理、查找和排序班级：软件102姓名：学号：完成日期：2011.12.16题目：内部排序算法比较问题描述：通过随机数据比较各算法的关键字比较次数与移动次数基本要求：至少比较快速排序与堆排序。对结果进行简单分析一、需求分析功能：对给定的数进行排序，并统计关键字的比较次数和移动次数输入：要进行统计数的个数和这些数输出：关键字的比较次数和移动次数和排序后的序列测试数据：测试数据1：72419426预期输出结果1：12244679快速排序移动次数：24判断次数：20直接插入排序移动次数：25判断次数：13堆排序移动次数：54判断次数：25测试数据2：12345预期输出结果：12345快速排序移动次数：28判断次数：14直接插入排序移动次数：0判断次数：0堆排序移动次数：28判断次数：10二、概要设计由题目知，我们创建一个结构体存储数据的长度和数据，并且需要写出快速排序、堆排序和直接插入排序的代码。模块：1．结构体2．快速排序算法3．直接插入排序算法4．堆排序算法三、详细设计1.结构体：typedefstruct{intlength;intnum[101];}NUM;2．快速排序voidquick_sort(NUM&a,intl,inth,int&move_count,int&judge_count){intlow=l;inthigh=h;intm;if(lowhigh){m=one_quick_sort(a,low,high,move_count,judge_count);quick_sort(a,1,m-1,move_count,judge_count);quick_sort(a,m+1,high,move_count,judge_count);}}3．堆排序voidheap_sort(NUM&a,int&move_count,int&judge_count){for(inti=a.length/2;i0;--i){非0开始Lowhigh调用一次快速排序函数调用轴以下对自己快速排序调用轴以上对自己快速排序结束heap_adjust(a,i,a.length,move_count,judge_count);}for(inti=a.length;i1;--i){swap(a.num[1],a.num[i]);move_count+=3;heap_adjust(a,1,i-1,move_count,judge_count);}}4．直接插入排序voidinsertSort(NUM&a,int&move_count,int&judge_count){0非0开始i=a.length/2i0调用一次堆排序函数i=a.lengthi0Swap(a.num[1],a.num[i])Count+=3调用一次堆排序函数结束a.num[0]=a.length;for(inti=2;i=a.length;i++){if(a.num[i]a.num[i-1]){intj;a.num[0]=a.num[i];a.num[i]=a.num[i-1];move_count+=2;++judge_count;for(j=i-2;a.num[0]a.num[j];--j){++judge_count;++move_count;a.num[j+1]=a.num[j];}//endifa.num[j+1]=a.num[0];++move_count;}//endif}//endforreturn;}四、调试分析1.快速排序产生死循环，没有结果输出。在74219426这组测试数据中，由于开始没有等号，当privotkey=a.num[high]=4时产生了死循环。2.栈溢出。我们都知道递归是用栈实现，但是在中的high传参数时用成了a.length导致了死递归，导致了栈溢出。五、用户手册功能：统计在快速排序、堆排序、直接插入排序中，数字的移动次数和判断次数。并且输出排序后的序列。使用说明：输入数字的长度和数字然后回车。试例：六、测试结果测试数据1：72419426预期输出结果1：12244679快速排序移动次数：24判断次数：20直接插入排序移动次数：25判断次数：13堆排序移动次数：54判断次数：25测试数据2：12345预期输出结果：12345快速排序移动次数：28判断次数：14直接插入排序移动次数：0判断次数：0堆排序移动次数：28判断次数：10七、源程序清单#includestdafx.h#includeiostreamusingnamespacestd;typedefstruct{intlength;intnum[101];}NUM;voidinsertSort(NUM&a,int&move_count,int&judge_count){a.num[0]=a.length;for(inti=2;i=a.length;i++){if(a.num[i]a.num[i-1]){intj;a.num[0]=a.num[i];a.num[i]=a.num[i-1];move_count+=2;++judge_count;for(j=i-2;a.num[0]a.num[j];--j){++judge_count;++move_count;a.num[j+1]=a.num[j];}//endifa.num[j+1]=a.num[0];++move_count;}//endif}//endforreturn;}intone_quick_sort(NUM&a,intL,intH,int&move_count,int&judege_count){intprivotkey=a.num[L];intlow=L;inthigh=H;a.num[0]=privotkey;++move_count;while(lowhigh){while(lowhigh&&privotkey=a.num[high]){--high;++judege_count;}a.num[low]=a.num[high];++move_count;while(lowhigh&&privotkey=a.num[low]){++low;++judege_count;}a.num[high]=a.num[low];++move_count;}a.num[low]=privotkey;++move_count;returnlow;}voidquick_sort(NUM&a,intl,inth,int&move_count,int&judge_count){intlow=l;inthigh=h;intm;if(lowhigh){m=one_quick_sort(a,low,high,move_count,judge_count);quick_sort(a,1,m-1,move_count,judge_count);quick_sort(a,m+1,high,move_count,judge_count);}}intjudge(inta,intb,int&count){++count;if(a=b)return1;return0;}voidheap_adjust(NUM&a,ints,intm,int&move_count,int&judge_count){intrc=a.num[s];++move_count;for(intj=2*s;j=m;j*=2){if(jm&&!judge(a.num[j],a.num[j+1],judge_count)){j++;}if(judge(rc,a.num[j],judge_count)){break;}a.num[s]=a.num[j];++move_count;s=j;}a.num[s]=rc;++move_count;}voidswap(int&a,int&b){ints;s=a;a=b;b=s;}voidheap_sort(NUM&a,int&move_count,int&judge_count){for(inti=a.length/2;i0;--i){heap_adjust(a,i,a.length,move_count,judge_count);}for(inti=a.length;i1;--i){swap(a.num[1],a.num[i]);move_count+=3;heap_adjust(a,1,i-1,move_count,judge_count);}}int_tmain(intargc,_TCHAR*argv[]){NUMa,b,c;coutpleaseinputlengthofthenumber:endl;cina.length;b.length=a.length;c.length=b.length;coutpleaseinputthenumber:endl;for(inti=1;i=a.length;i++){cina.num[i];b.num[i]=a.num[i];c.num[i]=a.num[i];}intmove_count=0;intjudge_count=0;//快¨¬速¨´排?序¨°coutquicksort:endl;quick_sort(a,1,a.length,move_count,judge_count);coutmove_judge:move_countjudge_count:judge_countendl;coutafterquick_sortthenumberis:endl;for(inti=1;i=a.length;i++){couta.num[i];}//直¡À接¨®插?入¨?排?序¨°coutendlendl;move_count=0;judge_count=0;coutinsert_sortsort:endl;insertSort(b,move_count,judge_count);coutmove_count:move_countjudege_count:judge_countendl;coutafterinsert_sortthenumberis:endl;for(inti=1;i=b.length;i++)coutb.num[i];coutendl;//堆?排?序¨°move_count=0;judge_count=0;coutheap_sortsort:;heap_sort(c,move_count,judge_count);coutmove_count:move_countjudge_count:judge_countendl;coutafterheap_sortthenumberis:endl;for(inti=c.length;i=1;--i){coutc.num[i];}coutendl;return0;}