基于Java的按位拆分快速排序并行算法

doi:10.3724/SP.J.1087.2012.02455

计算机应用 ›› 2012, Vol. 32 ›› Issue (09): 2455-2457.DOI: 10.3724/SP.J.1087.2012.02455

基于Java的按位拆分快速排序并行算法

庹清1,2*,宋耀虎2

1.吉首大学城乡资源与规划学院,湖南张家界 427000;
2.吉首大学数学与统计学院,湖南吉首 416000

收稿日期:2012-03-13 修回日期:2012-05-15 发布日期:2012-09-01 出版日期:2012-09-01
通讯作者: 庹清
作者简介:庹清(1964-),男,湖南张家界人,教授,博士,主要研究方向:并行计算、算法优化; 宋耀虎(1986-),男,广西都安人,主要研究方向:算法设计与分析。
基金资助:
国家自然科学基金资助项目(11101186);湖南省教育厅科学研究基金资助项目(08A057);吉首大学博士基金资助项目(201101)

Bit-split parallel algorithm for quick sorting based on Java

TUO Qing^1,2*,SONG Yao-hu²

1.College of Urban and Rural Resources and Planning,Jishou University,Zhangjiajie Hunan 427000,China;
2.College of Mathematics and Statistics,Jishou University,Jishou Hunan 416000,China

Received:2012-03-13 Revised:2012-05-15 Online:2012-09-01 Published:2012-09-01
Contact: Qing TUO

摘要/Abstract

摘要： 针对大数据量排序算法优化问题,提出一种基于Java的按位拆分的排序新算法。该排序算法按照位拆分数据,并结合Java的多线程对拆分的数据进行并行处理。数据实验结果表明,对于大数据量排序,该算法性能明显优于快速排序算法,而且算法具有很好的并行效率。

关键词: 按位拆分, 快速排序, 并行算法, 数据实验, 算法分析

Abstract: This paper presented a new sorting algorithm based on bit-split quick sort that aimed to explore the algorithm which had excellent performance for large data. The algorithm split data in bit, and parallel processed the split data in combination with Java's concurrent mechanism. The data experiments show that the new sorting algorithm is significantly better than quick sort for large data sorting and owns very good parallel efficiency.

Key words: bit-split, quick sort, parallel algorithm, data experiment, algorithm analysis

中图分类号:

TP301.6

庹清宋耀虎. 基于Java的按位拆分快速排序并行算法[J]. 计算机应用, 2012, 32(09): 2455-2457.

TUO Qing SONG Yao-hu. Bit-split parallel algorithm for quick sorting based on Java[J]. Journal of Computer Applications, 2012, 32(09): 2455-2457.

参考文献

[1]WANG YINGXU.A new sort algorithm:self-indexed sort [J].ACM SIGPLAN Notices,1996,31(3):28-36.
[2]朱红,陈清华,刘国发.一种Byte-快速排序算法研究[J].计算机工程,2002,28(12):39-57.
[3]黄兴.比特位拆分索引排序算法研究[D].北京:清华大学,2007.
[4]庹清,向贵成,宋耀虎.改进的按位拆分快速排序算法[J].计算应用,2011,31(S1):183-184.
[5]杨颖红,王向阳.一种新的按位块分段快速排序算法[J].微电子学与计算机,2006,23(8):136-143.
[6]宋耀虎,庹清.基于Java按位拆分快速排序算法的数值仿真[J].吉首大学学报:自然科学版,2010,31(5):43-44.
[7]王向阳.一种新的分〖WW)〗“档”〖WW(〗快速排序算法[J].小型微型计算机系统,2001,22(8):973-976.
[8]钟诚,陈国良.Multisets排序的最优并行算法[J].计算机研究与发展,2003,40(2):336-341.
[9]王向阳.任意分布数据的基数分配链接排序算法[J].计算机学报,2000,23(7):774-778.
[10]PIGEON S.QuickSort and radix sorts on lists[J].Software Tools for the Professional Programmer,2002,27(5):89-91.
[11]张建中.快速分组排序[J].数值计算与计算机应用,1988,9(2):139-143.
[12]唐开山.按位段分块排序法[J].微计算机应用,1997,18(3):154-157.
[13]CHEN J C.Proportion split sort[J].Nordic Journal of Computing,1996,3(3):271-279.
[14]HOARE C A R.Quicksort[J].The Computer Journal,1962,15(1):10-15.
[15]江华,谭新星.一种非比较分段排序算法的研究[J].小型微型计算机系统,2003,20(4):46-48.
[16]唐向阳.分段快速排序法[J].软件学报,1993,4(2):53-57.
[17]KNUTH D E.The art of computer programming,Volume 3:sorting and searching[M].2nd ed.Bedford,Massachusetts:Addison Wesley,1998.
[18]CHEN J C.Quadripartite sort[J].Journal of Algorithms,1998,28(2):258-271.
[19]HARRIS E P,RAMAMOHANARA K.Optimal clustering of relations to improve sorting and partitioning for joins[J].The Computer Journal,1997,40(7):416-434.
[20]IGARASHI Y,WOOD D.Roughly sorting:A generalization of sorting [J].Journal of Information Processing,1991,14(1):36-42.

基于Java的按位拆分快速排序并行算法

Bit-split parallel algorithm for quick sorting based on Java

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	付朝江, 王天奇, 林悦荣. 基于有效并行求解策略的显式有限元分析并行算法[J]. 计算机应用, 2018, 38(4): 1072-1077.
[2]	褚征, 于炯, 鲁亮, 英昌甜, 卞琛, 王跃飞. 基于内存云的大块数据对象并行存取策略[J]. 计算机应用, 2016, 36(6): 1526-1532.
[3]	陈羽中, 郭松荣, 陈宏, 李婉华, 郭昆, 黄启成. 基于并行分类算法的电力客户欠费预警[J]. 计算机应用, 2016, 36(6): 1757-1761.
[4]	王春波, 董红斌, 印桂生, 刘文杰. 基于Hadoop的超像素分割算法[J]. 计算机应用, 2016, 36(11): 2985-2992.
[5]	何莉, 刘晓东, 李松阳, 张倩. 多核环境下并行粒子群算法[J]. 计算机应用, 2015, 35(9): 2482-2485.
[6]	李双李文敬孙环龙林中明. 基于多核机群的人工鱼群并行算法[J]. 计算机应用, 2013, 33(12): 3380-3384.
[7]	柯琦钟诚陈清媛陆向艳. 多核机群上通信高效的整数序列并行排序方法[J]. 计算机应用, 2013, 33(03): 821-824.
[8]	王海峰. 快速复杂网络聚类图形处理器并行算法[J]. 计算机应用, 2012, 32(09): 2458-2462.
[9]	袁晖坪. 广义行（列）对称矩阵的QR分解及其算法[J]. 计算机应用, 2012, 32(04): 990-993.
[10]	周凯汀郑力新林福泳. 周期B样条基函数系数的并行算法[J]. 计算机应用, 2011, 31(07): 1800-1803.
[11]	宋鸿陟傅熠张丽霞彭红星梁华坤. 分割方式的多线程快速排序算法[J]. 计算机应用, 2010, 30(9): 2374-2378.
[12]	苗莎郑晓薇. 三次插值样条曲线拟合多核并行算法[J]. 计算机应用, 2010, 30(12): 3194-3196.
[13]	蔡昭权魏文红王高才郑宗晖卢庆武. 一种基于De Bruijn网络结构的并行矩阵乘算法[J]. 计算机应用, 2009, 29(3): 880-883.
[14]	魏文红李清霞王文丰. 一种基于Biswapped网络的并行矩阵乘算法[J]. 计算机应用, 2009, 29(12): 3218-3220.
[15]	杨邦任立良贺颖庆. 基于快速排序的数字高程模型分级填洼算法[J]. 计算机应用, 2009, 29(11): 3161-3164.