问如何在c++中实现链表的快速排序
EN

Stack Overflow用户

提问于 2014-06-10 12:16:05

回答 1查看 610关注 0票数 0

我必须实现单链表的快速排序，双链表的快速排序可以使用cormen中指定的算法来实现，因为节点有指向下一个和前一个元素的指针，但我不知道如何实现链表的快速排序。我已经在网上找过了，但找不到任何有用的东西。任何伪代码或建议都将非常有用。

发布于 2014-06-10 13:30:00

首先，只使用正向迭代器在数组上实现快速排序。以下是分区步骤。你维护的不变量如下:A是枢轴元素，我们有两个迭代器(索引)i和j，对于0，k=，<=。K >= i的元素是未知的。现在，如果ai >= pivot，则递增i。如果ai < pivot，则交换ai和aj，并递增i和j。

当你在一个数组上工作时，把算法“翻译”成单链表。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/24132758

复制

相似问题

问如何在c++中实现链表的快速排序EN