| 一个新的就地稳定归并算法 |
| |
| 引用本文： | 胡圣荣. 一个新的就地稳定归并算法[J]. 河池学院学报, 2014, 34(5): 49-52 |
| |
| 作者姓名： | 胡圣荣 |
| |
| 作者单位： | 华南农业大学工程学院,广东广州,510642 |
| |
| 摘 要： | 为了消除经典归并算法O(n)的附加空间并保持稳定性,提出一个简便的就地归并算法,它在待归并的第二段头部动态形成缓冲区,存放归并时前段的较大者,并组织成循环队列。对长为m、n的两段,归并时比较次数不超过m+n-1。将算法用于归并排序进行了测试,给出了归并、归并排序两者效率的关系,由排序结果验证了归并的比较次数为最优的O(n),并得出移动次数约为n2/48。
|
| 关 键 词： | 归并 就地归并 归并排序 算法 |
A New Stable in-place Merge Algorithm |
| |
| HU Sheng-rong. A New Stable in-place Merge Algorithm[J]. Journal of Hechi University, 2014, 34(5): 49-52 |
| |
| Authors: | HU Sheng-rong |
| |
| Affiliation: | HU Sheng-rong ( College of Engineering, South China Agricultural University, Guangzhou, Guangdong 510642, China) |
| |
| Abstract: | In order to eliminate the classical merging algorithm＇s additional space of 0 （n） and keep its stability, a simple in - place merging algorithm is presented in the paper. A buffer area is formed dynamically in the head part of the second data block to store the larger elements of the previous one in the merging process, forming a circular queue. For two gorithm was tested throu Resuhs verified optimal adjacent blocks of size m and n, the frequency of comparisons is m ＋ n - 1 at most. The algh merge sort, and the complexity relationship between merge and merge sort was deduced. comparisons of 0 （n） in merging, and the new algorithm＇ s assignments were about rt2/48. |
| |
| Keywords: | merge in - place merge merge sort algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
