一种三路划分快速排序的改进算法

• 作者: 王善坤 陶祯蓉
• 来源期刊: 计算机应用研究
• 关键词: 快速排序 平均时间复杂度 三路划分快速排序 算法 排序性能
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2513-2516
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2012.07.029

摘要

快速排序是一种经典的排序算法,它的平均性能非常突出.针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率.通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距.改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王善坤	大连理工大学城市学院网络信息中心	15	44	4.0	6.0
2	陶祯蓉		1	7	1.0	1.0