计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (33): 53-56.DOI: 10.3778/j.issn.1002-8331.2008.33.017

• 理论研究 • 上一篇    下一篇

分组排序算法

汪维清1,罗先文1,汪维华2   

  1. 1.西南大学荣昌校区 信息管理系,重庆 402460
    2.重庆文理学院 数学与计算机科学系,重庆 402160
  • 收稿日期:2007-12-17 修回日期:2008-03-18 出版日期:2008-11-21 发布日期:2008-11-21
  • 通讯作者: 汪维清

Group-sort algorithm

WANG Wei-qing1,LUO Xian-wen1,WANG Wei-hua2   

  1. 1.Department of Information Management,Southwest University Rongchang Campus,Chongqing 402460,China
    2.Department of Mathematics and Computer Science,Chongqing University of Arts and Sciences,Chongqing 402160,China
  • Received:2007-12-17 Revised:2008-03-18 Online:2008-11-21 Published:2008-11-21
  • Contact: WANG Wei-qing

摘要: 提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θmn);最好情况和平均情况下的时间复杂度均是θnlog(n/mk));在最坏情况下的空间复杂度是O(mn-m2m);最好情况和平均情况下的空间复杂度均是O(mklog(n/mk));并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。

关键词: 排序, 分组排序, 快速排序, 归并排序, 基数排序

Abstract: Propose the grouping sort algorithm,and labor it’s principle and complexity of time and space.Obtain that it’s time complexity is θmn) in the worst situation,and it’s time complexity of is θnlog(n/mk)) in the best or in average situation.Obtain that it’s complexity of space is O(mn-m2m) in the worst situation,and it’s complexity of space is O(mklog(n/mk)) in the best or in average situation.Take the experiment with the multi-group random data.The result shows the article’s correctness.This result is very helpful for designing efficient algorithms for huge data processing.

Key words: sort, group sort, quick sort, merge sort, radix sort