[1]李宁,李振,刘秋,等.希尔排序理想最优增量序列的研究[J].常州大学学报(自然科学版),2024,36(06):63-70.[doi:10.3969/j.issn.2095-0411.2024.06.008]
　LI Ning,LI Zhen,LIU Qiu,et al.Research on the ideal optimal increment sequence of Shellsort[J].Journal of Changzhou University(Natural Science Edition),2024,36(06):63-70.[doi:10.3969/j.issn.2095-0411.2024.06.008]
点击复制

希尔排序理想最优增量序列的研究()
分享到：

常州大学学报(自然科学版)[ISSN:2095-0411/CN:32-1822/N]

卷:
第36卷
期数:
2024年06期
页码:
63-70
栏目:
计算机与信息工程
出版日期:
2024-12-03

文章信息/Info

Title:
Research on the ideal optimal increment sequence of Shellsort
文章编号:
2095-0411(2024)06-0063-08
作者:
李宁; 李振; 刘秋; 李博; 袁浩珉; 徐守坤
常州大学 阿里云大数据学院, 江苏 常州 213164
Author(s):
LI Ning;  LI Zhen;  LIU Qiu;  LI Bo;  YUAN Haomin;  XU Shoukun
(Aliyun School of Big Data, Changzhou University, Changzhou 213164, China)
关键词:
希尔排序;  增量序列;  Li序列
Keywords:
Shellsort;  incremental sequence;  Li sequence
分类号:
TP 301.6
DOI:
10.3969/j.issn.2095-0411.2024.06.008
文献标志码:
A
摘要:
希尔排序的运行效率取决于对增量序列的选择。随着新增量序列的提出,希尔排序的执行效率不断提高,然而始终未能求得理想最优增量序列。文章总结增量序列的更新历程,研究希尔排序算法及其各种增量序列,探究理想最优序列。提出一种新的增量序列——Li序列,并给出Li序列的实现过程和具体推导过程。Li序列有待进一步完善,但通过实验,多维度比较Li序列与当前主流增量序列的优劣,证明Li序列是最接近理想最优增量序列的增量序列之一。
Abstract:
The operating efficiency of Shellsort depends on the choice of incremental sequence. With the introduction of new incremental sequences, the execution efficiency of Shellsort has been continuously improved, but the ideal optimal incremental sequence has not been obtained. This paper summarizes the update process of the incremental sequence, studies Shellsort algorithm and its various incremental sequence, and explores the ideal optimal sequence. This paper proposes a new incremental sequence: Li sequence, and gives the realization process and specific derivation process of Li sequence. The Li sequence needs to be further improved, but comparing the advantages and disadvantages of the Li sequence and the current mainstream incremental sequence through experiments in multiple dimensions it is proved that the Li sequence is one of the incremental sequences closest to the ideal optimal incremental sequence.

参考文献/References:

[1] SHELL D L. A high-speed sorting procedure[J]. Communications of the ACM, 1959, 2(7): 30-32.
[2] HIBBARD T N. An empirical study of minimal storage sorting[J]. Communications of the ACM, 1963, 6(5): 206-213.
[3] PAPERNOV A A, STASEVICH G V. A method of information sorting in computer memories[J]. Problemy Peredachi Informatsii, 1965, 1965: 81-98.
[4] PRATT V R. Shellsort and sorting networks[M]. New York: DBLP, 1972.
[5] KNUTH D. The art of computer programming; v 3: sorting and searching[M]. Massachusetts: Addison-Wesley, 1973.
[6] SEDGEWICK R. A new upper bound for Shellsort[J]. Journal of Algorithms, 1986, 7(2): 159-173.
[7] GONNET G H, BAEZA-YATES R. Handbook of algorithms and data structures: in pascal and C[M]. 2nd ed. Boston: Addison-Wesley Longman Publishing, 1991.
[8] TOKUDA N. An improved Shellsort[C]// IFIP 12th World Computer Congress on Algorithms. Amsterdam: North-Holland PubLishing Co., 1992: 449-457.
[9] CIURA M. Best increments for the average case of shellsort[C]// Proceedings of the 13th International Symposium on Fundamentals of Computation Theory: In Freiwalds, Rusins(ed.). London: Springer-Verlag, 2001, 2(13): 106-117.
[10] JIANG T, LI M, VIT?NYI P. A lower bound on the average-case complexity of shellsort[J]. Journal of the ACM, 2000, 47(5): 905-911.
[11] VIT?NYI P. On the average-case complexity of Shellsort[J]. Random Structures & Algorithms, 2018, 52(2): 354-363.
[12] LEE J W, KIM Y S, NO J S. Analysis of modified shell sort for fully homomorphic encryption[J]. IEEE Access, 2021, 9: 126198-126215.
[13] 张连堂, 张博. 希尔排序最佳增量序列研究[J]. 韶关学院学报, 2005, 26(6): 15-18.
[14] 胡圣荣. 希尔排序效率的真实性拟合尝试: Sedgewick增量序列(1982)[J]. 湖北民族学院学报(自然科学版), 2014, 32(2): 218-221.
[15] 谢婷. 希尔排序算法设计思想研究[J]. 铜陵学院学报, 2016, 15(2): 111-112, 126.
[16] 王琼, 李鑫, 窦海波, 等. 同心协力策略优化研究[J]. 常州大学学报(自然科学版), 2020, 32(4): 77-82.
[17] ROSIN C D. Stepping stones to inductive synthesis of low-level looping programs[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 2362-2370.
[18] SEPAHYAR S, VAZIRI R, REZAEI M. Comparing four important sorting algorithms based on their time complexity[C]//Proceedings of the 2019 2nd International Conference on Algorithms, Computing and Artificial Intelligence. Sanya: ACM, 2019: 320-327.

备注/Memo

备注/Memo:
收稿日期: 2024-03-01。
基金项目: 江苏省产学研合作资助项目(BY2022218); 江苏省石油化工过程关键设备数字孪生技术工程研究中心开放课题资助项目(DTEC202103)。
作者简介: 李宁(1974—), 男, 甘肃庆阳人, 硕士, 副教授。通信联系人: 徐守坤(1972—), E-mail: xsk@cczu.edu.cn
更新日期/Last Update: 1900-01-01