HOWTO · C++
在 C++ 中对链表进行排序
本编程教程演示了在 C++ 中对链表数据结构的排序操作的实现。
本页内容
要按升序排列单向链表，可以比较相邻节点的值，并交换顺序错误的值。链表指针保持不变，因此此实现排序的是节点中保存的值，而不是重新连接节点。下面的实现使用冒泡排序，并包含完整的驱动程序。
单向链表存储的内容
单向链表由一串节点组成。每个节点存储一个值，以及一个指向下一节点的指针；最后一个节点指向 nullptr。链表的 head 指针指向首节点。与数组不同，链表节点不必存放在连续的内存位置。要访问某个节点，需要从 head 开始，依次沿着 next 指针前进。
这种结构使得在头部插入只需常数时间，但要找到后续位置则必须遍历。因此，排序时需要沿着指针逐个访问节点。代码使用模板，因此可以存储不同类型的值，前提是该类型支持排序所需的比较和交换操作。
在 C++ 中构建一个简单的单向链表
每个节点在初始化时会同时设置其值和指针。链表负责管理自己的节点，并在析构函数中释放它们；同时禁用复制，以免两个链表意外删除同一批节点。insertAtHead 会将一个值添加到当前首节点之前，displayAll 则按遍历顺序打印各个值。
按升序排列链表
冒泡排序会多次遍历相邻节点对。如果当前值大于下一节点的值，std::swap 就会交换这两个值。每次遍历结束时，尚未归位的最大值会移动到右侧；last 标记边界，使下一轮跳过已排好序的后缀。如果某一轮没有发生交换，算法就会停止。空链表会立即返回，只有一个节点的链表则无需比较。
该排序在最坏情况下需要 O(n²) 时间，并使用 O(1) 额外空间。它保留节点之间的链接，但会改变各节点保存的值。T 必须支持 operator> 且可交换；此实现不会通过重新连接节点来排序。
编译并运行示例
将完整程序保存为 sort.cpp。驱动程序依次在头部插入 50、16 和 45，因此排序前遍历时会依次打印 45、16 和 50。随后程序会对链表排序并显示升序结果。
本节中的代码以及显示的标签或输出仍为英文。
#include <iostream>
#include <utility>
template <class T>
struct Node {
T data;
Node<T>* next;
explicit Node(const T& value) : data(value), next(nullptr) {}
};
template <class T>
class SinglyLinkedList {
private:
Node<T>* head;
public:
SinglyLinkedList() : head(nullptr) {}
SinglyLinkedList(const SinglyLinkedList&) = delete;
SinglyLinkedList& operator=(const SinglyLinkedList&) = delete;
~SinglyLinkedList() {
while (head != nullptr) {
Node<T>* next = head->next;
delete head;
head = next;
}
}
void insertAtHead(const T& value) {
Node<T>* node = new Node<T>(value);
node->next = head;
head = node;
}
void displayAll() const {
const Node<T>* current = head;
while (current != nullptr) {
std::cout << current->data << '\n';
current = current->next;
}
}
void sortLinkedList() {
if (head == nullptr) {
return;
}
Node<T>* last = nullptr;
bool swapped;
do {
swapped = false;
Node<T>* current = head;
while (current->next != last) {
if (current->data > current->next->data) {
using std::swap;
swap(current->data, current->next->data);
swapped = true;
}
current = current->next;
}
last = current;
} while (swapped);
}
};
int main() {
SinglyLinkedList<int> list;
list.insertAtHead(50);
list.insertAtHead(16);
list.insertAtHead(45);
std::cout << "Before sorting:\n";
list.displayAll();
list.sortLinkedList();
std::cout << "After sorting:\n";
list.displayAll();
}
已验证的运行结果如下。输出块中的 Before sorting: 和 After sorting: 标签保留英文；其中的数值展示了排序前后的链表内容。
Before sorting:
45
16
50
After sorting:
16
45
50
请在文件所在目录中使用 C++11 或更高版本的编译器进行编译和运行：
g++ -std=c++11 -Wall -Wextra -pedantic sort.cpp -o sort
./sort
显示操作会每行输出一个值，与上方输出一致。
