select.h

这是快速排序的源代码

#include <iostream>
using namespace std;
#define NUM 8
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);
		int BinarySearch(T a[],const T& x,int n);
        
		int index;
	private:
		T **table;
		int length,MaxSize;
};

template<class T>
IndirectList<T>::IndirectList(int MaxListSize)
{
	MaxSize=MaxListSize;
	table=new T*[MaxSize];
	length=0;
	index=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<NUM;q++)
			cout<<a[q]<<" ";
		cout<<endl;

		select(a,s,high-1);
		select(a,high+1,t);
	}
}
template <class T>
int IndirectList<T>::BinarySearch(T a[],const T& x,int n)
{
	
	int left=0;
	int right=n-1;
	while(left<=right)
	{
		index++;
		int middle=(left+right)/2;
		if(x==a[middle])
			return middle;
		if(x>a[middle])
			left=middle+1;
		else
			right=middle-1;
	}
	return -1;
}