| 一个拟就地稳定归并排序算法 |
| |
| 引用本文： | 胡圣荣. 一个拟就地稳定归并排序算法[J]. 湖南理工学院学报：自然科学版, 2014, 0(2): 45-49 |
| |
| 作者姓名： | 胡圣荣 |
| |
| 作者单位： | 华南农业大学工程学院,广州510642 |
| |
| 摘 要： | 为了降低经典归并排序算法O（n）的附加空间并保持稳定性，提出一个新的拟就地归并算法.介绍了根据移动次数导出的段长关系进行选择的原理，给出了相应的归并及归并排序的C语言算法，用大量随机序列进行了排序对比测试；测试组数自动选取，拟合结果为比较次数约为20.13n ln （n）＋1.24n ln（n）-1.22n ，移动次数约为20.655n ln （ n ）-0.89nln（n）＋2.6n、附加栈空间O（ln（n））.得益于算法的简便性，附加程序开销小，在测试范围内实际时空耗费在同类算法中有明显优势.
|
| 关 键 词： | 归并 就地归并 归并排序 算法 |
A Stable In-situ Merge Sort Algorithm |
| |
| HU Sheng-rong. A Stable In-situ Merge Sort Algorithm[J]. Journal of Hunan Institute of Science and Technology, 2014, 0(2): 45-49 |
| |
| Authors: | HU Sheng-rong |
| |
| Affiliation: | HU Sheng-rong (College of Engineering, South China Agricultural University, Guangzhou 510642, China) |
| |
| Abstract: | In order to reduce the O （n） additional space of classical merge sort and keep stability, a new in-situ merging algorithm is presented. The length principle derived from the mobile number of assignments is introduced. Corresponding merge sort in C language was tested by groups of random sequences, the number of groups is also chosen automatically. Results show that the number of comparisons is about20.13nln（n）＋1.24nln（n）？1.22n, the number of assignments is about20.655nln（n）？0.89nln（n）＋2.6n, the additional stack space isO（ln（n））benefiting by simplicity and low additional program cost, the algorithm presented exhibits a clear advantage in both practical time and space consuming compared with an efficient merge sort algorithm. |
| |
| Keywords: | merge in-place merge merge sort algorithm |
| 本文献已被 维普 等数据库收录！ |
|
