duisort.h

本代码实现了几乎所有的排序算法

#include<iostream.h>
#include<assert.h>

class Dui{
   friend ostream &operator<<( ostream &, const Dui & );
   friend istream &operator>>( istream &, Dui & );
public:
	Dui( int = 10 );                          
	~Dui(){  delete [] ptr;   }                                       
	int &operator[]( int );	
	void Copy(int *Array,int esize);
	int Delete();//
	void HeapSort(int *Array,int esize);                                   
protected:
	int size; 
	int *ptr; 
	int last;
	void Movedown(int);
};

Dui::Dui( int arraySize )
{
   size = ( arraySize > 0 ? arraySize : 10 ); 
   last =-1;////////////////////////////代表为空
   ptr = new int[ size ]; 
   assert( ptr != 0 );              
}

int &Dui::operator[]( int subscript )
{
   assert( 0 <= subscript && subscript < size );

   return ptr[ subscript ]; // reference return
}

istream &operator>>( istream &input, Dui &a )
{
   for ( int i = 0; i < a.size; i++ )
   {
      input >> a.ptr[ i ];
	  if(!cin.fail())
		a.last++;
	  else
		  i=a.size;
   }

   return input;   // enables cin >> x >> y;
}

ostream &operator<<( ostream &output, const Dui &a )
{
	int i;
	if(a.last>=0)
	{
		for ( i = 0; i <= a.last; i++ ) 
		{
			output <<"  " << a.ptr[ i ];

			if ( ( i + 1 ) % 10 == 0 ) // 10 numbers per row of output
				output << endl;
		}
		if ( i % 10 != 0 )
			output << endl;
	}
	else	output<<"  堆为空!"<<endl;
	return output;   // enables cout << x << y;
}
//*********************************************************
void Dui::Copy(int *Array,int esize)
{
	last =-1;////////////////////////////代表为空
	if ( size != esize ) 
	{
		delete [] ptr;         
		size = esize;     
		ptr = new int[ size ]; 
		assert( ptr != 0 );    
	}

    for ( int i = 0; i < size; i++ )
	{
		ptr[ i ] = Array[ i ];  
		last++;//
	}
}

int Dui::Delete()
{
	int temp=ptr[0];

	ptr[0]=ptr[last];
	last--;
	Movedown(0);//按堆的性质调整

	return temp;
}

void Dui::Movedown(int farther)
{
	int small=2*farther+1;
	while (small<=last)
	{
		if(small<last && ptr[small]>ptr[small+1])
			small++;
		if(ptr[farther]>ptr[small])//最小堆不允许父节点比子节点大
		{
			int temp=ptr[farther];
			ptr[farther]=ptr[small];
			ptr[small]=temp;
			
			farther=small;
			small=2*farther+1;
		}
		else	small=last+1;//终止while循环
	}
}

void Dui::HeapSort(int *Array,int esize)
{
	Copy(Array,esize);

	for(int i=(last-1)/2; i>=0 ;i--)
		Movedown(i);//i为最后一个叶节点的父节点

	cout<<"初始最小堆为:"<<endl;
	cout<<*this;
	for(i=0;i<size;i++)
	{	
		Array[i]=Delete();
		cout<<"第"<<(i+1)<<"次处理后堆为:"<<endl;
		cout<<*this;
	}
}