前端之家收集整理的这篇文章主要介绍了
c – 使用链接列表进行堆排序，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
我想知道是否有人曾经使用链表进行堆排序,如果他们可以提供
代码.我已经能够使用数组进行heapsort,但是尝试在链表中进行操作似乎不切实际,只是在你知道的地方痛苦.我必须为我正在做的项目实现
链接列表,任何帮助将不胜感激.
我也在使用C.
答案是“你不想在链表上实现堆排序.”
Heapsort是一个很好的排序算法,因为它是O(n log n)并且它是就地的.但是,当您有链接列表时,heapsort不再是O(n log n),因为它依赖于对数组的随机访问,而链接列表中没有该数组.因此,您要么丢失了就地属性(但需要定义树状结构是O(n)空间).或者您将需要不使用它们,但请记住链接列表是O(n)用于成员查找.这使运行时复杂性变得像O(n ^ 2 log n),这比bubblesort更糟糕.
只需使用mergesort.您已经有O(n)内存开销要求.
原文链接：https://www.f2er.com/c/115655.html
