分组排序算法

doi:10.3778/j.issn.1002-8331.2008.33.017

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

分组排序算法

汪维清¹,罗先文¹,汪维华²

1.西南大学荣昌校区信息管理系，重庆 402460
2.重庆文理学院数学与计算机科学系，重庆 402160

收稿日期:2007-12-17 修回日期:2008-03-18 出版日期:2008-11-21 发布日期:2008-11-21
通讯作者: 汪维清

Group-sort algorithm

WANG Wei-qing¹,LUO Xian-wen¹,WANG Wei-hua²

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

摘要/Abstract

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

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

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/m^k）） in the best or in average situation.Obtain that it’s complexity of space is O（mn-m²＋m） in the worst situation，and it’s complexity of space is O（m^klog（n/m^k）） 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

汪维清¹,罗先文¹,汪维华². 分组排序算法[J]. 计算机工程与应用, 2008, 44(33): 53-56.

WANG Wei-qing¹,LUO Xian-wen¹,WANG Wei-hua². Group-sort algorithm[J]. Computer Engineering and Applications, 2008, 44(33): 53-56.

[1]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[2]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[3]	马震太，张晓梅，孙功星. BESIII实验软件事例级并行化研究[J]. 计算机工程与应用, 2021, 57(20): 253-262.
[4]	郭佳丽，王秋萍，王晓峰. 融合学习策略和邻域搜索的飞蛾火焰算法[J]. 计算机工程与应用, 2021, 57(12): 170-179.
[5]	肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.
[6]	姜金川，王冲. 基于学习自动机和用户兴趣的PageRank算法研究[J]. 计算机工程与应用, 2020, 56(3): 80-85.
[7]	张松慧，熊汉江. 融合神经网络和泊松分解的兴趣点推荐算法[J]. 计算机工程与应用, 2020, 56(21): 176-186.
[8]	段浴，曹龙汉，张治中，高尚蕾. 5G终端模拟器中信令分析技术的研究与实现[J]. 计算机工程与应用, 2020, 56(15): 106-112.
[9]	丁棋梁，石泽智，李建华. 基于分组贝叶斯排序的药物-靶标关系预测[J]. 计算机工程与应用, 2020, 56(15): 185-190.
[10]	郭皓月，樊重俊. 考虑决策者权重和核心评级的模糊排序方法[J]. 计算机工程与应用, 2020, 56(10): 163-170.
[11]	任慧. 考虑运输中断的可靠三级供应链网络设计[J]. 计算机工程与应用, 2019, 55(6): 265-270.
[12]	董骏峰，王祥，梁昌勇. 基于个体邻域的改进NSGA-II算法[J]. 计算机工程与应用, 2019, 55(5): 166-174.
[13]	田泽金，黄锐露，吕跃进. 区间粗糙数互补判断矩阵的两种一致性[J]. 计算机工程与应用, 2019, 55(24): 235-240.
[14]	严太山，文怡婷，李文彬，杨勃. 出租车合乘多目标优化方法研究[J]. 计算机工程与应用, 2019, 55(20): 222-226.
[15]	连天友，余勤. 改进KNN算法对人体身份的识别[J]. 计算机工程与应用, 2019, 55(11): 142-146.

分组排序算法

Group-sort algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics