使用链表实现冒泡排序有什么问题？
这就是我需要在链表上实现冒泡排序算法的地方。是的，我在Stack Overflow中看到了很多解决这个问题的答案。它们几乎都是使用指向指针的指针来实现的。在这里，我尝试使用引用指针而不是双指针来实现此功能。我花了一天多的时间来找出我的代码出了什么问题。
我的冒泡排序和交换函数的实现如下所示：
struct node
{
int data;
node* next;
node(int x)
{
data = x;
next = NULL;
}
};node* swap(node *a, node *b){
node* temp = b->next;
b->next = a;
a->next = temp;
return b;
}void bubbleSort(node*& head) {
node* ptr = head;
node* last = NULL;
int swapped;
do
{
swapped = 0;
ptr = head;
while (ptr->next != last)
{
if (ptr->data > ptr->next->data)
{
if (ptr == head)
{
head = swap(ptr, ptr->next);
swapped = 1;
}
else{
ptr = swap(ptr, ptr->next);
swapped = 1;
}
}
ptr = ptr->next;
}
} while (swapped);
}上述代码的输出(这是错误的)如下：
The original list =
2 -> 1 -> 4 -> 3 -> 6 -> 5 ->
The Sorted list =
1 -> 2 -> 4 -> 6 -> 我知道这对你们中的大多数人来说都是一些基础知识。但是，如果你能花点时间看看这段代码出了什么问题，我将不胜感激。
不是因为我使用了引用指针来完成与双指针相同的事情。例如，this bubble-sort implementation is done using double-pointers?
回答 1
Stack Overflow用户
发布于 2021-02-06 14:17:44
交换对于列表来说有点特殊。交换2个连续的节点涉及接触4个节点、2个交换的节点以及它们之前的节点。这就是为什么您的sort()输出的列表长度与其输入的长度不同。
考虑到这一点，交换操作就变成了：
void swap_nodes(Node* a_pred, Node*& a, Node* b_pred, Node*& b)
{
assert(a != nullptr && b != nullptr && b_pred != nullptr);
assert(!a_pred || a_pred->next == a);
assert(b_pred->next == b);
if (a == b)
return;
b_pred->next = a;
if (a_pred)
a_pred->next = b;
Node* t = a->next;
a->next = b->next;
b->next = t;
t = a;
a = b;
b = t;
}此外，如果在内部循环中没有发生交换，则不能通过测试进行早期转义。这个测试只告诉您当前的外部循环节点是最小的，直到结束，而不是范围是完全排序的。
跟踪正在测试的节点之前的节点非常重要，因为不这样做将意味着必须通过再次循环列表来找到这些前置节点。
然后，排序函数变为：
void sort(Node*& head)
{
for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
{
for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
{
if (b->data < a->data)
{
swap_nodes(a_pred, a, b_pred, b);
if (a_pred == nullptr)
head = a;
}
}
}
}如果你想优化一点，你不能减少比较的数量，但你可以减少掉期的数量，你可以尝试这样做：
void sort(Node*& head)
{
for (Node* a = head, *a_pred = nullptr; a != nullptr; a_pred = a, a = a->next)
{
// find smallest node value in [a, end)
Node* small_pred = a_pred;
Node* small = a;
for (Node* b = a->next, *b_pred = a; b != nullptr; b_pred = b, b = b->next)
{
if (b->data < small->data)
{
small_pred = b_pred;
small = b;
}
}
if (small != a)
{
// remove smallest from list.
small_pred->next = small->next;
// insert smallest before a.
small->next = a;
if (a_pred == nullptr) // same as a == head
head = small;
else
a_pred->next = small;
// keep outer loop happy, by making it look like a swap.
a = small;
}
// node a is now the smallest node in range [a, end)
// move on to the next.
}
}编辑
上面的冒泡排序是行业中使用的排序。“学究”的气泡分类，由于某种未知的原因，仍然在被教授：
void pedantic_bubble_sort(Node*& head) {
for (Node* sentinel = nullptr; sentinel != head;) {
bool swaps = false;
for (Node *pred = nullptr, *a = head, *b = a->next; a && b;
pred = a, a = b, b = b->next) {
if (b->data < a->data) {
swap_nodes(pred, a, a, b);
if (!pred) head = a;
swaps = true;
}
if (b->next == sentinel) {
sentinel = b;
break;
}
}
if (!swaps) break;
}
}我的天啊，这个算法非常慢。
您可以在这里对其进行修补，并与其他算法和std::list::sort()：https://godbolt.org/z/Yco8WY进行性能比较
https://stackoverflow.com/questions/66073601
复制相似问题
腾讯云开发者
