快速排序(算法与数据结构课程设计)

1、快速排序一、问题描述排序是数据结构中典型的算法，经常有插入排序、选择排序、快速排序等。本文要求对排序表中的无序数据进行快速排序，并讨论快速排序的改进方法(双倍快速排序、基于归并的快速排序)，这样可以对排序进行优化，提高效率。二、基本要求1、选择合适的存储结构建立排序表，并能遍历表输出元素。2、编写快速排序算法，并能够输出排序的结果。快速排序及其改进双倍快速排序和基于归并的快速排序算法。三、测试数据输入以下数据：5、3、7、11、1、9、4、8四、算法思想1、普通快速排序的基本思想：可以运用一趟快速排序把序列分成分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两

2、部分记录继续进行快速排序，以达到整个序列有序。一趟的快速排序是：附设两个指针low和high,它们的初值分别为low和high，设枢轴记录的关键字为pivotkey,则首先从high所指位置起向前搜索到第一个关键字小于pivotkey大的记录和枢轴记录互相交换，然后从low所指位置向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两部直至low二high为止。2、双倍快速排序思想：快速排序的基本思想是基于分支策略的思想。即对于输入的子序列Llow.high,如果规模足够小则直接进行排序，否则分三步处理：分解(Divide):设输入的序列Llow.High,确定支点元

3、素Llow和LHigh,并使LLow.key=LlHigh.key,然后分解(Divide):将序列Llow.High划分成三个子序列LLow.L-l、LL+1.H-1和LH+l.High,使Llow.High中元素的关系为LLow.L-1LLLL+1.H-1LHLH+1.High。递归求解(Conquer)：通过递归调用快速排序算法分别对LLow.L-l、LL+1.H-1和LH+l.High分别进行分解排序。合并(Merge)：对分解出的三个子序列的排序是就地进行的,所以在LLow.L-l、LL+1.H-1和LH+l.High都排好序后不需要执行任何计算Llow.High就已排好序。3、基于

4、归并的快速排序：对划分结果产生的两个子序列的长度进行检查，如果其中一个与另一个的长度比超过某一界限，则认为这是一个“畸形划分”，对较短的子序列继续使用“快速排序”，而把较长的子序列平分为两个子序列分别排序，然后再进行一次合并。两个有序序列的合并是可以实现为线性的时间复杂度的，因此可以在每次都是畸形划分时仍然获得0(N*LogN)的时间复杂度。其中Partition就是众所周知的用于“快速排序的划分子程序，Merge(Data,First,Size)把Data中0,First)和First,Size)两个有序列合并为一个有序序列并存放在Data中。Partition划分的位置M处的值就是划分的枢

5、值，也就是说序列可以分成O,M-1、M,M和M+l,Size-l三部分。如果Partition的实现不能保证这一点，则MoreData应为DataM，而MoreSize也应为Size-M。(五、模块划分1、voidCreate(SqList*L)，建立排序表。2、voidTraverse(SqListL)，遍历排序表(输出哨兵)。3、voidswap(int*a,int*b)，用于交换两个数。4、intPartition(SqList*L,intlow,inthigh)，将一个序列划分成两个子序列，后一子序列所有值都不大于前一子序列任意值。返回子序列分割处索引。5、voidQSort1(SqL

6、ist*L,intlow,inthigh)，调用快排函数进行排序。6、intQSort2(SqList*L,intlow,inthigh)，调用双倍快排函数进行排序。7、voidMerge(RedTypeSR,RedTypeTR,inti,intm,intn),两个有序序列合并为一个有序列序。8、voidMSort(RedTypeSR,RedTypeTR1,ints,intt),归并排序。9、intqsort1(SqList*L,intlow,inthigh)，快速排序。10、voidmenu，输出时清晰。11、intmain(),主函数。六、数据结构ey)；L-length=n;/*遍历排序

7、表(输出哨兵)*/voidTraverse(SqListL)inti;for(i=1;ir0=L-rlow;pivotkey=L-rlow.key；while(lowhigh)while(lowrhigh.key=pivotkey)high-；L-rlow=L-rhigh；while(lowrlow.keyrhigh=L-rlow；L-rlow=L-r0；Traverse(*L)；/*每一趟的输出*/(printf(n)；returnlow；/*快速排序函数*/voidQSort1(SqList*L,intlow,inthigh)intpivotloc；/*设置枢轴*/if(lowhigh|l

8、ow=high)return1；if(L-rlow.keyL-rhigh.key)/*确保区间内第一个元素的值不大于区间内最后一个元素的值*/swap(&L-rlow.key,&L-rhigh.key)；Ls=low；Hs=high；for(i=low+1；iri.keyL-rhigh.key)Hs-；swap(&L-ri.key,&L-rHs.key)；/*交换两数*/i-；/*下一个比较位置不变*/n-；/*循环次数减1*/swap(&L-rLs.key,&L-rlow.key)；/*交换两数*/swap(&L-rHs.key,&L-rhigh.key)；/*交换两数*/Traverse(

9、*L)；/*每一趟的输出*/printf(n)；QSort2(L,low,Ls-l)；/*对分解后的第一部分递归快速排序*/QSort2(L,Ls+l,Hs-l)；/*对分解后的第二部分第归快速排序*/QSort2(L,Hs+l,high)；/*对分解后的第三部分第归快速排序*/return0；%/*基于归并的快速排序*/voidMerge(RedTypeSR,RedTypeTR,inti,intm,intn)/*调用归并函*/intj,k；/*定义两数*/for(j=m+1,k=i;i=m&j=n;+k)ifLQ(SRi.key,SRj.key)TRk=SRi+；elseTRk=SRj+；i

10、f(i=m)while(k=n&i=m)TRk+=SRi+；if(j=n)while(k=n&jhigh)return1；k=Partition(L,low,high)；f=k-low；s=high-k；if(fs&s!=0)r=f/s;/*检查其中一个子序列与另一个的长度比是否超过某一界限*/elseif(f!=0)r=s/f;if(rM)mid=(k-l-low)/2+s；/*较长的子序列平分为两个子序列*/QSort1(L,s,mid);/*此时进行快速排序*/|QSort1(L,mid+1,k-1)；MSort(L-r,L-r,mid,k-1)；mid=(f-k-1)/2+k+1；QS

11、ort1(L,k+1,mid)；QSort1(L,mid+1,f)；MSort(L-r,L-r,mid,f)；Traverse(*L)；printf(n)；elseQSort1(L,low,high)；return0；voidmenu()SqListL；intx；【printf(n08课程设计快速排序算法演示n)；printf(nl快速排序算法n);printf(n2双倍快速排序算法n);printf(n3基于归并的快速排序算法n);printf(n4退出演示n);scanf(%d,&x);switch(x)/*调用switch语句进行输出*/case1:printf（n普通快速排序n）;Cr

12、eate(&L);QSort1(&L,1,;break;case2:printf(n双倍快速排序n)；Create(&L);QSort2(&L,1,；break；case3:printf(n基于归并改良的快速排序n)；Create(&L)；qsort1(&L,1,；break；case4:printf(n演示结束n);break；default：printf(n输入有错n);/*主函数*/intmain()menu();system(pause);return1;八、测试情况程序的测试结果如下：1、快速排序结果：2、双倍快速排序运行结果正确经验证，手工运算也对。3、基于归并的快速排序运行正确，

13、结果也正确。九、参考文献1、严蔚敏，数据结构C语言，清华大学出版社。2、谭浩强，c语言程序设计，清华大学出版社。小结经过一年的数据结构学习，对于程序编写的算法及其应用有了一定的了解和掌握，并且能够在一些方面将其运用。这次的课程设计是关于快速排序以及其的一些改进方法的设计。虽然这次的课程设计并没有真正的涉及生活工作中的应用，但是我们通过本次的数据结构的课程设计，了解并知道了一些调试程序的方法，而且学会了一些处理错误的方法。这次的课程设计使得我们对数据结构有了进一步的掌握，并是的我们对VC+的运用更加的熟悉。经历了这次课程设计，不仅仅是对我们的学习提供了帮助，也同时对我们的意志力进行了一次锻炼。没

14、有足够的耐心就会刚编辑一点程序或者出个错误找不到就会不耐烦，从而导致接下来的工作无法进行而被迫暂时搁置，最终使得课程设计的完成效率大大降低。快速排序算法的最好时间O(nlogn)平均时间O(N*LogN)最坏时间O(N2)稳定性一不稳定解释：在所有同数量级O(N*LogN)的排序方法中，快速排序被认为是平均性能最好的一种；但是，若初始记录序列按关键字逆序或基本有逆序时，快速排序则蜕化为冒泡排序，此时，算法的时间复杂度为O(N2)。从时间上看快速排序平均性能优于书上的各种排序吧，但是也存在缺点，上面提到的双倍快速排序和基于归并的快速排序刚好弥补了这一瑕疵，从中找到不足使快排更快。同时经过这次课程

15、设计我们领略到分工合作精神，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，我们每个人都是独立的个体，我们可以独立的查找资料来独立的编辑一个程序，然而我们也可以互相研讨而一起完成一个程序。相对来说独立的个人毕竟一个人的能力是有限的，而通过团队合作我们就可很好的完成一个人完成起来比较困难的工作，这种合作就使得我们的设计相对来说轻松了不少。这次的课程设计不仅仅是使我们有了上面的收获，同时也使我们深刻的认识到自己专业知识的匮乏，以及独立完成程序设计的能力上的不足。通过这次的课程设计，我们认识到了自我的不足还有很多，因此我们在接下来的时间里将会更加努力的去学习和应用，以提高自身的专业技能和实际能力，自强