如何在C++中实现冒泡排序?
How to implement bubble sort in C++?
我尝试在单链表上实现冒泡排序(通过改变指针)。我想知道这个解决方案有什么问题。它似乎很清楚并且应该可以工作,但我是 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;
}
我已经在列表的前两个和最后两个元素上测试了替换功能。有效。调用 bubbleSortRecu(list, 5)
后,我的列表被破坏了。这是输出:
Original: 4 3 5 1 0
Replaced: 3 4 5 0 1
After bubblesort: 3 4 5
你能解释一下如何解决它以及我在哪里做错了吗?
实际上,您不交换节点,只交换指向下一个节点的指针。
特别是,您不会修改指向到您尝试交换的节点的指针。
例如,如果
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);
}
我尝试在单链表上实现冒泡排序(通过改变指针)。我想知道这个解决方案有什么问题。它似乎很清楚并且应该可以工作,但我是 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;
}
我已经在列表的前两个和最后两个元素上测试了替换功能。有效。调用 bubbleSortRecu(list, 5)
后,我的列表被破坏了。这是输出:
Original: 4 3 5 1 0
Replaced: 3 4 5 0 1
After bubblesort: 3 4 5
你能解释一下如何解决它以及我在哪里做错了吗?
实际上,您不交换节点,只交换指向下一个节点的指针。
特别是,您不会修改指向到您尝试交换的节点的指针。
例如,如果
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);
}