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

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (29): 13-15.

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

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

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

出版日期:2012-10-11 发布日期:2012-10-22

Non-recursive programming algorithm for quickselect

QIU Yonghong1，2, ZENG Yongnian2, ZOU Bin2

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

摘要/Abstract

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

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

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

邱永红1，2，曾永年2，邹滨2. 快速选择的循环迭代实现算法[J]. 计算机工程与应用, 2012, 48(29): 13-15.

QIU Yonghong1，2, ZENG Yongnian2, ZOU Bin2. Non-recursive programming algorithm for quickselect[J]. Computer Engineering and Applications, 2012, 48(29): 13-15.

[1]	张岐山，陈露露. 基于均衡接近度灰关联的Slope One算法[J]. 计算机工程与应用, 2021, 57(9): 96-102.
[2]	王永贵，李倩玉. 基于KNN-GBDT的混合协同过滤推荐算法[J]. 计算机工程与应用, 2021, 57(9): 103-108.
[3]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[4]	张朕通，单玉刚，袁杰. 联合多尺度和注意力机制的遥感影像检测[J]. 计算机工程与应用, 2021, 57(9): 212-216.
[5]	兰红，黄敏. 融合KNN优化的密度峰值和FCM聚类算法[J]. 计算机工程与应用, 2021, 57(9): 81-88.
[6]	闫晓燊，高强，朱思萌，奚学程，赵万生. 亮度不均匀低质量图像中压印字符分割方法[J]. 计算机工程与应用, 2021, 57(8): 185-191.
[7]	高一锴，彭力，徐龙壮. 改进AFSA算法优化TWSVM的火焰识别方法[J]. 计算机工程与应用, 2021, 57(8): 204-213.
[8]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[9]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[10]	高铖铖，陈锡程，张瑞，宋秋月，易东，伍亚舟. 三种新型智能算法在疫情预警模型中的应用——基于百度搜索指数的COVID-19疫情预警[J]. 计算机工程与应用, 2021, 57(8): 256-263.
[11]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[12]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[13]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[14]	沈新烽，姜平，周根荣. 改进SSD算法在零部件检测中的应用研究[J]. 计算机工程与应用, 2021, 57(7): 257-262.
[15]	雍玖，王阳萍，党建武，雷晓妹. 改进TLD与ORB的AR系统长时跟踪注册方法[J]. 计算机工程与应用, 2021, 57(7): 178-184.