快速排序算法的分析与研究_王春红.pdf

2013年10月15日 现代电子技术 Oct.2013 第36卷第20期 ModernElectronicsTechnique Vol.36No.20 54 54 快速排序算法的分析与研究 王春红，王文霞 （运城学院 计算机科学与技术系，山西 运城 044000） 摘 要：快速排序是排序算法中性能较好的一种，但存在对数据基本有序的情形下的性能瓶颈问题。为了保证快速排 序在任何情况下的高效性，在对快速排序算法的时间效率进行充分的分析的基础上，指出支点元素的选取是影响快速排序 算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法，很好地避免了最坏情况的发生。通过实验验证了改 进算法的正确性和高效性。 关键词：快速排序算法；支点元素；时间效率；随机化快速排序 中图分类号：TN911-34；TP301.6 文献标识码：A 文章编号：1004-373X（2013）20-0054-03 Analysisandresearchofquicksortingalgorithm WANGChun-hong，WANGWen-xia （DepartmentofComputerScienceandtechnology，YunchengUniversity，Yuncheng 044000，China） Abstract：Quicksortisoneofsortingalgorithmswithbetterperformance，butithaschokepointwhensorteddataisinba⁃ sicsortorder.Inordertoensurehighefficiencyofquicksortinanycase，basedonafullanalysisofthetimeefficiencyof quicksortingalgorithm，itispointedoutthatthemainfactorwhichaffectstheefficiencyofquicksortingalgorithmsistheselec⁃ tionofpointingelement.Therefore，aquicksortingmethodofselectingthepointingelementrandomlyisproposed，whichmakes theoccurrenceoftheworstcasewellavoided.Thecorrectnessandefficiencyoftheimprovedalgorithmwereverifiedbyexperi⁃ ments. Keywords：quicksortingalgorithm；pointingelement；timeefficiency；randomizedquicksort 快速排序（Quicksort）是一种基于比较、划分的排序 为n的单支二叉树。因此，保证快速排序在任何情况下 方法。它基本思想是：在待排元素集S中选择一个元素 高效性，近年来被国内学者从各种不同的角度进行了 [1-6] x作为支点（Pivot），通过一趟排序将要排序的数据分割 改进与优化 。 成独立的两个子序列S 和S ，其中左部分S 的所有元素 L R L 都小于或等于支点元素，而右部分S 的所有元素都大于 R