| 逻辑堆与树排序 |
| |
| 引用本文： | 武继刚.逻辑堆与树排序[J].烟台大学学报(自然科学与工程版),1996(2):19-23. |
| |
| 作者姓名： | 武继刚 |
| |
| 作者单位： | 烟台大学计算机系 |
| |
| 摘 要： | 树排序算法是堆排序算法的变体，本文给出了逻辑堆的结构并将其应用于树排序算法中使得树排序算法的最坏复杂度由原来的４ｎｌｏｇｎ＋Ｏ（ｎ）降低到２ｎｌｏｇｎ＋Ｏ（ｎｌｏｇｌｏｇｎ）＋Ｏ（ｎ），接近于最优堆排序算法（复杂度为ｎｌｏｇｎ＋ｎｌｏｇｌｏｇｎ＋Ｏ（ｎ），并且对几乎已有序的输入，算法的复杂度为Ｏ（ｎｌｏｇｌｏｇｎ），这在ｎ＜２１８的实际应用中基本保持了原树排序算法的优势．
|
| 关 键 词： | 堆排序，逻辑堆，2－3树，树排序 |
Logic Heap and Treesort |
| |
| Wu Jigang.Logic Heap and Treesort[J].Journal of Yantai University(Natural Science and Engineering edirion),1996(2):19-23. |
| |
| Authors: | Wu Jigang |
| |
| Abstract: | Treesort is the variant of heapsort. The data structure called logie heap used in treesort is presented. The worst complexity of new treesort algorithm is reduced from 4nlogn 0(n) to 2nlogn 0(nlogn) 0(n), especially, to 0(nloglogn) for the input of nearly sorted order. |
| |
| Keywords: | heapsort logic heap 2-3 tree treesort |
| 本文献已被 CNKI 维普 等数据库收录！ |
