快速排序一个低效问题的完善处理

为了改善含有大量重复数据时快速排序效率低下的问题,提出了简便有效的拟3路划分算法,即每次划分时并不单独分离出等值元素以形成等值区,而是划分后及时排除基准处自然形成的等值区,从而避免了3路划分的困难,仅需对原算法做极少的修改,数值结果表明效果优于其它同类算法。

Perfect Treatment to a Low-efficient Problem of Quicksort

To improve the low efficiency of quicksort when sorting data with large number of equals, a simple and effective quasi 3-way partition algorithm is proposed： in partitioning the equals are not needed to draw out specially to form complete equals area, but the equals area naturally formed around the pivot is excluded immediately after partition. In this way, the complexity of 3-way partition is avoided , and very little modification is required for the general partition algorithm. Numerical results show the superiority to other similar algorithms in efficiency.