描述：有n个记录存储在带头结点的双向链表中，利用双向冒泡排序方法对其按升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）

代码展示

#include <iostream>
using namespace std;
typedef int ElemType;
// 结点类型定义
typedef struct DulNode
{
	ElemType data;
	struct DulNode* prior; // 前驱指针
	struct DulNode* next; // 后继指针
}DulNode, *DulList;
void CreateList(DulList& DL, int n)
{
	DulNode *p, *rear;
	int tmp;
	DL = new DulNode; // 表头结点，表头结点不存储数据。
	DL->next = NULL;
	DL->prior = NULL;
	rear = DL; // 表尾指针
	while (n--)
	{
		cin >> tmp;
		p = new DulNode; // 生成新的结点
		p->data = tmp;
		p->next = rear->next; // 这里填NULL也可以。
		p->prior = rear;
		rear->next = p;
		rear = p; // 表尾指针更新为最新元素
	}
}
void DoubleWayBubbleSort(DulList& DL)
{// 对存储在带头结点的双向链表DL中的元素进行双向起泡排序
	int flag = 1; // 设标记，可用于提前结束冒泡过程
	DulNode* head = DL; // 双向链表表头，算法过程中是向下起泡的开始结点
	DulNode* tail = NULL; // 双向链表表尾，算法过程中是向上起泡的开始结点
	while (flag)
	{
		DulNode* p = head->next; // 工作指针
		flag = 0; // 假设本趟无交换，用于提前停止
		while (p->next != tail)
		{// 向下起泡
			if (p->data > p->next->data) {
				flag = 1; // 此趟有交换
				DulNode* tmp = p->next; // tmp用于暂时指代将要与p交换的结点
				p->next = tmp->next; // p的后继结点指向tmp的后继结点
				if (tmp->next != NULL) tmp->next->prior = p; // 该后继结点的前驱指针指向p
				p->prior->next = tmp; // p的前驱结点的后继指针指向tmp
				// p的前驱结点变为tmp的前驱结点，p变为tmp的后继结点
				tmp->prior = p->prior; 
				p->prior = tmp;
				tmp->next = p;
				// p = p->next; 这里是因为在交换的过程中p已经移动到下一个位置了
			}
			else {
				p = p->next; // 指向下一结点
			}
		}
		tail = p; // 准备向上起泡
		p = tail->prior;
		while (flag && p->prior != head)
		{ // 向上起泡
			if (p->data < p->prior->data)
			{
				DulNode* tmp = p->prior;
				p->prior = tmp->prior;
				if (tmp->prior != NULL) tmp->prior->next = p;
				p->next->prior = tmp;
				tmp->next = p->next;
				p->next = tmp;
				tmp->prior = p;
			}
			else {
				p = p->prior; 
			}
		}
		head = p; // 为下一次向下起泡作准备
	}

}

void PrintList(DulList DL)
{
	DulNode* p = DL->next;
	while (p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
}
int main(void)
{
	int n;
	cin >> n;
	DulList D;
	CreateList(D, n); // 建表
	cout << "冒泡排序前：";
	PrintList(D); // 打印链表测试生成是否正确
	cout << endl;
	DoubleWayBubbleSort(D);
	cout << "冒泡排序后：";
	PrintList(D);
	return 0;
}

测试结果

上述向下冒泡某一交换过程图解

• 看到这儿的你，要加油，保持热爱，奔赴山海。