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