堆对链接列表进行排序 [英] Heap Sort a Linked List

问题描述

我正在尝试在c ++中创建一个排序函数，该函数使用Heap sort对链接列表对象进行排序，但是我不确定如何入门.谁能给我关于如何做的任何想法?我什至不确定如何对链接列表进行排序

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

推荐答案

Heapsort 的工作原理是数据中的堆.仅当您对每个元素具有随机访问时，才能有效地构建堆.

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.

一种更好的链表排序方法是插入排序-尤其是因为您可以作为链表实现的insert()函数的一部分来执行排序.

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.

这篇关于堆对链接列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！