数据结构实验八快速排序

1、HUNAN UNIVERSITY课程实验报告题 目： 快速排序 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日 期 2 0 1 5年 1月 7日 一、需求分析1程序的功能由用户输入任务件数和任务时间，使用快速排序，输出使得所有任务等待时间最小的序列。2.输入的形式本程序由用户输入任务总数以及每个任务所花时间，中间用空格或换行隔开，任务总数必须为正整数。请输入任务总数：请输入各个任务所花时间：3.输出形式在对这些任务所花时间进行快速排序后，将这些数据从小到大输出任务时间。任务所花时间的排序如下：4.测试数据1.请输入任务总数：9请输入各个任务所花时间：5 3 4 2 6 1 5

2、7 3任务所花时间从小到大的排序如下：1 2 3 3 4 5 5 6 7 2. 请输入任务总数： 10请输入各个任务所花时间：6 5 1 2 3 5 4 8 6 1 任务所花时间从小到大的排序如下：1 1 2 3 4 5 5 6 6 83. 请输入任务总数：6请输入各个任务所花时间：10 10 19 45 23 5 任务所花时间从小到大的排序如下：5 10 10 19 23 454. 请输入任务总数： 8请输入各个任务所花时间：8 7 6 5 4 3 2 1任务所花时间从小到大的排序如下： 1 2 3 4 5 6 7 85. 请输入任务总数： 10请输入各个任务所花时间：2 4 6 8 1 0

3、 12 14 26 15任务所花时间从小到大的排序如下：0 1 2 4 6 8 12 14 15 26二、概要设计1.抽象数据类型将每一个元素储存在一个有序并且有限的序列中，每一个元素都有一个自己的位置，也都有一个数据类型，所以使用线性表来储存各个任务所花的时间。2. ADTADT alist数据对象：定义线性表的最大储存元素maxsize; 当前储存元素数listsize;数据关系：若listsize=0,则线性表没有元素，为空;基本操作：alist(int n)/构造函数 alist()/析构函数 bool append(int a)/增加元素3.算法的基本思想 设要排序的线性表中元素是A

4、0AN-1，首先通过时间函数余作为关键数据piot，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，通过前后指针的移动，实现快速排序。再将piot值左右两边的线性表进行快速排序，直到需要快速排序的线性表只有1个元素。4.程序基本流程程序分为三个模块：输入模块：由用户读入任务总数n以及各个任务所花时间；排序模块：对这些时间进行快速排序；输出模块：输出排序后的序列。三详细设计1.物理数据类型由于线性表长度已知，并且进行大量的交换操作，所以使用顺序表来实现。顺序表的伪代码class alistpublic:int maxsize;int listsize;int* listarry;a

5、list(int n)maxsize = n;listsize = 0;listarry = new intmaxsize;alist()deletelistarry;bool append(int a)if (listsize = maxsize)return false;listarrylistsize+ = a;return true;2. 详细设计获取piot值partationquicksort获取piot值：获取随机数，通过随机数获得piot值。为了防止随机数大于所有数，对随机数就行求余，对求余后的值加1（防止左边界为0，右边界为1的情况，（r+l）/2=0）.int findpi

6、ot(int a, int b)srand(time(0);int n = rand() % (a+b)/2+1);return n;partation（划分）：开始参数l.r紧挨要分割子线性表的实际边界。每一轮执行外层do循环时，l和r都将向的线性表中间移动，若在移动过程中，l遇到比piot值大的值就停止，l遇到比piot小的就停止，交换l和r所对应的值，再次移动，直到它们交叉为止。int partition(int l, int r, int &pivot)dowhile (listarry+l pivot);swap( l, r); while (l r);swap( l, r);ret

7、urn l; quicksort（快速排序）：通过递归，获取piot值后，对线性表从位置i到位置j进行一次划分，通过k值获得排序后poit值所在位置，对起始位置i到k和k+1到末尾j再次快速排序。void qsort( int i, int j)if (j = i)return;int pivotindex = findpiot( i, j);int k = partition(i - 1, j, listarryj);swap( k, j);qsort( i, k - 1);qsort( k + 1, j);3 算法的时空分析及改进设想 最好情况O（nlogn），最差情况（n2）4. 输入和

8、输出的格式输入： 输入任务数量，任务时间：请输入任务数: .请输入任务时间: .cout n;alist a(n);cout 输入任务时间n;for (int i = 0; i temp;a.append(temp);输出：任务所花时间排序如下：.cout 任务所花时间排序如下n;for (int i = 0; i n; i+)cout a.listarryi ;cout endl;4 测试结果测试1测试2测试3测试4测试55 试验心得书上快速排序十分详细，用抽象数据类型做也就多了定义类。6 附录#includeiostream#includetime.husing namespace std

9、;class alistpublic:int maxsize;int listsize;int* listarry;alist(int n)maxsize = n;listsize = 0;listarry = new intmaxsize;alist()deletelistarry;bool append(int a)if (listsize = maxsize)return false;listarrylistsize+ = a;return true;int findpiot(int a, int b)srand(time(0);int n = rand() % (a+b)/2);ret

10、urn n;int partition(int l, int r, int &pivot)dowhile (listarry+l pivot);swap( l, r); while (l r);swap( l, r);return l;void qsort( int i, int j)if (j = i)return;int pivotindex = findpiot( i, j);int k = partition(i - 1, j, listarryj);swap( k, j);qsort( i, k - 1);qsort( k + 1, j);void swap( int a, int b)int temp;temp = listarrya;listarrya = listarryb;listarryb = temp;int main()int n,temp;cout n;alist a(n);cout 输入任