Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (29): 13-15.

Previous Articles     Next Articles

Non-recursive programming algorithm for quickselect

QIU Yonghong1,2, ZENG Yongnian2, ZOU Bin2   

  1. 1.Department of Geographic Information Engineering, Hunan Normal University, Changsha 410081, China
    2.School of Geoscience and Info-Physics, Central South University, Changsha 410083, China
  • Online:2012-10-11 Published:2012-10-22

快速选择的循环迭代实现算法

邱永红1,2,曾永年2,邹  滨2   

  1. 1.湖南师范大学 地理信息工程系,长沙 410081
    2.中南大学 地球科学与信息物理学院,长沙 410083

Abstract: After analyzing the basic idea of the quickselect algorithm, a non-recursive programming algorithm, cyclically iterative algorithm, for quick selection is presented. The performance of the algorithm is validated by both the traditional robust recursive algorithm and “nth_element” which is the VC++ standard library function. The result shows that the proposed cyclically iterative algorithm performs relatively better than the recursive algorithm in terms of time efficiency and reliability, while it is also more efficient compared to the “nth_element”.

Key words: quickselect, non-recursive, cyclical iteration, algorithm

摘要: 在分析快速选择算法基本思想的基础上,给出了用于快速选择的非递归实现算法——循环迭代算法,并通过实验,与递归算法以及VC++标准库函数nth_element进行了比较,结果表明,该算法比传统的递归算法具有较高的效率和可靠性;与标准库函数nth_element比较,在时间效率方面具有明显优势。

关键词: 快速选择, 非递归, 循环迭代, 算法