数据结构实验八快速排序

HUNANUNIVERSITY课程实验报告题目：快速排序学生姓名学生学号专业班级指导老师李晓鸿完成日期2015年1月7日一、需求分析1．程序的功能由用户输入任务件数和任务时间，使用快速排序，输出使得所有任务等待时间最小的序列。2.输入的形式本程序由用户输入任务总数以及每个任务所花时间，中间用空格或换行隔开，任务总数必须为正整数。请输入任务总数：请输入各个任务所花时间：3.输出形式在对这些任务所花时间进行快速排序后，将这些数据从小到大输出任务时间。任务所花时间的排序如下：4.测试数据1.请输入任务总数：9请输入各个任务所花时间：534261573任务所花时间从小到大的排序如下：1233455672.请输入任务总数：10请输入各个任务所花时间：6512354861任务所花时间从小到大的排序如下：11234556683.请输入任务总数：6请输入各个任务所花时间：10101945235任务所花时间从小到大的排序如下：510101923454.请输入任务总数：8请输入各个任务所花时间：87654321任务所花时间从小到大的排序如下：123456785.请输入任务总数：10请输入各个任务所花时间：24681012142615任务所花时间从小到大的排序如下：01246812141526二、概要设计1.抽象数据类型将每一个元素储存在一个有序并且有限的序列中，每一个元素都有一个自己的位置，也都有一个数据类型，所以使用线性表来储存各个任务所花的时间。2.ADTADTalist{数据对象：定义线性表的最大储存元素maxsize;当前储存元素数listsize;数据关系：若listsize=0,则线性表没有元素，为空;基本操作：alist(intn)//构造函数~alist()//析构函数boolappend(inta)//增加元素}3.算法的基本思想设要排序的线性表中元素是A[0]……A[N-1]，首先通过时间函数余作为关键数据piot，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，通过前后指针的移动，实现快速排序。再将piot值左右两边的线性表进行快速排序，直到需要快速排序的线性表只有1个元素。4.程序基本流程程序分为三个模块：输入模块：由用户读入任务总数n以及各个任务所花时间；排序模块：对这些时间进行快速排序；输出模块：输出排序后的序列。三．详细设计1.物理数据类型由于线性表长度已知，并且进行大量的交换操作，所以使用顺序表来实现。顺序表的伪代码classalist{public:intmaxsize;intlistsize;int*listarry;alist(intn){maxsize=n;listsize=0;listarry=newint[maxsize];}~alist(){delete[]listarry;}boolappend(inta){if(listsize==maxsize)returnfalse;listarry[listsize++]=a;returntrue;}};2.详细设计获取piot值——partation——quicksort获取piot值：获取随机数，通过随机数获得piot值。为了防止随机数大于所有数，对随机数就行求余，对求余后的值加1（防止左边界为0，右边界为1的情况，（r+l）/2==0）.intfindpiot(inta,intb){srand(time(0));intn=rand()%((a+b)/2+1);returnn;}partation（划分）：开始参数l.r紧挨要分割子线性表的实际边界。每一轮执行外层do循环时，l和r都将向的线性表中间移动，若在移动过程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交换l和r所对应的值，再次移动，直到它们交叉为止。intpartition(intl,intr,int&pivot){do{while(listarry[++l]pivot);while((r!=0)&&(listarry[--r]pivot));swap(l,r);}while(lr);swap(l,r);returnl;}quicksort（快速排序）：通过递归，获取piot值后，对线性表从位置i到位置j进行一次划分，通过k值获得排序后poit值所在位置，对起始位置i到k和k+1到末尾j再次快速排序。voidqsort(inti,intj){if(j=i)return;intpivotindex=findpiot(i,j);intk=partition(i-1,j,listarry[j]);swap(k,j);qsort(i,k-1);qsort(k+1,j);}3．算法的时空分析及改进设想最好情况O（nlogn），最差情况（n^2）4.输入和输出的格式输入：输入任务数量，任务时间：请输入任务数:.....请输入任务时间:......cout输入任务数\n;cinn;alista(n);cout输入任务时间\n;for(inti=0;in;i++){cintemp;a.append(temp);}输出：任务所花时间排序如下：.........cout任务所花时间排序如下\n;for(inti=0;in;i++)couta.listarry[i];coutendl;四．测试结果测试1测试2测试3测试4测试5五．试验心得书上快速排序十分详细，用抽象数据类型做也就多了定义类。六．附录#includeiostream#includetime.husingnamespacestd;classalist{public:intmaxsize;intlistsize;int*listarry;alist(intn){maxsize=n;listsize=0;listarry=newint[maxsize];}~alist(){delete[]listarry;}boolappend(inta){if(listsize==maxsize)returnfalse;listarry[listsize++]=a;returntrue;}intfindpiot(inta,intb){srand(time(0));intn=rand()%((a+b)/2);returnn;}intpartition(intl,intr,int&pivot){do{while(listarry[++l]pivot);while((r!=0)&&(listarry[--r]pivot));swap(l,r);}while(lr);swap(l,r);returnl;}voidqsort(inti,intj){if(j=i)return;intpivotindex=findpiot(i,j);intk=partition(i-1,j,listarry[j]);swap(k,j);qsort(i,k-1);qsort(k+1,j);}voidswap(inta,intb){inttemp;temp=listarry[a];listarry[a]=listarry[b];listarry[b]=temp;}};intmain(){intn,temp;cout输入任务数\n;cinn;alista(n);cout输入任务时间\n;for(inti=0;in;i++){cintemp;a.append(temp);}coutendl;a.qsort(0,n-1);cout任务所花时间排序如下\n;for(inti=0;in;i++)couta.listarry[i];coutendl;system(pause);return0;}