将一个杂乱无序的整数序列，按照从小到大的顺序排列并输出。

用第二章的相关知识实现，即先初始化一个空的单链表，然后每读入一个数据，将该数据存入结点并插入单链表，当然，插入时要从头结点开始向后（或从尾结点开始向前）搜索合适的插入位置，以保证插入后仍然有序。

输出时，从头结点开始向后，顺序输出各结点的值。

测试数据不止一组，每组测试数据：

１）先输入无序序列的整数个数n；(n不超过10000)

２）然后连续输入n个整数；

若n的值输入为０值，则输入结束．

与每组输入的测试数据相对应，输出其按从小到大排好序后的整数序列．

注意：每组输出占一行．

  1 #include <iostream>  2 #include <stdio.h>  3 using namespace std;  4 struct link{  5     int key;  6     struct link *pre;  7     struct link *next;  8 };  9  10 void initlist(link &L) 11 { 12     L.next=NULL; 13     L.pre=NULL; 14 } 15 void createlist(link &L,int n) 16 { 17     int a,i; 18     link *p1,*p2; 19     scanf("%d",&a); 20         p1=new link; 21         p1->key=a; 22         L.next=p1; 23         p1->pre=NULL; 24          25         for(i=1;i<n;i++) 26         { 27             scanf("%d",&a); 28             p2=new link; 29             p2->key=a; 30             p2->pre=p1; 31             p2->next=NULL; 32             p1->next=p2; 33             p1=p1->next; 34              35         } 36      37 } 38 void search(link L,link *&low,link *&high) 39 { 40     low=L.next; 41     high=L.next; 42     while(high->next!=NULL) 43         high=high->next; 44 } 45 void firstquick(link L,link *low,link *high,link *&i) 46 { 47     link *j; 48     int p; 49     i=low; 50     j=high; 51     p=i->key; 52     while(i!=j) 53     { 54         while((i!=j)&&(j->key>=p)) 55             j=j->pre; 56         if(j->key<p) 57             i->key=j->key; 58         while((i!=j)&&(i->key<=p)) 59             i=i->next; 60         if(i->key>p) 61             j->key=i->key; 62     } 63     i->key=p; 64 } 65 void allquick(link L,link *low,link *high,link *&i) 66 { 67     link *t; 68     if(low!=high) 69     { 70         firstquick(L,low,high,i); 71         if(i!=low) 72             allquick(L,low,i->pre,t); 73         if(i!=high) 74             allquick(L,i->next,high,t); 75     } 76 } 77 void print(link L) 78 { 79     link *w; 80     w=L.next; 81     while(w!=NULL) 82     { 83         printf("%d ",w->key); 84         w=w->next; 85     }; 86     printf("\n"); 87 } 88 int main() 89 { 90     link L,*low,*high,*q; 91     initlist(L); 92     int n; 93     while(scanf("%d",&n)&&n) 94     { 95         initlist(L); 96     createlist(L,n); 97     search(L,low,high); 98     allquick(L,low,high,q); 99     print(L);100     }101     return 0;102 }