有几个记录存储在带头结点的双向链表中,如下图所示。现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)
时间: 2024-03-23 11:39:26 浏览: 17
算法步骤如下:
1. 定义一个指向双向链表头节点的指针,用于遍历链表。
2. 定义两个指向链表节点的指针,分别指向相邻的两个节点。
3. 定义一个布尔变量,用于记录是否发生了交换操作。
4. 开始进行排序,外层循环从头节点开始遍历链表,内层循环从链表尾部开始向前遍历,这样每次可以找到未排序部分中最大和最小的两个元素。
5. 如果当前节点的值比后一个节点的值大,则交换这两个节点的值,并将布尔变量设为 true。
6. 如果内层循环结束后布尔变量仍然为 false,说明已经排好序了,直接退出循环即可。
以下是实现代码:
```
void bubbleSort(node *head) {
if(head == NULL || head->next == NULL) return;
node *p, *q;
bool swapped = true;
while(swapped) {
swapped = false;
p = head->next;
q = p->next;
while(q != NULL) {
if(p->data > q->data) {
int tmp = p->data;
p->data = q->data;
q->data = tmp;
swapped = true;
}
p = p->next;
q = q->next;
}
}
}
```