冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它
们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就
是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数
列的顶端。
在链表中应用冒泡排序,由于链表的元素是动态分配的,并且每个节点包含指向下一个节点
的指针,所以冒泡排序的实现会稍有不同。
以下是冒泡排序在链表中应用的一个简单示例:
```cpp
#include <iostream>
// 定义链表节点结构体
struct Node {
int data;
Node* next;
};
// 创建新节点
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = nullptr;
return newNode;
}
// 链表的冒泡排序
void bubbleSort(Node** head) {
if (*head == nullptr || (*head)->next == nullptr) {
return; // 链表为空或只有一个节点,无需排序
}
Node* current = *head;
Node* next = nullptr;
Node* end = nullptr;
bool swapped;
do {
swapped = false;
end = current;
while (end->next != nullptr) {
end = end->next;
}
end = *head;
while (end->next != nullptr) {