从n个元素中选取前k(k〈〈n)个元素的排序方法

J4 ›› 2014, Vol. 36 ›› Issue (A2): 273-275.

从n个元素中选取前k(k〈〈n)个元素的排序方法

冯广慧，陈守孔

(吉林大学珠海学院，广东珠海 519041

收稿日期:2014-06-13 修回日期:2014-08-20 出版日期:2014-12-25 发布日期:2014-12-25

Sorting methods for selecting the top
k(k〈〈n)elements in a set of n elements

FENG Guanghui,CHEN Shoukong

（Zhuhai College,Jilin University,Zhuhai 519041,China）

Received:2014-06-13 Revised:2014-08-20 Online:2014-12-25 Published:2014-12-25

摘要/Abstract

摘要：

首先叙述了常见的几种排序方法，分析了各自的优缺点，指出了每趟排序都至少有一个元素能确定自己最终位置的排序方法。重点分析了堆排序与快速排序，提出在大量元素中找出前几个元素时，堆排序和快速排序方法相比，使用快速排序解决此类问题效率更佳。

关键词: 排序, 堆排序, 快速排序

Abstract:

In this paper,we firstly describe several common sorting methods,analyze their merits and shortcomings,and then propose some sorting methods which can determine the final position of at least one element during each trip of sorting.We discuss heapsort algorithm and quicksort algorithm in particular.Through the comparison of these methods,it shows that the quicksort is often better than heapsort when finding out the first several elements among a large number of elements.

Key words: sort；heapsort；quicksort

冯广慧，陈守孔. 从n个元素中选取前k(k〈〈n)个元素的排序方法[J]. J4, 2014, 36(A2): 273-275.

FENG Guanghui,CHEN Shoukong. Sorting methods for selecting the top
k(k〈〈n)elements in a set of n elements [J]. J4, 2014, 36(A2): 273-275.

［1］	Chen Shoukong,Meng Jiana. Algorithms and data structures(C language version)［J］.Beijing：China Machine Press，2008.(in Chinese)
［2］	Yan Weimin,Wu Weimin.Data structures(C language version)［J］.Beijing：Tsinghua University Press，2009.(in Chinese)
［3］	Zhang Ming，Wang Tengjiao，Zhao Haiyan.Data structures and algorithms［J］.Beijing：Higher Education Press，2008.(in Chinese)
	附中文参考文献：
［1］	陈守孔,孟佳娜,武秀川.算法与数据结构（C语言版）［J］.北京：机械工业出版社,2008.
［2］	严蔚敏,吴伟民.数据结构（C语言版）［J］.北京：清华大学出版社,2009.
［3］	张铭,王腾蛟.数据结构与算法［J］.北京：高等教育出版社,2008.

[1]	卓灵1，聂静1，肖静薇1，袁杨2，胡新1，陈柯1. 电力无线通信异构多网共存环境中的网络选择算法[J]. J4, 20160101, 38(01): 78-83.
[2]	曹军航, 黄瑞章, 白瑞娜, 赵建辉, . DCsR：一种面向中文文本的集成式纠错框架[J]. 计算机工程与科学, 2023, 45(02): 370-380.
[3]	何海江. 融合语句复杂度的软件错误定位轻量级方法[J]. 计算机工程与科学, 2022, 44(12): 2187-2195.
[4]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[5]	陈华烨, 汪海涛, 姜瑛, 陈星. 基于排序学习的构件检索方法的研究[J]. 计算机工程与科学, 2021, 43(06): 1006-101.
[6]	刘亚波, 吴秋轩. 基于长短时记忆网络的电商大数据同一性标定[J]. 计算机工程与科学, 2021, 43(03): 407-415.
[7]	杨柳, 金培权. 面向DRAM和NVM异构混合内存架构的排序连接算法优化[J]. 计算机工程与科学, 2021, 43(02): 191-198.
[8]	肖满, 丁璐, 张怡. 带两个服务等级的3台机半在线算法[J]. 计算机工程与科学, 2020, 42(12): 2252-2258.
[9]	官蕊, 丁家满, 贾连印, 游进国, 姜瑛, . 基于强化学习的多样性文档排序算法[J]. 计算机工程与科学, 2020, 42(09): 1697-1703.
[10]	朱国晖，张茵，刘秀霞，孙天骜. 基于两次优先级排序的虚拟网络映射算法[J]. 计算机工程与科学, 2020, 42(05): 795-802.
[11]	李茜, 周华健, 杨浩运, 殷海兵. 一种基于listwise的在线学习书目排序检索算法[J]. 计算机工程与科学, 2020, 42(04): 749-754.
[12]	王鑫, 陈建凯, 翟俊海, . 区间值属性单调决策树算法的扩展[J]. 计算机工程与科学, 2020, 42(03): 557-563.
[13]	张卫祥，齐玉华，魏波，张敏，窦朝晖. 基于蚁群算法的测试用例优先排序[J]. 计算机工程与科学, 2020, 42(02): 241-249.
[14]	刘少楠，李玲，苑迎，蒋国佳，王聪，吕艳霞. 基于节点连通性排序的虚拟网络映射算法[J]. 计算机工程与科学, 2019, 41(12): 2101-2109.
[15]	孟昱煜，陈绍立，刘兴长. 面向排序学习的层次聚类特征选择算法[J]. 计算机工程与科学, 2019, 41(12): 2211-2216.