实验八快速排序

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

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

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

3、3692393181168]第一趟排序后[6811692318]70[9373]第二趟排序后[181123]68[69]70[9373]第三趟排序后111823686970[93731第四趟排序后1118236869707393一.实验内容从时间上看，快速排序的平均性能优于英它各种排序方法，从空间上看，快速排序只需一个栈空间来实现递归。最坏的情况下，一个长度为n的序列，其快速排序所需栈的最大深度为no最小深度为O(logn)o实验基本思想：设有n个记录的序列，运用快速排序法将其按升序排列，并输出排列结果。实验源程序算法如下：quicksort(intr[]

4、,ints,intt)/*把r[s]至r[t]的元素进行快速排序*/{inti=s;intj=t;if(s=r[01)j-;r[i]=r[j]；i++；while(i

5、写出每趟排序的结果和实验报告。#include#includevoidquicksort(intr[],ints,intt)排序*/{intm;/*m为监视哨*/inti=s;intj=t;/*把r[s]至r[t]的元素进行快速m=r[s];do{while(i=m)j—;{r[i]=r[j]；i++；}while(i

6、rt(rj+l,t);intmain(void)inta[12]={67,l,3,4,12,8,9,O,5,43,55,15},i;quicksort(a,0,l1);foT(i二0;ivl2;i++)printf(n%d”,a[i]);return0;}五、强化与提高1、已知序歹!J{503,55,78,99,10,953,487,41,13,776,314},采用快速排序对该序列作降序排序时的每一趟结果。2、对于快速排序的非递归算法，可用队列实现吗？说明理由。3、写出快速排序的非递归算法。