Heapsort是一个很好的排序算法,因为它是O(n log n)并且它是就地的.但是,当您有链接列表时,heapsort不再是O(n log n),因为它依赖于对数组的随机访问,而链接列表中没有该数组.因此,您要么丢失了就地属性(但需要定义树状结构是O(n)空间).或者您将需要不使用它们,但请记住链接列表是O(n)用于成员查找.这使运行时复杂性变得像O(n ^ 2 log n),这比bubblesort更糟糕.

只需使用mergesort.您已经有O(n)内存开销要求.