数据结构实验八快速排序实验报告

《数据结构实验八快速排序实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANUNIVERSITY数据结构实验课程最终报告题目：实验八快速排序专业班级:计算机科学与技术姓名:XXX学号：指导老师：李晓鸿完成日期：2015・01・06需求分析背景排序是计算机内经常进行的一种操作，其冃的是将一组“无序”的记录序列调整为“有序”的记录序列。假设含n个记录的序列为｛Ri,Rs…，Rn）其相应的关键字序列为｛Ki,心，・・・，Kn｝这些关键字相互Z间可以进行比较，即在它们Z间存在着这样一个关系：Kp】WKp2W・・・WKpn按此固有关系将上式记录序列重新排列为｛Rpl,Rp2,…，R“｝的操作称作排序。排序算法是

2、计算机科学屮最重要的研究问题么一。对于排序的研究既有理论上的重要意义,又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识別、及统计学等领域具有广泛应用。常见的排序算法冇起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。例1：有吋候应用程序木身就需要对拮息进行排序。为了准备客八账目，银行需要根据支票的号码对支票排序；例2：在一个绘制互相重叠的图形对彖的程序■!«,nJ能需耍根据一个“在上方”关系将各对象排序，以便自下而上地绘出対象。例3：在一个由n个数构成的集合上，求集合中第i小/大的数。例4：对一个含有n个元数的集

3、合，求解屮位数、k分位数。1•问题描述在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。只需要将n件任务按用时去从小到大排序，就町以得到任务依次的处理顺序。当有n件任务同时来临时,每件任务需要用时m,求让所有任务等待的时间和最小的任务处理顺序。2.程序要求实现的功能当有n件任务同时来临

4、时，每件任务需要用时ni,求出让所有任务等待的吋间和授小的任务处理顺序。3.输入输出要求a）输入要求：第一行是一个整数n,代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间。b）输出要求：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。4.测试数据1.输入：请输入任务件数：-1输出：输入有误，请重新输入！2.输入：请输入任务件数：4请输入各任务所需时间：2430输出:输入有误，请重新输入！1.输入：请输入任务件数：4请输入各任务所需时间：24

5、36输出：任务执行的先后顺序为：23462.输入：请输入任务件数：9请输入各任务所需时间：534261573输出:任务执行的先后顺序为：123345567二、概要设计(-)函数调用关系图intrandom(intstart,intend);voidQuickSort(inta[],intstart,intend);intPartition(inta[],intstart,intend);voidchange(inta[],inti,intj);voidQuickSort(inta[],intstart,intend);详细设计(一)物理

6、数据类型木程序所输入的任务件数和任务时间均为整数，可使用整数int实现数据的存储。使用数组实现快速排序。(二)具体步骤和伪代码1.输入任务件数及任务时长while(l){cout«/z请输入任务件数："；cin>>size;while(size)//任务件数大于0,则执行该循环，否则重新输入件数{inti;cout«，z请输入各任务所需时间:〃；for(i=0;i>a[i];if(a[i]<=0){cout«z，输入有误，请重新输入！"<〈endl;break;}}if(i==size)break;}cou

7、t«z/输入有误，请重新输入!，，«endl;2.调用函数取随机轴值intrandom(intstart,intend)intt;srand(time(NULL))；〃设置随机数种子，对多组数据排序时不会取相同的轴值whi1e(1){t=rand()%(end+l);if(t>二start)returnt;}}1.数组中的两个元素交换位置voidchange(inta[N],inti,intj){intt;t=a[i];a[i]=a[j];}2.快速排序时对数据进行划分区域intPartition(irita[],intstart,in

8、tend){inttemp=random(start,end);//得到随机轴值changc(a,temp,end);inti=start-l;//i用来指示轴值之后插入的位置intbase=a[end];