如何在C ++中实现冒泡排序？

Question

我已经尝试在单链表上实现冒泡排序（通过更改指针）。我想知道此解决方案出了什么问题。似乎很清楚，应该可以工作，但是我是C ++的初学者，所以我想我犯了一些我无法发现的错误。这是代码：

#include <iostream>
using namespace std;

struct node{
    int value;
    node *next = nullptr;
};

void print(node* n){
    while(n){
        cout<< n->value << " ";
        n = n->next;
    }
    cout << endl;
}

void replace(node*& first, node* second){
    node* tmp = second->next;
    second->next = first;
    first->next = tmp;
    first = second;
}

void bubbleSortRecu(node*& head, int length){
    if(!head || !head->next || length == 1) return;
    node* n = head;
    int counter = length - 1;
    while(n->next && counter){
        if(n->value > n->next->value)
            // std::swap(n->value, n->next->value); // swaping values works fine
            replace(n, n->next);
        n = n->next;
        counter --;
    }
    bubbleSortRecu(head, --length);
}

int main(){

    node* list = new node{4};
    list->next = new node{3};
    list->next->next = new node{5};
    list->next->next->next = new node{1};
    list->next->next->next->next = new node{0};

    cout << "Original: ";
    print(list);

    cout << "Replaced: ";
    replace(list, list->next);
    replace(list->next->next->next, list->next->next->next->next);
    print(list);

    bubbleSortRecu(list, 5);
    cout << "After bubblesort: ";
    print(list);

    return 0;
}

我已经在列表的前两个元素和后两个元素上测试了replace函数。有效。打电话给bubbleSortRecu(list, 5)后，我的名单坏了。输出为：

Original: 4 3 5 1 0 
Replaced: 3 4 5 0 1 
After bubblesort: 3 4 5  

您能解释一下如何解决它，我在哪里出错？

Answer 1

实际上，您不交换节点，仅交换指向下一个节点的指针。

尤其是，您不会修改指向to您尝试交换的节点的指针。

例如，如果

a -> b -> c -> d

并且您想要交换b和c，那么a现在应该指向c，而不是b。此外，c应指向b，等等。>

因此，有获取意义

a -> c -> b -> d
使用您的方法，您会得到：

a -> b -> d
c -> c
因此，链条断裂。 

一个简单的解决方法是简单地在节点内交换value，而无需修改指针。

void replace(node* first, node* second){
    std::swap (first->value, second->value);
}