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

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

Enhanced algorithm for three-route quick sort

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 caseswhen 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.