欢迎登录北京林业大学OJ系统
http://www.bjfuacm.com
295基于双向链表的双向冒泡排序法
描述
有n个记录存储在带头结点的双向链表中，利用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。(注：双向冒泡排序即相邻两趟排序向相反方向冒泡)。
输入
多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。
输出
每组数据输出一行，为从小到大排序后的序列。每两个元素之间用空格隔开。
输入样例 1
5
4 5 3 2 9
6
1 3 5 7 9 2
0
输出样例 1
2 3 4 5 9
1 2 3 5 7 9
#include<iostream>
#include<string>
using namespace std;
typedef struct LNode
{int data;struct LNode *next;struct LNode *prior;
}LNode,*LinkList;
void InitList(LinkList &L,int n)
{L=new LNode; L->next=NULL;LinkList H=L;while(n--){LinkList p=new LNode;cin>>p->data;p->next=L->next;L->next=p;p->prior=L;L=p;}L=H;
}
void Sort(LinkList &L)
{LinkList p=L->next;while(p->next!=NULL)p=p->next;LinkList first=L->next;LinkList last=p; while(first->next!=NULL||last->prior!=L){if(first->next!=NULL){ for(p=first;p->next!=NULL;p=p->next)if(p->data>p->next->data){int t=p->data;p->data=p->next->data;p->next->data=t;}first=first->next;}if(last->prior!=L){for(p=last;p->prior!=L;p=p->prior)if(p->data<p->prior->data){int t=p->data;p->data=p->prior->data;p->prior->data=t;}last=last->prior;}}
}
void Print(LinkList L)
{LinkList p=L->next;while(p->next){cout<<p->data<<" ";p=p->next;}cout<<p->data<<endl;
}
int main()
{int n;while(cin>>n&&n!=0){ LinkList L;InitList(L,n);Sort(L);Print(L);}return 0;
}