一种三路划分快速排序的改进算法  被引量:7

Enhanced algorithm for three-route quick sort

在线阅读下载全文

作  者:王善坤[1] 陶祯蓉 

机构地区:[1]大连理工大学城市学院网络信息中心 [2]四川省计算机研究院

出  处:《计算机应用研究》2012年第7期2513-2516,共4页Application Research of Computers

摘  要:快速排序是一种经典的排序算法,它的平均性能非常突出。针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距。改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率。Quick sort is a kind of classic sorting method whose average operation stands out.For the low efficiency problem of the quick sort in some special cases(when dealing with ordered or repetitive data),the algorithm improved the three-way quick sort,so that in special cases,the algorithm still maintainsed good efficiency.Large number of tests show that,in its best scenario,this calculating approach is largely superior to the ordinary ones,and in its worst scenario,it equals to the ordinary ones.The improved three-way quick sort is a general and efficient sorting algorithms,so in certain case,it may provide access to more efficiency.

关 键 词:快速排序 平均时间复杂度 三路划分快速排序 算法 排序性能 

分 类 号:TP301.6[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象