快速排序无法按预期使用链表
Quick sort not working as intended with linked list
前言：
我不关心我的特定快速排序算法的可行性。这不是问题所在。我很好奇为什么我已经编写的程序会以它的方式运行，而不是为什么我应该使用 STL 或其他任何东西。这是为了学习目的。 （例如，我知道选择枢轴作为头部并不是最好的情况——但这不是我要问的）
问题：
我有一个由Node*组成的链表。我专门为它写了一个快速排序算法。它的工作原理是采用给定的链表，并根据选定的 pivot 递归地将其拆分为子列表。枢轴始终是列表的 head（前面），子列表 left 和 right 分别是包含小于和大于枢轴 than/equal 的值的列表.我几乎把它弄下来了，但我不知道如何正确 add_link 枢轴。在之前的迭代中，我总是 add_link 将枢轴指向正确的子列表，但这导致了无限循环，所以我在比较值时完全跳过了枢轴。结果列表已排序，但它缺少用于数据透视表的每个值。我应该如何解决这个问题？
这是一个最小的可重现示例：
#include <iostream>
struct Link {
Link(int d=int(), Link* n=nullptr) {
data = d;
next = n;
}
int data;
Link* next;
};
struct LinkList {
Link* sentinel;
size_t size;
LinkList(Link* h=new Link, size_t s=0) {
size = s;
sentinel = h;
}
~LinkList() {
Link* current = sentinel;
while (current != 0) {
Link* next = current->next;
delete current;
current = next;
}
sentinel = 0;
}
};
// Prototypes
Link* sort_q(Link* sentinel);
void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater);
Link* concatenate(Link* lower, Link* greater);
// helpful function calls quick sort
void sort(LinkList& l) {
l.sentinel = sort_q(l.sentinel);
}
// returns false if there sentinel = null; true if add_link was successful
bool add_link(Link* sentinel, Link* add_link, Link*& end) {
if (sentinel == nullptr) {
return false;
}
Link* curr = sentinel;
for (; curr->next; curr = curr->next) {}
curr->next = add_link;
end = curr->next;
return true;
}
Link* sort_q(Link* sentinel) {
Link* lower = nullptr;
Link* greater = nullptr;
Link* cmp = sentinel;
// base case LinkList = null or sentinel->null
if (sentinel == nullptr || sentinel->next == nullptr) {
return sentinel;
}
divide(sentinel, cmp, lower, greater);
lower = sort_q(lower);
greater = sort_q(greater);
return concatenate(lower, greater);
}
void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater) {
lower = new Link, greater = new Link;
// lend is pointer to end of lower subLinkList
// rend is pointer to end of greater subLinkList
Link* lend = nullptr, * rend = nullptr;
// loop through LinkList until end
while (sentinel != nullptr) {
if (sentinel == cmp) {
sentinel = sentinel->next; continue;
}
if (sentinel->data < cmp->data) {
// break current link
Link* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
if (add_link(lend, tmp, lend))
continue;
// otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
lower->next = tmp;
lend = lower->next;
}
else {
// break current link
Link* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
if (add_link(rend, tmp, rend))
continue;
// otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
greater->next = tmp;
rend = greater->next;
}
}
// remove dummy Link(s)
if (lower->next)
lower = lower->next;
else
lower = cmp;
if (greater->next)
greater = greater->next;
else
greater = cmp;
// unlink cmp
cmp->next = nullptr;
}
// connected subLinkLists
Link* concatenate(Link* lower, Link* greater) {
Link* sentinel;
sentinel = lower;
while (lower->next != nullptr) {
lower = lower->next;
}
lower->next = greater;
return sentinel;
}
void print(LinkList &l) {
for (Link* n = l.sentinel; n != NULL; n = n->next) {
std::cout << n->data << '\n';
}
}
int main() {
// set up linked LinkList 8->4->5->11->7->5->3->9->null
Link* sentinel = new Link(8 , new Link(4, new Link(5, new Link(11, new Link(7, new Link(5, new Link(3, new Link(9))))))));
LinkList l(sentinel,5);
sort(l);
print(l);
return 0;
}
我想要的输出是
3
4 // pivot missing from output
5
5
7
8 // pivot missing from output
9
11
但它输出
3
5
5
7
9
11
编辑#1：
我试过在连接之间添加主元，但这也不起作用。它产生不同的结果，但不完全相同。像这样修改 sort_q() 和 partition()：
Link* qsort(Link* sentinel) {
// ... other stuff before modification
return concatenate(lower, cmp); // changed greater argument to pass cmp which is now cmp->next = greater once finishing partition()
}
void partition(Link* sentinel, Link*& cmp, Link*& lower, Link*& greater) {
// .. other stuff before modifications
// remove dummy Link
if (lower->next)
lower = lower->next;
if (greater->next)
greater = greater->next;
cmp->next = greater; // cmp points to greater (greater) sublist
}
输出变为
3
4
5
7
0
8
11
0
您假设您可以同时获得更小和更大的列表，并且您已经确保在调用 divide 之前列表中至少有 2 个项目，所以这很好。
你只需要处理好除法结束时的所有情况。确保 cmp 最终出现在两个列表之一中。几乎与之前一样，但您需要处理较低和较高列表都非空的情况。
// remove dummy node(s)
cmp->next = nullPtr;
if (lower->next && greater->next) {
// we have two lists. put cmp on greater
lower = lower->next;
cmp->next = greater->next;
greater = cmp;
}
else if (lower->next) {
// only a lower list, use cmp on greater
lower = lower->next;
greater = cmp;
}
else if (greater->next) {
// only a greater list, use cmp as lower.
greater = greater->next;
lower = cmp;
}
看到上面，处理所有3种情况，可以简化为：
// remove dummy node(s)
if (lower->next) {
// we have lower node, so put cmp on greater
lower = lower->next;
cmp->next = greater->next;
greater = cmp;
}
else if (greater->next) {
// only a greater list, use cmp as lower.
greater = greater->next;
lower = cmp;
cmp->next = nullPtr;
}
然后使用 concatenate(lower,greater)。虽然可以优化 divide 连接列表和 return 哨兵，但这更像是重写。
编辑：把它们放在一起消除你的内存泄漏，它应该是这样的（注意，我没有编译或测试）
void divide(Node* sentinel, Node* cmp, Node*& lower, Node*& greater) {
lower = nullptr, greater = nullptr;
// lend is pointer to end of lower sublist
// rend is pointer to end of greater sublist
Node* lend = nullptr, * rend = nullptr;
// loop through list until end
while (sentinel != nullptr) {
if (sentinel == cmp) {
sentinel = sentinel->next; continue;
}
if (sentinel->data < cmp->data) {
// break current link
Node* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if sublist is not empty, append current node to sublist and update end pointer
if (append(lend, tmp, lend))
continue;
// otherwise, "append" current node to empty sublist and update end pointer manually
lend = lower = tmp;
}
else {
// break current link
Node* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if sublist is not empty, append current node to sublist and update end pointer
if (append(rend, tmp, rend))
continue;
// otherwise, "append" current node to empty sublist and update end pointer manually
rend = greater = tmp;
}
}
// insert cmp node
if (lower) {
// we have lower node, so put cmp on greater
cmp->next = greater;
greater = cmp;
}
else if (greater) {
// only a greater list, use cmp as lower.
lower = cmp;
cmp->next = nullptr;
}
}
我看到的主要问题是您有时，但不总是，将枢轴添加到 partition() 中的“左”或“右”列表。这种不一致可能违反了 partition() 的预期功能。但是，此功能 未记录 。所以我会修改我的评估，说主要问题是你没有记录你的功能。你的项目越大，就越有可能因为缺乏文档而遇到问题。
文档！
我希望看到 partition() 记录说它将列表分成三部分：左、右和枢轴。
/// Partitions the list starting at `head` into three pieces. Data less than
/// the given partition's data is put in the `left` list, while the remaining
/// data (except `*partition` itself) is put in the `right` list. The third
/// piece consists of `*partition`, which is assumed to be in the given list.
void partition(Node* head, Node* pivot, Node*& left, Node*& right) {
另一种选择可能是立即将枢轴放在这些列表之一中。但是，这些列表将在调用 partition() 后立即进行排序，并且不需要在该排序中包含 *partition。左排序，右排序，然后连接左、分区和右。除了更快，因为在下一个递归调用中要排序的节点更少，将分区节点保留在列表之外将使 gua运行tee 您的列表变得更短每次递归调用。
不过，这是您的决定，因为您是设计师。重要的是决定你想要什么功能，记录它，并遵循这个决定。
强制一致性！
一旦您指定了功能，就可以更轻松地验证您的代码是否尊重您所做的任何设计决策。您的 sort_q() 函数无法说明上述规范，因为它没有将分区添加到列表中。可能有比下面更简单的方法来执行此操作，但下面的方法只需很少重写代码即可达到目的。 （至此sort_q()结束。）
// ** Return left -> pivot -> right, not just left -> right **
return concatenate(left, concatenate(pivot, right));
}
此外，您的 partition() 函数通过（有时）将分区节点添加到您的列表之一来违反此规范。别那样做。将您的链接设置为 null。
// remove dummy node(s)
if (left->next)
left = left->next;
else
left = nullptr; // <-- null, not pivot
if (right->next)
right = right->next;
else
right = nullptr; // <-- null, not pivot
嗯...我之前避免重写您的代码，但这种特殊的结构让我觉得不必要的复杂。如果某个指针不为空，则将其分配给某物。否则（当该指针为 null 时），分配 null 而不是指针（它是 null，所以同样的事情）。说的比较啰嗦。只需分配指针即可。
// remove dummy node(s)
left = left->next;
right = right->next;
// *** Memory leak, as we removed the nodes without deleting them ***
哦，内存泄漏真让人头疼。特别是因为您实际上并不需要虚拟节点。但这离题到一个单独的问题，所以现在我只注意到如果您将 left 和 right 初始化为 nullptr，您的代码将非常接近工作。 （你的提示是，如果 left 被初始化为 nullptr 那么，在调用 append() 的那一刻，当且仅当 left 为空。)
最后一点：如果到目前为止您已经完成了所有这些操作，那么您可能 运行 在某个时候遇到了分段错误。您缺少检查 concatenate()（也许是您开始使用虚拟节点的原因？）
// connected sublists
Node* concatenate(Node* left, Node* right) {
if ( left == nullptr ) // <-- Add this check
return right; // <-- It is very easy to concatenate to nothing.
Node* head = left;
这应该可以解决眼前的问题。不过还有其他需要改进的地方，所以请继续努力。 （你的代码的其他部分我称之为“不必要的复杂”，尽管没有 if 语句变得那么严重 - 也不太明显。）
前言：
我不关心我的特定快速排序算法的可行性。这不是问题所在。我很好奇为什么我已经编写的程序会以它的方式运行，而不是为什么我应该使用 STL 或其他任何东西。这是为了学习目的。 （例如，我知道选择枢轴作为头部并不是最好的情况——但这不是我要问的）
问题：
我有一个由Node*组成的链表。我专门为它写了一个快速排序算法。它的工作原理是采用给定的链表，并根据选定的 pivot 递归地将其拆分为子列表。枢轴始终是列表的 head（前面），子列表 left 和 right 分别是包含小于和大于枢轴 than/equal 的值的列表.我几乎把它弄下来了，但我不知道如何正确 add_link 枢轴。在之前的迭代中，我总是 add_link 将枢轴指向正确的子列表，但这导致了无限循环，所以我在比较值时完全跳过了枢轴。结果列表已排序，但它缺少用于数据透视表的每个值。我应该如何解决这个问题？
这是一个最小的可重现示例：
#include <iostream>
struct Link {
Link(int d=int(), Link* n=nullptr) {
data = d;
next = n;
}
int data;
Link* next;
};
struct LinkList {
Link* sentinel;
size_t size;
LinkList(Link* h=new Link, size_t s=0) {
size = s;
sentinel = h;
}
~LinkList() {
Link* current = sentinel;
while (current != 0) {
Link* next = current->next;
delete current;
current = next;
}
sentinel = 0;
}
};
// Prototypes
Link* sort_q(Link* sentinel);
void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater);
Link* concatenate(Link* lower, Link* greater);
// helpful function calls quick sort
void sort(LinkList& l) {
l.sentinel = sort_q(l.sentinel);
}
// returns false if there sentinel = null; true if add_link was successful
bool add_link(Link* sentinel, Link* add_link, Link*& end) {
if (sentinel == nullptr) {
return false;
}
Link* curr = sentinel;
for (; curr->next; curr = curr->next) {}
curr->next = add_link;
end = curr->next;
return true;
}
Link* sort_q(Link* sentinel) {
Link* lower = nullptr;
Link* greater = nullptr;
Link* cmp = sentinel;
// base case LinkList = null or sentinel->null
if (sentinel == nullptr || sentinel->next == nullptr) {
return sentinel;
}
divide(sentinel, cmp, lower, greater);
lower = sort_q(lower);
greater = sort_q(greater);
return concatenate(lower, greater);
}
void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater) {
lower = new Link, greater = new Link;
// lend is pointer to end of lower subLinkList
// rend is pointer to end of greater subLinkList
Link* lend = nullptr, * rend = nullptr;
// loop through LinkList until end
while (sentinel != nullptr) {
if (sentinel == cmp) {
sentinel = sentinel->next; continue;
}
if (sentinel->data < cmp->data) {
// break current link
Link* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
if (add_link(lend, tmp, lend))
continue;
// otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
lower->next = tmp;
lend = lower->next;
}
else {
// break current link
Link* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if subLinkList is not empty, add_link current Link to subLinkList and update end pointer
if (add_link(rend, tmp, rend))
continue;
// otherwise, "add_link" current Link to empty subLinkList and update end pointer manually
greater->next = tmp;
rend = greater->next;
}
}
// remove dummy Link(s)
if (lower->next)
lower = lower->next;
else
lower = cmp;
if (greater->next)
greater = greater->next;
else
greater = cmp;
// unlink cmp
cmp->next = nullptr;
}
// connected subLinkLists
Link* concatenate(Link* lower, Link* greater) {
Link* sentinel;
sentinel = lower;
while (lower->next != nullptr) {
lower = lower->next;
}
lower->next = greater;
return sentinel;
}
void print(LinkList &l) {
for (Link* n = l.sentinel; n != NULL; n = n->next) {
std::cout << n->data << '\n';
}
}
int main() {
// set up linked LinkList 8->4->5->11->7->5->3->9->null
Link* sentinel = new Link(8 , new Link(4, new Link(5, new Link(11, new Link(7, new Link(5, new Link(3, new Link(9))))))));
LinkList l(sentinel,5);
sort(l);
print(l);
return 0;
}
我想要的输出是
3
4 // pivot missing from output
5
5
7
8 // pivot missing from output
9
11
但它输出
3
5
5
7
9
11
编辑#1：
我试过在连接之间添加主元，但这也不起作用。它产生不同的结果，但不完全相同。像这样修改 sort_q() 和 partition()：
Link* qsort(Link* sentinel) {
// ... other stuff before modification
return concatenate(lower, cmp); // changed greater argument to pass cmp which is now cmp->next = greater once finishing partition()
}
void partition(Link* sentinel, Link*& cmp, Link*& lower, Link*& greater) {
// .. other stuff before modifications
// remove dummy Link
if (lower->next)
lower = lower->next;
if (greater->next)
greater = greater->next;
cmp->next = greater; // cmp points to greater (greater) sublist
}
输出变为
3
4
5
7
0
8
11
0
您假设您可以同时获得更小和更大的列表，并且您已经确保在调用 divide 之前列表中至少有 2 个项目，所以这很好。
你只需要处理好除法结束时的所有情况。确保 cmp 最终出现在两个列表之一中。几乎与之前一样，但您需要处理较低和较高列表都非空的情况。
// remove dummy node(s)
cmp->next = nullPtr;
if (lower->next && greater->next) {
// we have two lists. put cmp on greater
lower = lower->next;
cmp->next = greater->next;
greater = cmp;
}
else if (lower->next) {
// only a lower list, use cmp on greater
lower = lower->next;
greater = cmp;
}
else if (greater->next) {
// only a greater list, use cmp as lower.
greater = greater->next;
lower = cmp;
}
看到上面，处理所有3种情况，可以简化为：
// remove dummy node(s)
if (lower->next) {
// we have lower node, so put cmp on greater
lower = lower->next;
cmp->next = greater->next;
greater = cmp;
}
else if (greater->next) {
// only a greater list, use cmp as lower.
greater = greater->next;
lower = cmp;
cmp->next = nullPtr;
}
然后使用 concatenate(lower,greater)。虽然可以优化 divide 连接列表和 return 哨兵，但这更像是重写。
编辑：把它们放在一起消除你的内存泄漏，它应该是这样的（注意，我没有编译或测试）
void divide(Node* sentinel, Node* cmp, Node*& lower, Node*& greater) {
lower = nullptr, greater = nullptr;
// lend is pointer to end of lower sublist
// rend is pointer to end of greater sublist
Node* lend = nullptr, * rend = nullptr;
// loop through list until end
while (sentinel != nullptr) {
if (sentinel == cmp) {
sentinel = sentinel->next; continue;
}
if (sentinel->data < cmp->data) {
// break current link
Node* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if sublist is not empty, append current node to sublist and update end pointer
if (append(lend, tmp, lend))
continue;
// otherwise, "append" current node to empty sublist and update end pointer manually
lend = lower = tmp;
}
else {
// break current link
Node* tmp = sentinel;
sentinel = sentinel->next;
tmp->next = nullptr;
// if sublist is not empty, append current node to sublist and update end pointer
if (append(rend, tmp, rend))
continue;
// otherwise, "append" current node to empty sublist and update end pointer manually
rend = greater = tmp;
}
}
// insert cmp node
if (lower) {
// we have lower node, so put cmp on greater
cmp->next = greater;
greater = cmp;
}
else if (greater) {
// only a greater list, use cmp as lower.
lower = cmp;
cmp->next = nullptr;
}
}
我看到的主要问题是您有时，但不总是，将枢轴添加到 partition() 中的“左”或“右”列表。这种不一致可能违反了 partition() 的预期功能。但是，此功能 未记录 。所以我会修改我的评估，说主要问题是你没有记录你的功能。你的项目越大，就越有可能因为缺乏文档而遇到问题。
文档！
我希望看到 partition() 记录说它将列表分成三部分：左、右和枢轴。
/// Partitions the list starting at `head` into three pieces. Data less than
/// the given partition's data is put in the `left` list, while the remaining
/// data (except `*partition` itself) is put in the `right` list. The third
/// piece consists of `*partition`, which is assumed to be in the given list.
void partition(Node* head, Node* pivot, Node*& left, Node*& right) {
另一种选择可能是立即将枢轴放在这些列表之一中。但是，这些列表将在调用 partition() 后立即进行排序，并且不需要在该排序中包含 *partition。左排序，右排序，然后连接左、分区和右。除了更快，因为在下一个递归调用中要排序的节点更少，将分区节点保留在列表之外将使 gua运行tee 您的列表变得更短每次递归调用。
不过，这是您的决定，因为您是设计师。重要的是决定你想要什么功能，记录它，并遵循这个决定。
强制一致性！
一旦您指定了功能，就可以更轻松地验证您的代码是否尊重您所做的任何设计决策。您的 sort_q() 函数无法说明上述规范，因为它没有将分区添加到列表中。可能有比下面更简单的方法来执行此操作，但下面的方法只需很少重写代码即可达到目的。 （至此sort_q()结束。）
// ** Return left -> pivot -> right, not just left -> right **
return concatenate(left, concatenate(pivot, right));
}
此外，您的 partition() 函数通过（有时）将分区节点添加到您的列表之一来违反此规范。别那样做。将您的链接设置为 null。
// remove dummy node(s)
if (left->next)
left = left->next;
else
left = nullptr; // <-- null, not pivot
if (right->next)
right = right->next;
else
right = nullptr; // <-- null, not pivot
嗯...我之前避免重写您的代码，但这种特殊的结构让我觉得不必要的复杂。如果某个指针不为空，则将其分配给某物。否则（当该指针为 null 时），分配 null 而不是指针（它是 null，所以同样的事情）。说的比较啰嗦。只需分配指针即可。
// remove dummy node(s)
left = left->next;
right = right->next;
// *** Memory leak, as we removed the nodes without deleting them ***
哦，内存泄漏真让人头疼。特别是因为您实际上并不需要虚拟节点。但这离题到一个单独的问题，所以现在我只注意到如果您将 left 和 right 初始化为 nullptr，您的代码将非常接近工作。 （你的提示是，如果 left 被初始化为 nullptr 那么，在调用 append() 的那一刻，当且仅当 left 为空。)
最后一点：如果到目前为止您已经完成了所有这些操作，那么您可能 运行 在某个时候遇到了分段错误。您缺少检查 concatenate()（也许是您开始使用虚拟节点的原因？）
// connected sublists
Node* concatenate(Node* left, Node* right) {
if ( left == nullptr ) // <-- Add this check
return right; // <-- It is very easy to concatenate to nothing.
Node* head = left;
这应该可以解决眼前的问题。不过还有其他需要改进的地方，所以请继续努力。 （你的代码的其他部分我称之为“不必要的复杂”，尽管没有 if 语句变得那么严重 - 也不太明显。）