冒泡排序算法实现及示例

"冒泡排序—钟以军" 冒泡排序是一种简单的排序算法，它的基本思想是通过重复遍历待排序的元素列表，比较相邻的元素并根据需要交换它们的位置，使得每一轮遍历结束后，最大的元素会“浮”到列表的末尾，就像水中的气泡一样逐渐上浮。这个过程会持续进行，直到整个列表完全排序。 在提供的代码中，作者实现了一个泛型版本的冒泡排序，使用了模板类`link<T>`来表示链表中的节点，其中`T`代表可以是任意类型的数据。链表节点包含一个数据成员`data`，以及两个整型指针`pre`和`next`，分别表示前驱节点和后继节点的索引。链表的头部由`head`变量表示，尾部由`rear`表示。 `sort`函数是冒泡排序的核心，它接受一个指向链表头节点的引用`x`，以及头节点和尾节点的索引`head`和`rear`。首先，初始化一个布尔变量`flag`用于判断是否还有交换发生，以及一个计数器`v`记录已经完成的趟数。在`while(flag)`循环中，进行两层嵌套的循环来遍历链表。内层循环中，如果当前节点的数据大于其后继节点的数据，则交换它们，同时设置`flag`为真，表示有交换发生。外层循环用于控制总的趟数，如果在一轮遍历中没有发生交换，说明列表已经排序完成，跳出循环。 代码中，每完成一趟冒泡排序，都会打印出当前的排序状态，这有助于理解冒泡排序的过程。此外，为了处理链表结构，代码在主函数`main`中创建了一个链表，并让用户输入`n`个整数，然后将这些整数分配给链表节点。最后，调用`sort`函数对链表进行排序，并输出排序后的结果。 这段代码实现了链表形式的冒泡排序，适用于任何可比较类型的元素，而且通过打印中间状态，有助于学习者直观地理解冒泡排序的工作原理。