论文部分内容阅读
树排序算法是堆排序算法的变体，本文给出了逻辑堆的结构并将其应用于树排序算法中使得树排序算法的最坏复杂度由原来的４ｎｌｏｇｎ＋Ｏ（ｎ）降低到２ｎｌｏｇｎ＋Ｏ（ｎｌｏｇｌｏｇｎ）＋Ｏ（ｎ），接近于最优堆排序算法（复杂度为ｎｌｏｇｎ＋ｎｌｏｇｌｏｇｎ＋Ｏ（ｎ）），并且对几乎已有序的输入，算法的复杂度为Ｏ（ｎｌｏｇｌｏｇｎ），这在ｎ〈２＾１８的实际应用中基本保持了原树排序算法的优势。