堆排序链表
我正在尝试在 C++ 中创建一个排序函数，使用堆排序对链表对象进行排序，但我不知道如何开始。谁能给我任何关于如何做的想法？我什至不确定如何对链接列表进行排序
I'm trying to create a sort function in c++ that sorts a linked list object using Heap sort but I'm not sure how to get started. Can anyone give me any idea on how to do it ? I'm not even sure how I would sort a Linked List
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Heapsort 通过构建 堆出数据。仅当您对每个元素具有随机访问时，构建堆才有效。
第一步是创建一个指向列表对象的指针数组，以便您可以对数组执行通常的堆排序。
最后一步是将指针数组转换回链表。
链接列表的更好排序方法是插入排序——尤其是因为您可以执行sort 作为链表实现的
insert()函数的一部分。Heapsort works by building a heap out of the data. A heap is only efficient to build when you have random-access to each element.
The first step is going to be creating an array of pointers to your list objects, so you can perform the usual heap sort on the array.
The last step will be converting your array of pointers back into a linked list.
A better sorting method for a linked list is an insertion sort -- not least because you can perform the sort as part of your linked list implementation's
insert()function.我必须同意萨诺兹的回答。由于多种原因，堆设置链表效率极低，但首先是它们应该在初始放置时进行排序。也就是说，如果我要尝试，我会创建一个 ArrayList。 links 将所有链接加载到其中。然后你可以把它分成一堆并排序。完成后，只需重新加载从头开始的链接列表即可。
I have to agree with sarnolds answer. It is extremely inefficient to heap set a linked list for a number of reasons but the first being that they should have been sorted upon initial placement. That said, if I were going to try I would create an
ArrayList<T> linksthe load all the links into it. Then you can grab that in heaps and sort them. Once you're finished just reload your linked list starting with thr head.HeapSort 的优点有两个原因 -
1-它是一种就地算法。
2- O(nlogn) 的时间复杂度
O(nlogn) 是因为数组的随机访问特性，但是如果您使用链表，那么您将无法获得数组的随机访问优势。
因此时间复杂度将变为O(n^2)。这不利于排序。
我建议您对链表使用合并排序算法。
HeapSort is good for 2 reasons -
1- It is an In place algorithm.
2- Time complexity of O(nlogn)
The O(nlogn) is because of random access nature of array, But if you use linked list then you would not get random access advantage of array.
Hence the time complexity will become O(n^2). That is not good for sorting.
I will recommend you to use merge sort algo for linked list.