quick_sort.cpp

大学数据结构课用的实验程序

//在双向链表上实现快速排序的递归算法。
#include<iostream.h>
struct doulinklisttp{
          int key;
		  doulinklisttp *pre;
		  doulinklisttp *next;
};
void initiate(doulinklisttp &dulist)//初始化链表
{
     dulist.next=NULL;
	 dulist.pre=NULL;
}
void create(doulinklisttp &dulist)//建立链表
{
    int n;
	doulinklisttp *p1,*p2;
	cout<<"please input some numbers\n"
		<<"ended the number list with \"-1\"\n";
	cin>>n;
    p1=new doulinklisttp;//读入第一个数，建立头结点
	p1->key=n;
	dulist.next=p1;
	p1->pre=NULL;
    cin>>n;
	while (n>=0)         //读入剩下的数字，建立完整的链表
	{
	    p2=new doulinklisttp; 
		p2->key=n;
		p2->pre=p1;
		p2->next=NULL;
		p1->next=p2;
		p1=p1->next;
		cin>>n; 
	};
}
void search(doulinklisttp dulist,doulinklisttp *&l,doulinklisttp *&h)//查找新建链表的第一个结点和尾结点
{
	 l=dulist.next; 
	 h=dulist.next;
	 while (h->next!=NULL) 
		 h=h->next;
}
void  quickpass(doulinklisttp *l,doulinklisttp *h,doulinklisttp *&i)//对链表进行第一趟排序
{      
      doulinklisttp *j;
	  int p;
      i=l;
      j=h;
      p=i->key;
      while (i!=j)
	  {
		   while ((i!=j)&&(j->key>=p))  j=j->pre;   //当当前数大于枢轴记录关键字，指针向前移
		   if (j->key<p) i->key=j->key;
           while ((i!=j)&&(i->key<=p))  i=i->next;  //当当前数小于枢轴记录关键字，指针向后移
		   if (i->key>p) j->key=i->key; 
	  } 
      i->key=p;
}
void quicksort(doulinklisttp *l,doulinklisttp *h,doulinklisttp *&i)//对整个链表第归排序
{     
     doulinklisttp *t2;
	 if (l!=h)
	  {  
		  quickpass(l,h,i);
          if (i!=l) quicksort(l,i->pre,t2);       
		  if (i!=h) quicksort(i->next,h,t2);   
	  }
}
void write(doulinklisttp dulist)
{
	doulinklisttp *w2;
	w2=dulist.next;
	while(w2!=NULL)
	{
		cout<<w2->key<<"  ";
	    w2=w2->next;
	};
	cout<<endl;
}
void main()
{
     doulinklisttp doulist,*low,*high,*q;
	 initiate(doulist);
	 create(doulist);
	 cout<<"the input number list is\n";
	 write(doulist);
	 search(doulist,low,high);
	 quicksort(low,high,q);
	 cout<<"the ordered number list is\n";
	 write(doulist);
}
// 颜骏、索利军