快速排序算法.doc

快速排序算法发布时间:2011-01-0420:132013中国大数据大会赠票申请文思海辉第一届在线编程大赛消灭0回答,赢下载分订阅CSDN社区周刊,及时了解社区精华内容办公大师系列经典丛书诚聘译者快速排序算法分类:(后续)2011-01-0420:1374949人阅读评论(140)收藏举报cexchangenulltable算法快速排序算法作者July二零一一年一月四日------------------------------------------写之前,先说点题外话。每写一篇文章,我都会遵循以下几点原则:一、保持版面的尽量清晰,力保排版良好。二、力争所写的东西,清晰易懂,图文并茂三、尽最大可能确保所写的东西精准,有实用价值。因为,我觉得,你既然要把你的文章,公布出来,那么你就一定要为你的读者负责。不然,就不要发表出来。一切,为读者服务。ok,闲不多说。接下来,咱们立刻进入本文章的主题,排序算法。众所周知,快速排序算法是排序算法中的重头戏。因此,本系列,本文就从快速排序开始。------------------------------------------------------一、快速排序算法的基本特性时间复杂度:O(n*lgn)最坏:O(n^2)空间复杂度:O(n*lgn)不稳定。快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)。通常是用于排序的最佳选择。因为,基于比较的排序,最快也只能达到O(nlgn)。二、快速排序算法的描述算法导论,第7章快速排序时基于分治模式处理的,对一个典型子数组A[p...r]排序的分治过程为三个步骤::A[p..r]被划分为俩个(可能空)的子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]<=A[q]<=A[q+1..r]:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序。。三、快速排序算法版本一:QUICKSORT(A,p,r)1ifp<r2thenq?PARTITION(A,p,r)//关键3QUICKSORT(A,p,q-1)4QUICKSORT(A,q+1,r)数组划分快速排序算法的关键是PARTITION过程,它对A[p..r]进行就地重排:PARTITION(A,p,r)1x?A[r]2i?p-13forj?ptor-14doifA[j]?x5theni?i+16exchangeA[i]<->A[j]7exchangeA[i+1]<->A[r]8returni+1ok,咱们来举一个具体而完整的例子。来对以下数组,进行快速排序,28713564(主元)一、ip/j28713564(主元)j指的2<=4,于是i++,i也指到2,2和2互换,原数组不变。j后移,直到指向1..二、j(指向1)<=4,于是i++i指向了8,所以8与1交换。数组变成了:ij21783564三、j后移,指向了3,3<=4,于是i++i这是指向了7,于是7与3交换。数组变成了:ij21387564四、j继续后移,发现没有再比4小的数,所以,执行到了最后一步,即上述PARTITION(A,p,r)代码部分的第7行。因此,i后移一个单位,指向了8ij21387564A[i+1]<->A[r],即8与4交换,所以,数组最终变成了如下形式,21347568ok,快速排序第一趟完成。4把整个数组分成了俩部分,213,7568,再递归对这俩部分分别快速排序。ip/j213(主元)2与2互换,不变,然后又是1与1互换,还是不变,最后,3与3互换,不变,最终,3把213,分成了俩部分,21,,递归排序,(主元),7、5、6、都比8小,所以第一趟,还是7568,不过,此刻8把7568,分成了756,和8.[756->576->567]再对756,递归排序,最终结果变成5678。ok,所有过程,全部分析完成。最后,看下我画的图:快速排序算法版本二不过,这个版本不再选取(如上第一版本的)数组的最后一个元素为主元,而是选择,数组中的第一个元素为主元。/**************************************************//*函数功能:快速排序算法*//*函数参数:结构类型table的指针变量tab*//*整型变量left和right左右边界的下标*//*函数返回值:空*//*文件名::quicksort()*//**************************************************/voidquicksort(table*tab,intleft,intright