select.h

这是快速排序的源代码

#include <iostream>
using namespace std;
#define NUM 10
template<class T>
class IndirectList
{
	public:
		IndirectList(int MaxListSize=10);
		~IndirectList();
		bool IsEmpty()const{return length==0;}
		int Length()const{return length;}
		IndirectList<T>&Insert(int k,const T&x);
		void Output(ostream& out) const;
		void select(T a[],int s,int t);
        
	private:
		T **table;
		int length,MaxSize;
};

template<class T>
IndirectList<T>::IndirectList(int MaxListSize)
{
	MaxSize=MaxListSize;
	table=new T*[MaxSize];
	length=0;
}

template<class T>
IndirectList<T>::~IndirectList()
{
	for(int i=0;i<length;i++)
		delete table[i];
	delete []table;
}




template<class T>
IndirectList<T>& IndirectList<T>::Insert(int k,const T&x)
{
	for(int i=length-1;i>=k;i--)
		table[i+1]=table[i];
	table[k]=new T;
	*table[k]=x;
	length++;
	return *this;
}


template <class T>
void IndirectList<T>::Output(ostream &out) const
{
	for(int i=0;i<length;i++)
		cout<<*table[i]<<" ";
}

template <class T>
ostream& operator<<(ostream& out,const IndirectList<T>& x)
	{
		x.Output(out);
		return out;
	}



template<class T>
void IndirectList<T>::select(T a[],int s,int t)
{
	int low=s;
	int high=t;
	T key;
	if(s<t)
	{
		key=a[low];
		do
		{
			while(low<high&&a[high]>key)
				high--;
			if(low<high&&a[high]<key)
			{
				a[low]=a[high];
				low++;
			}
			while(low<high&&a[low]<key)
				low++;
			if(low<high&&a[low]>key)
			{
				a[high]=a[low];
				high--;
			}
		}while(low<high);
		a[high]=key;
		
		for(int q=0;q<10;q++)
			cout<<a[q]<<" ";
		cout<<endl;
		select(a,s,high-1);
		select(a,high+1,t);
	}
}