| 分段有序归并排序算法 |
| |
| 引用本文： | 何奉道.分段有序归并排序算法[J].西南交通大学学报,1992,5(5):41-46. |
| |
| 作者姓名： | 何奉道 |
| |
| 作者单位： | 西安交通大学计算机科学与工程系 |
| |
| 摘 要： | 任一数据序列都是分段有序的。基于这一特点，本文提出了分段有序归并排序算法。其最优时
间复杂性为O(n)，空间复杂性为O(1)。最坏情况下的比较次数少于nlogn十O。叨n，小于快
速排序算法的平均比较次数，是同类算法的最优上界。
|
| 关 键 词： | 分段有序 排序 算法分析 |
Merging-Sort Algorithm Based on Segmented Order |
| |
| He Fengdao.Merging-Sort Algorithm Based on Segmented Order[J].Journal of Southwest Jiaotong University,1992,5(5):41-46. |
| |
| Authors: | He Fengdao |
| |
| Institution: | Dept.of Computer Sci.and Eng. |
| |
| Abstract: | According to a set of data being in segmented order.a merging-
sort algorithm is suggested in this paper.Its complexities of
optimal time and space are of O(n)and O(1)respectively.In the
worst case the comparison time is less than nlogn+0.057n and
the average comparison time of quicksort.Therefore it yields a
superior limit of the known sorting algorithms of this kind. |
| |
| Keywords: | Segmented order sorting algorithm analysis |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《西南交通大学学报》浏览原始摘要信息 |
| 点击此处可从《西南交通大学学报》下载免费的PDF全文 |
