实验八 快速排序.doc

HUNAN UNIVERSITY课程预习报告题 目： 快速排序 学生姓名 学生学号 2012080102 专业班级 计算机科学与技术班 完 成 日 期 4 一、需求分析输入的形式和输入值的范围：第一行是一个整数n，代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间。中间用空格或者回车隔开。不对非法输入做处理，及假设用户输入都是合法的。输出的形式：输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。程序所能达到的功能：在操作系统中，当有 n 件任务同时来临时，每件任务需要用时ni，输出所有任务等待的时间和最小的任务处理顺序。测试数据：输入请输入任务个数：9请输入任务用时：5 3 4 2 6 1 5 7 3输出任务执行的顺序：1 2 3 3 4 5 5 6 7二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的第一个输入。并将随后输入的一组数据储存在整数数组中。算法的基本思想如果将任务按完成时间从小到大排序，则在完成前一项任务时后面任务等待的时间总和最小，即得到最小的任务处理顺序。采取对输入的任务时间进行快速排序的方法可以在相对较小的时间复杂度下得到从小到大的顺序序列。三、详细设计实现概要设计中定义的所有数据类型：第一次输入的正整数要求大于零，为了能够存储，采用int型定义变量。接下来输入的一组整数，数据范围大于零，为了排序需要，采用线性结构存储，即int类型的数组。实现程序的具体步骤：程序主要采取快速排序的方法处理无序数列：1在序列中根据随机数确定轴值，根据轴值将序列划分为比轴值小和比轴值大的两个子序列。2对每个子序列采取从左右两边向中间搜索的方式，不断将值与轴值比较，如果左边的值大于轴值而右边的小于轴值则将二者交换，直到左右交叉。3分别对处理完毕的两个子序列递归地采取1，2步的操作，直到子序列中只有一个元素。程序各模块的伪代码：主函数int main() int n; coutn; int an; cout请输入任务用时：; for(int i=0;iai; qsort(a,0,n-1);/调用“快排函数” cout任务执行的顺序：; for(int i=0;in;i+)coutai ; /输出排序结果快速排序算法：void qsort(int a,int i,int j) if(j=i)return;/只有一个元素 int pivotindex=findpivot(a,i,j);/调用“轴值寻找函数”确定轴值 swap(a,pivotindex,j);/调用“交换函数”将轴值置末 int k=partition(a,i-1,j,aj);/调用“分割函数”根据轴值分割序列 swap(a,k,j); qsort(a,i,k-1);/递归调用，实现子序列的调序 qsort(a,k+1,j); 轴值寻找算法：/为了保证轴值的“随机性”，采用时间初始化种子。int findpivot(int a,int i,int j) srand(unsigned int)time(NULL); int n=rand()%(j-i+1)+i; /返回传入范围内的轴值 数据交换算法：void swap(int a,int i,int j) int temp; temp=ai; ai=aj; aj=temp; 序列分割算法：int partition(int a,int l,int r,int &pivot) do while(a+lpivot); swap(a,l,r); while(lr); swap(a,l,r); return l;/返回右边部分的首位置 算法的时空分析对于长度为n的序列，进行快速排序的效率取决于对主值的选择。随机化快速排序虽然在最坏情况下的时间复杂度仍然是O(n2），但是随机数取值不佳的概率比较低，所以大部分能够达到O(nlogn）的时间复杂度。另输入输出的时间复杂度为（n）。所以该算法的时间复杂度为O(nlogn）。函数的调用关系图输入Findpivot 确定轴值Swap 交换快排主函数Pa