就是这样，我需要在链表上实现冒泡排序算法。是的，我在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 ->
我知道这对你们大多数人来说是一些基础知识。但是如果你能花点时间看看这段代码有什么问题，我将非常感激。
是不是我使用的引用指针实现了与双指针相同的功能?例如，这个冒泡排序实现是使用双指针完成的。
交换对于列表来说有点特殊。交换连续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.
}
}
[编辑]
上面的气泡排序是行业中使用的一种。"pedantic"冒泡排序，不知什么原因，现在还在学习:
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;
}
}
imho，这个算法是聪明的慢。
您可以在这里进行修改，并与其他算法和std::list::sort(): https://godbolt.org/z/Yco8WY进行性能比较