存储管理查找和排序 实验

1、存储管理、查找和排序班级：软件102 姓名：学号： 完成日期：2011.12.16题目：内部排序算法比较问题描述：通过随机数据比较各算法的关键字比较次数与移动次数基本要求：至少比较快速排序与堆排序。对结果进行简单分析一、 需求分析功能： 对给定的数进行排序，并统计关键字的比较次数和移动次数输入： 要进行统计数的个数和这些数输出： 关键字的比较次数和移动次数和排序后的序列测试数据：测试数据1：7 2 4 1 9 4 2 6 预期输出结果1：1 2 2 4 4 6 7 9快速排序移动次数：24 判断次数：20直接插入排序移动次数：25 判断次数：13堆排序移动次数：54 判断次数：25测试数据2：

2、1 2 3 4 5 预期输出结果：1 2 3 4 5快速排序移动次数：28 判断次数：14直接插入排序移动次数：0 判断次数：0堆排序移动次数：28 判断次数：10二、概要设计由题目知，我们创建一个结构体存储数据的长度和数据，并且需要写出快速排序、堆排序和直接插入排序的代码。 模块：1结构体2快速排序算法3直接插入排序算法4堆排序算法三、详细设计1. 结构体： typedef structint length;int num101;NUM;2快速排序void quick_sort(NUM &a,int l,int h,int &move_count,int &judge_count)int l

3、ow=l;int high=h;int m;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);非0开始Low0;-i)heap_adjust(a,i,a.length,move_count,judge_count);for (int i=a.length;i1;-i)swap(a.num1,a.numi);move_count+=3;heap

4、_adjust(a,1,i-1,move_count,judge_count);0非0开始i=a.length/2i0调用一次堆排序函数i=a.lengthi0Swap(a.num1,a.numi)Count+=3调用一次堆排序函数结束4直接插入排序void insertSort(NUM &a,int &move_count,int &judge_count)a.num0=a.length;for (int i=2;i=a.length;i+)if(a.numia.numi-1)int j;a.num0=a.numi;a.numi=a.numi-1;move_count+=2;+judge_c

5、ount;for( j=i-2;a.num0a.numj;-j)+judge_count;+move_count;a.numj+1=a.numj;/end ifa.numj+1=a.num0;+move_count;/end if/end forreturn ;四、调试分析1.快速排序产生死循环，没有结果输出。在7 4 2 1 9 4 2 6这组测试数据中，由于开始没有等号，当privotkey=a.numhigh=4时产生了死循环。2.栈溢出。我们都知道递归是用栈实现，但是在中的high传参数时用成了a.length导致了死递归，导致了栈溢出。五、用户手册功能：统计在快速排序、堆排序、直接插

6、入排序中，数字的移动次数和判断次数。并且输出排序后的序列。使用说明：输入数字的长度和数字然后回车。试例：六、测试结果测试数据1：7 2 4 1 9 4 2 6 预期输出结果1：1 2 2 4 4 6 7 9快速排序移动次数：24 判断次数：20直接插入排序移动次数：25 判断次数：13堆排序移动次数：54 判断次数：25测试数据2：1 2 3 4 5 预期输出结果：1 2 3 4 5快速排序移动次数：28 判断次数：14直接插入排序移动次数：0 判断次数：0堆排序移动次数：28 判断次数：10七、源程序清单#include stdafx.h#include using namespace st

7、d;typedef structint length;int num101;NUM;void insertSort(NUM &a,int &move_count,int &judge_count)a.num0=a.length;for (int i=2;i=a.length;i+)if(a.numia.numi-1)int j;a.num0=a.numi;a.numi=a.numi-1;move_count+=2;+judge_count;for( j=i-2;a.num0a.numj;-j)+judge_count;+move_count;a.numj+1=a.numj;/end ifa.n

8、umj+1=a.num0;+move_count;/end if/end forreturn ;int one_quick_sort(NUM &a,int L,int H,int &move_count,int &judege_count)int privotkey=a.numL;int low=L;int high=H;a.num0=privotkey;+move_count;while(lowhigh)while(lowhigh&privotkey=a.numhigh)-high;+judege_count;a.numlow=a.numhigh;+move_count;while(low=

9、a.numlow)+low;+judege_count; a.numhigh=a.numlow;+move_count;a.numlow=privotkey;+move_count;return low;void quick_sort(NUM &a,int l,int h,int &move_count,int &judge_count)int low=l;int high=h;int m;if (lowhigh)m=one_quick_sort(a,low,high,move_count,judge_count);quick_sort(a,1,m-1,move_count,judge_cou

10、nt);quick_sort(a,m+1,high,move_count,judge_count);int judge(int a,int b,int &count)+count;if(a=b)return 1;return 0;void heap_adjust(NUM &a,int s,int m,int &move_count,int &judge_count)int rc=a.nums;+move_count;for (int j=2*s;j=m;j*=2)if (j0;-i)heap_adjust(a,i,a.length,move_count,judge_count);for (in

11、t i=a.length;i1;-i)swap(a.num1,a.numi);move_count+=3;heap_adjust(a,1,i-1,move_count,judge_count);int _tmain(int argc, _TCHAR* argv)NUM a,b,c;coutplease input length of the number:a.length;b.length=a.length;c.length=b.length;coutplease input the number:endl;for (int i=1;ia.numi;b.numi=a.numi;c.numi=a

12、.numi;int move_count=0;int judge_count=0;/快速排?序coutquick sort:endl;quick_sort(a,1,a.length,move_count,judge_count);coutmove_judge:move_count judge_count:judge_countendl ;coutafter quick_sort the number is:endl;for (int i=1;i=a.length;i+)couta.numi ;/直接插?入?排?序coutendlendl;move_count=0;judge_count=0;coutinsert_sort sort:endl;insertSort(b,move_count,judge_count);coutmove_count:move_count judege_count:judge_count endl;coutafter insert_sort the number is:endl;for (int i=1;i=b.length;i+)coutb.numi ;coutendl;/堆?排?序move_c