Group-sort algorithm

doi:10.3778/j.issn.1002-8331.2008.33.017

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (33): 53-56.DOI: 10.3778/j.issn.1002-8331.2008.33.017

• 理论研究 • Previous Articles Next Articles

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

分组排序算法

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

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

通讯作者: 汪维清

Abstract

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

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

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

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

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

[1]	YANG Wei, WU Yingying, WANG Ting. Research on Configuration Optimization Problems of Shuttle-Carrier Storage and Retrieval System [J]. Computer Engineering and Applications, 2021, 57(4): 258-265.
[2]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[3]	MA Zhentai, ZHANG Xiaomei, SUN Gongxing. Event Level Parallelization Research of BESIII Experimental Software [J]. Computer Engineering and Applications, 2021, 57(20): 253-262.
[4]	DUAN Yu, CAO Longhan, ZHANG Zhizhong, GAO Shanglei. Research and Implementation of Signaling Analysis Technology in 5G Terminal Simulator [J]. Computer Engineering and Applications, 2020, 56(15): 106-112.
[5]	HUANG Jiacai, SHU Qi, ZHU Xiaochun, ZHOU Lei, LIU Hanzhong, LIN Jian. Robot Vision Recognition and Sorting Strategy Based on Transfer Learning [J]. Computer Engineering and Applications, 2019, 55(8): 232-237.
[6]	REN Hui. Design of Reliable Three-Echelon Supply Chain Network with Transportation Disruption [J]. Computer Engineering and Applications, 2019, 55(6): 265-270.
[7]	DONG Junfeng, WANG Xiang, LIANG Changyong. Improved NSGA-II Algorithm Based on Individual Neighborhood [J]. Computer Engineering and Applications, 2019, 55(5): 166-174.
[8]	YAN Taishan, WEN Yiting, LI Wenbin, YANG Bo. Research on Multi-Objective Optimization Method of Combined-Taxi [J]. Computer Engineering and Applications, 2019, 55(20): 222-226.
[9]	JU Luyan1, YANG Jianjun2, ZHANG Jianbing1, GUO Longlong1, LI Suobin1. Improved NSGA for Multi-Objective Flexible Job-Shop Scheduling Problem [J]. Computer Engineering and Applications, 2019, 55(13): 260-265.
[10]	LIAN Tianyou, YU Qin. Human Identity Recognition Using Improved KNN Method [J]. Computer Engineering and Applications, 2019, 55(11): 142-146.
[11]	JIANG Liubing1，2, XIAO Zhitao1, CHE Li1，2, ZHAO Jikui1. Fast phase unwrapping method based on quality guide for InSAR [J]. Computer Engineering and Applications, 2018, 54(3): 222-226.
[12]	SHEN Huanxue1，2, ZHENG Kai1，2, LIU Yao1，2, WANG Su1，2, LIU Yan1，2, ZHAO Ruixiang1，2, ZHOU Qianhao3. Parallel NSGA-II on Sunway many-core processor [J]. Computer Engineering and Applications, 2018, 54(17): 35-40.
[13]	TANG Shuzhu, YOU Peng, YAN Dawei, YONG Shaowei. Design optimization of near space communication network based on improved-NSGA2 [J]. Computer Engineering and Applications, 2018, 54(14): 203-210.
[14]	XU Qingzheng1, YANG Heng1, WANG Na1, WU Guohua2, JIANG Qiaoyong3. Recent advances in multifactorial evolutionary algorithm [J]. Computer Engineering and Applications, 2018, 54(11): 15-20.
[15]	BAI Donghui, ZHANG Tao, WEI Xinyu. Attributes-sorting algorithm based on attribute degree [J]. Computer Engineering and Applications, 2017, 53(5): 64-68.

Group-sort algorithm

分组排序算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics