快速排序算法与递归

《快速排序算法与递归》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安阳工学院学报38JournalofAnyangInstituteofTechnology2008年改进的快速排序算法与递归董萍（三门峡职业技术学院机电工程系，河南三门峡472000）摘要：快速排序算法结构简单,平均性能较佳,被广泛地应用于理论和算法设计。介绍了快速排序，提出了一种改进的快速排序算法，并给出了非递归的快速排序算法，进行了相应的算法复杂度分析。关键词：排序；快速排序；算法；双倍快速排序算法；递归中图分类号：TP301.6文献标识码：A文章编号：1673-2928（2008）06-0038-

2、04当今计算机应用领域非常之广，但由于计算机硬件的速度和存储空间的有限性，如何提高计算机速度并节省存储空间一直成为软件编制人员努力的方向。在众多措施中，排序操作成为程序设计人员考虑的因素之一。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占用量，进而影响整个软件的性能。排序(Sorting)，就是将数据元素的一个任意序列，重新排列成一个按关键字有序的序列，它在计算机中的使用频率很高，与许多排序算法比较，快速排序处于优势地位。1快速排序的基本思想、步骤与时间复杂度分析[1]快速排序又称为划分排

3、序，它是目前所有排序方法中速度最快的一种，是对气泡排序的一种改进方法。在快速排序中，记录的比较和交换是从两端向中间进行的，排序码较大的记录一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元。1.1基本思想快速排序算法结构简单，平均性能较佳。其基本思想是：在待排序的n个数据中任取一个数据(通常取第一个数据)，以该数据为标准(或称为枢轴)，将所有数据分成两组，一组中各数据都小于该数据，另一组中各数据都大于该数据，并把该数据排在这两组的中间(这也是该数据的最终排序位置)。然后对这两组分别重复上

4、述方法，直到所有的数据都排到相应的位置为止。[6]1.2算法步骤一趟快速排序采用从两头向中间夹入比较，同时交换与基准键值逆序的记录。具体做法是：设待定排序部分的记录存于rt,rt+1,...rw中，设置两个指针i和j，初始时i=t,j=w，基准记录Rd=rt,Kd=rt.key。首先从j所指的位置开始向前搜索，直至找到一个键值小于Kd的记录，并把它和Rd交换，然后从j所指位置向后搜索，直至找到一个键值大于Kd的记录，再把它和Rd交换。重复上述过程，直至i=j为止。对划分的两部分再分别进行快速排序，如此重

5、复，直至每部分只含一个记录，显然有序，快速排序完成。算法实现时，为了减少交换记录的次数，开始时把rt存入x，一趟排序过程中只做rj或ri的单向交换，直到一趟排序结束后不再把x存于ri中，快速排序的递归算法如下：voidkspxd(JDr,intt,intw){inti,j,k;JDx;if(t>=w)return;i=t;j=w;x=ri;do{while((rj.key>=x.key)&&(j>i))j--;if(ii)

6、)i++;if(i

7、情况并没有多大可能发生。其次，当每个轴值都将数组分成相等的两部分时，出现了快速排序的最佳情况。快速排序一直将数组分割下去，直到最后，在最佳情况下需要分割log2n次，最上层原始待排序数组中有n个记录，第二层分割的数组是2个长度各为n/2的子数组，第三层分割的子数组是4个长度为n/4的子数组……依次类推。因此，在每一层中，所有分割的步骤之和是n，于是整个算法的时间代价为O(nlog2n)。最后，快速排序的平均情况介于最好与最差两种情况之间。平均情况应考虑到所有可能的输入，对所耗费的时间求和，然后除以输入的

8、总情况数。轴值将数组分成长度为0和n-1，1和n-2……依次类推，其时间复杂度为O(nlog2n)。2改进的快速排序算法即双倍快速排序的算法[4]2.1算法的基本思想快速排序的基本思想是基于分支策略的思想。即对于输入的子序列Llow…High，如果规模足够小则直接进行排序，否则分三步处理：1）分解(Divide)：设输入的序列Llow…High，确定支点元素Llow和LHigh，并使LLow.key<=Ll-High.key，然后分解(Di