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

Question

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

Answer 1

首先只使用正向迭代器在数组上实现快速排序。这是划分步骤。您维护的不变量如下:A[0]是主元我们有两个迭代器(下标)i和j。对于0 <= k <我们有一个[k]><=枢轴。对于j <= k <如果有一个[k]>=主元。k>= i的元素是未知的。如果a[i]>= pivot，则增加i。如果a[i] <枢轴，交换a[i]和a[j]，并增加i和j。>

当你让它在数组中工作时，将算法"翻译"为单链表。