数据结构实验八-快速排序实验报告.doc
数据结构实验课程最终报告题 目：实验八快速排序专业班级：计算机科学与技术姓 名：XX学 号：指导老师: 李晓鸿完成日期:205、01、06一、 需求分析背景排序就是计算机内经常进行得一种操作,其目得就是将一组“无序”得记录序列调整为“有序"得记录序列。假设含n个记录得序列为R1， R2, ， R 其相应得关键字序列为 K， K2, ,Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： p1Kp2Kp按此固有关系将上式记录序列重新排列为 Rp1， Rp2,，Rpn得操作称作排序。排序算法就是计算机科学中最重要得研究问题之一.对于排序得研究既有理论上得重要意义，又有实际应用价值.它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见得排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。例:有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据支票得号码对支票排序；例2：在一个绘制互相重叠得图形对象得程序中，可能需要根据一个“在上方”关系将各对象排序,以便自下而上地绘出对象。例3：在一个由n个数构成得集合上,求集合中第i小/大得数。例4：对一个含有个元数得集合,求解中位数、k分位数.1. 问题描述在操作系统中，我们总就是希望以最短得时间处理完所有得任务。但事情总就是要一件件地做,任务也要操作系统一件件地处理。当操作系统处理一件任务时，其她待处理得任务就需要等待。虽然所有任务得处理时间不能降低,但我们可以安排它们得处理顺序,将耗时少得任务先处理,耗时多得任务后处理，这样就可以使所有任务等待得时间与最小。只需要将n 件任务按用时去从小到大排序，就可以得到任务依次得处理顺序.当有n 件任务同时来临时，每件任务需要用时n，求让所有任务等待得时间与最小得任务处理顺序.2. 程序要求实现得功能当有 n 件任务同时来临时,每件任务需要用时i,求出让所有任务等待得时间与最小得任务处理顺序。3. 输入输出要求a) 输入要求：第一行就是一个整数n，代表任务得件数。接下来一行,有n个正整数，代表每件任务所用得时间.b) 输出要求:输出有n行，每行一个正整数,从第一行到最后一行依次代表着操作系统要处理得任务所用得时间.按此顺序进行,则使得所有任务等待时间最小。4. 测试数据1. 输入:请输入任务件数：-1输出： 输入有误，请重新输入！2. 输入： 请输入任务件数:4请输入各任务所需时间：2 3 输出：输入有误，请重新输入！3. 输入：请输入任务件数：4请输入各任务所需时间：24 3 6输出:任务执行得先后顺序为： 2 3 4 4. 输入： 请输入任务件数：请输入各任务所需时间:5 3 4 2 1 3输出：任务执行得先后顺序为:12335567二、 概要设计(一) 函数调用关系图主函数void QuickSort(int a,int start,int end);void QuickSort(int a,int start,int end); int Partition(int a,int start,int end); int random(int start,int end) ;void change(int a,int i,int j); 三、 详细设计（一)物理数据类型本程序所输入得任务件数与任务时间均为整数，可使用整数 int实现数据得存储。使用数组实现快速排序。(二)具体步骤与伪代码1. 输入任务件数及任务时长 whie（1）cut请输入任务件数: ”; cn>>iz; wle(ie)/任务件数大于0,则执行该循环,否则重新输入件数inti；co”请输入各任务所需时间："； for(i0；isize；i+）cinai；if（ai<=0）cout"输入有误，请重新输入！<enl；break；if(i=size）beak; ut"输入有误，请重新输入！”endl；2. 调用函数取随机轴值int am(int art，in ed） n t; srand(im（LL）);/设置随机数种子,对多组数据排序时不会取相同得轴值he(） t=rand（)%（en1)； f（t=strt) reurn t; 3. 数组中得两个元素交换位置voidcge（int ，in i，nt j） itt； t=i; ai=j； t; 4. 快速排序时对数据进行划分区域intartiton（int a，nt，int d) ntem=ando(sa，n);/得到随机轴值 ng(a，em，nd）；i i=sart-1;/用来指示轴值之后插入得位置nt e=en; 以最后一个数作为划分得基点fo（nt j=sat；jend;j+）if（aj=base)i+；change（a，）;hne(a，+1，e）;etn i； 5. 快速排序void QuckSot(int aN，int tart，intend) if（endtrt)retur；/没有数据或只有一个数据 if（and)/大于1个数据 it =Partiton（，sar,end）；/划分区域/对两个区域分别进行快排QSor（a，stt,1）； Quicort（，i1,d）； （三) 算法得具体步骤1) 通过用户输入任务件数n及任务时长，并对输入合法性进行验证;若合法,则进行下一步,否则重新输入；2) 通过调用random()函数,获取非负且小于n得随机数，该随机数作为下标所表示得元素作为轴值;3) 根据所得轴值，进行快速排序.所有元素比基准值小得摆放在基准前面,所有元素比基准值大得摆在基准得后面(相同得数可以到任一边）。在这个分割结束之后，该基准就处于数列得中间位置。原本数列被划分为两部分4) 递归地把小于基准值元素得子数列与大于基准值元素得子数列排序. 5) 递归得基例就是数列得大小就是零或一,此时排序完成输出排序后得数列结果到界面。四、 输入输出格式输入:a. 输入任务件数cot”请输入任务件数: ”; cinsiz；b. 输入每件任务时长cu<<”请输入各任务所需时间："； for(i=0;i<siz；i）cin>>ai；输出：1、输入不合法:if（size<=0)t输入有误，请重新输入！end；f（ai<=0）cout<"输入有误，请重新输入！”endl；brea;2、输入合法，输出排序后得数列:cout<"任务执行得先后顺序为: "endl； fo（i=1；isize;i+) cot<<” ”<<enl; 五、 调试分析六、 实验心得在调试过程中，由于轴值得插入位置标记错误，所以排序结果一直出错，后来查找很久才发现该错误。以后会注意不会再此处犯错。
