稳定快速排序算法研究-论文.pdf

《稳定快速排序算法研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3I卷第7期计算机应用与软件Vo1．31No．72014年7月ComputerApplicationsandSoftwareJu1．2014稳定快速排序算法研究邵顺增(常州工程职业技术学院计算机技术系江苏常州213000)摘要快速排序算法与其他算法相比是相当有效的排序算法，但此算法并不完善，它是不稳定的。为此，对快速排序算法进行改进，在每次对数据分割时，对需要移动的数据先分别顺序拷出并保存，分割结束前再按要求分别顺序拷入，使得新排序算法是稳定算法。理论分析和实验数据表明，在任何情况下，稳定快速排序算

2、法都是稳定的，并且其他性能不比快速排序算法和3-并算法差。关键词排序算法算法稳定性算法时间复杂度算法空间复杂度稳定快速排序中图分类号TP301．6文献标识码ADOI：10．3969／j．issn．1000—386x．2014．07．067STUDYoNSTABLEANDQUICKSORTALGORITHMShaoShunzeng(DepartmentofComputer，ChangzhouInstituteofEngineeringTecknology，Changzhou213000，Jiangsu，

3、China)AbstractQuicksortalgorithmisamoreeficientonethanotheralgorithms，butitisimperfectforitsinstability．Therefore，weimprovethequicksortalgorithm．Ateachtimewhenthedataissegmented，thenewsortalgorithmcopiesoutandsavesthedatatobeshiftedinorderseparately，and

4、thencopiesintheminorderaccordingtotheneedrespectivelybeforethesegmentationisfinished，thatmakesthenewsortalgorithmbethestableone．Itisindicatedthatthestableandquicksortalgorithmisstableinanycasebythetheoreticalanalysisandexperimentaldata，anditsperformance

5、isasgoodasthequicksortalgorithmandthemergealgorithm．KeywordsSortalgorithmAlgorithmstabilityAlgorithmtimecomplexityAlgorithmspacecomplexityStableandquicksort分割成独立的二部分，通过直接交换方式使其中一部分记录的0引言关键字均比另一部分记录的关键字小，然后再分别对这两部分的记录继续进行排序，以达到整个序列有序。在把待排序的数快速排序算法在所有的排序算

6、法中是比较优秀的算法，也据分割成两部分时，需要把前后的数据直接进行交换，这样的交是推荐的常用算法，但它不完善，即它是不稳定的排序算法。所换可能导致数据前后颠倒，所以经典快速排序是不稳定的。要谓排序算法的稳定性是指在待排序的记录序列中，如果存在多想使排序稳定，需要改掉这种直接交换前后数据的办法，采用其个具有相同的关键字的记录，若经过排序，这些记录的相对次序他方法处理。稳定快速排序算法就是这样一种改进算法。保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的稳定快速排序的设计思想如下：序列中

7、，ri仍在rj之前，则称这种排序算法是稳定的，否则称为(1)通过一趟排序将要排序的数据划分成独立的两部分。不稳定的。在实际处理数据的过程中，有时对排序的稳定性要(2)每部分各自再分成两小块，使一小块所有数据都按原求很高，例如在处理类似有奖问卷问题时，常根据问卷的成绩给顺序排列且比另一小块按原顺序排列的所有数据都小(或大)。部分人一定的奖品，但有时相同成绩的人很多，不可能都给奖(3)把四块中两个小(或大)块按原顺序连接起来，放在所品，一般采取的是在成绩相同的情况下，提交答案早的得奖品，有数据的前部，把另

8、外两个不小于(或不大于)块也按原顺序连提交答卷晚的不得奖品，这时就需要对成绩排序的算法是稳定接起来，放在所有数据的后部。的。(4)然后再按此方法对形成的两部分数据分别进行稳定快近年来，不少学者提出各种改进的快速排序算法，如三路基速排序，直到所有数据都是有序的。整个排序过程可以递归进数快排、高效快速排序算法和超速快排等，都是增强了行。快速排序时间性能，但对排序算法的稳定性基本上没有涉及。本文针对这一情况提出了一种稳定快速排序算法。1．2算法设计思路本文以递