作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2009, Vol. 35 ›› Issue (17): 84-85. doi: 10.3969/j.issn.1000-3428.2009.17.028

• 软件技术与数据库 • 上一篇    下一篇

地址映射外分类算法的研究

万红运1,张志立1,李钟瑞2   

  1. (1. 许昌学院网络中心,许昌 461000;2. 河南省国税局信息中心,郑州 450003)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-09-05 发布日期:2009-09-05

Research on Address-mapping External Sorting Algorithm

WAN Hong-yun1, ZHANG Zhi-li1, LI Zhong-rui2   

  1. (1. Centre of Network, Xuchang University, Xuchang 461000; 2. Information Center, State Administration of Taxation, Henan Province, Zhengzhou 450003)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-09-05 Published:2009-09-05

摘要: 提出一种新的外分类算法,该算法无须预先产生初始归并段,可以快速获得预定分类结果。在特定的数据和硬件配置下,其性能优于二路平衡归并法和二路多步归并法。分析该算法的存储空间开销,给出算法正确性证明,在PC/586上用C++语言对其进行实现。

关键词: 地址映射外分类, 时间复杂度, 存储开销

Abstract: This paper proposes a new external sorting algorithm. The algorithm need not to produce original merged segment in advance and can immediately get the anticipant sorting result. Under the particular data and hardware configure, the performance of this algorithm exceeds two-ways balance mergesort and two-ways many steps mergesort. It analyzes the memory space spending of this algorithm, proves its correctness and realizes it in C++ on PC/586.

Key words: address-mapping external sorting, time complexity, memory overhead

中图分类号: