实验13-快速排序课程实习报告.docx

《实验13-快速排序课程实习报告.docx》由会员分享，可在线阅读，更多相关《实验13-快速排序课程实习报告.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、HUNAN UNIVERSITY课程实习报告实验13快速排序背景排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有 序”的记录序列。假设含个记录的序列为 Ri, R2,，Rn 其相应的关键字序列为 K1, K2,，Kn 这些关键字相互之间可以进行比拟，即在它们之间存在着这样一个关系：KpWKp2WKpn按此固有关系将上式记录序列重新排列为 Rpl,&2,，Rpn 的操作称作排序。排序算法是计算机科学中最重要的研究问题之一。对于排序的研究既有理论上的重要意 义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学 等领域具有广泛应用。常见的排序算

2、法有起泡排序、直接插入排序、简单项选择择排序、快速 排序、堆排序等。例1:有时候应用程序本身就需要对信息进行排序。为了准备客户账目，银行需要根据 支票的号码对支票排序；例2：在一个绘制互相重叠的图形对象的程序中，可能需要根据一个“在上方”关系将 各对象排序，以便自下而上地绘出对象。例3：在一个由n个数构成的集合上，求集合中第i小/大的数。例4：对一个含有n个元数的集合，求解中位数、k分位数。问题描述在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地 做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需 要等待。虽然所有任务的处理时间不能降低

3、，但我们可以安排它们的处理顺序，将耗时少的 任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。只需要将n件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有n 件任务同时来临时，每件任务需要用时求让所有任务等待的时间和最小的任务处理顺序。基本要求(1)数据的输入输出格式：输入：第一行是一个整数n,代表任务的件数。接下来一行，有n个正整数，代表每件任务所用的时间。输出:输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理 的任务所用的时间。按此顺序进行，那么使得所有任务等待时间最小。（2）使用快速排序，轴值采用随机数确定。测试数据输入9534261

4、573输出123345567一、实验目的快速排序1、熟悉和掌握快速排序的基本思想。2、了解并掌握快速排序的结构。3、掌 握和熟悉内部排序中快速排序的实现方法。二、实验预备知识快速排序是由起 泡排序改进而得来的。起泡排序的算法思想是：通过无序区中相邻纪录关键字 间的比拟和位置的交换，使关键字最小 的纪录如气泡一般逐渐往上“漂浮”直 至“水面”。整个算法是从最下面的纪录开始，对每两个相邻的关键字进行比 较，且使关键字较小的纪录换至关键字较大的纪录之上。，使得经过一趟起泡 排序后，关 键字最小的记录到达最上端，接着，再在剩下的纪录中找关键字最 小的纪录，并把它换在第二个位置上。依次类推，一直到所有记

5、录都有序为止。 快速排序的基本思想是在待排序的n个记录中任选一个记录，将 该纪录放入 最终位置后，数据序列被分割成两局部。所有关键字比拟 该纪录关键字小的放 置在前一局部，所有比他大的放置在后一局部，并将该纪录排在这两局部的中 间，这个过程称作一趟快速排序。之后 对分割成的两局部分别重复上述过程，直 到每个局部内只有一个记录为止。快速排序是不稳定的。从平均时间性能而言，快速排序最正确，其时间复杂性为0(nlog2n)。但在最坏情况下，即对几乎是排序好的输入序列，该算法的效率很低，近似于 0(n2)。对于较小的n值,该算法效果不明显；反之，对较大的n值，效果较好。 初始关键字 第一趟排序后 第二

6、趟排序后 第三趟排序后 第四趟排序后70 68 18 11 11 73 11 11 18 18 69 69 23 23 93 18 11 68 73 73 73 9318 70 9323 68 69 70 93 23 23 68 68 69 69 70 93 70 73三、实验内容 从时间上看，快速排序的平均性能优于其它各种排序方法，从空间 上看，快速排序只需一个栈空间来实现递归。最坏的情况下，一个长度为n的 序列，其快速排序所需栈的最大深度为n。最小深度为0 (logn) o实验基本思 想：设有n个记录的序列，运用快速排序法将其按升序排列，并输出排列结果。 实验源程序算法如下：quickso

7、rt (int r, int s, int t) /*把 rs至 rt的元素进行快速排序*/ int i=s; int j=t; if (st) r0=rs ; /*r0为监视哨*/ do while(i=r0) j; if(ij) ri=rj;i+; while(ij&ri=r0) i+; if(ij) rj=ri;j-; while (ij) ; r i=r 0 ; quicksort (r, s, j-l);quicksort (r, j+1, t) ; /*递归调用快速排序*/四、实验要求1、依据以上算法函数写出一组序列的快速排序程序。2、写出调 试运行的分析和体会。3、写出每趟排序的

8、结果和实验报告。ftinclude ttinclude void quicksort (int r, int s, int t) 排序*/ int m;/*m 为监视哨*/ int i=s; int j=t; if (st)/*把rs至rt的元素进行快速 m=rs; do while (i=m) j; if (ij) ri=rj; i+; while(ij&ri=m) i+; if(ij) rj=ri; j-; while(ij); ri=m; quicksort (r, s, j-1) ; quicksort (r, j+1, t) ; /*递归调用快速排序*/ int main (void

9、) int a12 = 67, 1,3, 4, 12,8, 9, 0, 5,43, 55, 15), i;quicksort (a, 0, 11) ; for (i=0; i12; i+) printf (d , ai) ; return 0; 五、 强化与提高 1、序列503, 55, 78, 99, 10, 953, 487, 41, 13, 776, 314, 采用快速排序对该序列作降序排序时的每一趟结果。2、对于快速排序的非递归 算法，可用队列实现吗？说明理由。3、写出快速排序的非递归算法。template void Orderedlist:QuickSort(const int le

10、ft,const int right) if(leftright)/递归算法，对象序列长度大于1,那么递归int pivotpos二Partition(left,right);进行分区，趟排序QuickSort(left,pivotpos-1); 处理左侧子序列QuickSort(pivotpos+l,right); 处理右侧子序列)template int Orderedlist:Partition (const int low,const int high) int i=lowj=high;T pivot=slistlow; /选基准对象dowhile(slistj=pivot)&(ij)

11、j-; 注意 j 从右向左扫描if(ij) slisti+=slistj;/注意，仅仅是slisti+装入slistfj内容，slistj并没有装入 slisti+内容，因为slistLj将要放的内容是pivot,现在不急于填,见图1.10为空框while(slisti=pivot)&( ij) i+; i从左向右扫描if(ij) slistj-=slisti;注意上一个if的i后+和本次的j后-，表示交换后再移动一个元素位置while(i!=j);slisti=pivot; /最后把空框填入，多设一个pivot,中间每步交换步骤省2/3 return i;)if(slistmidx) mid

12、=Binarysearch(slist,x,low,mid-l);中间点大于定值，查找左区间，注意mid-1)if(slistmid!=x) mid-1;return mid;找到返回下标，未找到但结束了，返回mid=-l)int main()const int h=19;int i,k=47;int ah=2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67;for(i=0;ivh;i+) coutai,t,;coutendl;i=Binarysearch(a,k,O,h-1);if(i-l) coutvv”系数”kvv”在表中位置(下标)：niendl;else coutvv系数kv不存在endl;k=33;i=Binarysearch(a,k,O,h-l);系数vvkvv”在表中位置(下标)：niendl;else coutvv系数不存在endl;return 0;