datalist.h

有各种排序算法

#ifndef DATALIST_H
#define DATALIST_H
#include <iostream>
using namespace std;
const int  DefaultSize = 100;
const int M = 8;
template <class T>
class Element {			//数据表元素定义
public:
    T key;				//排序码
    T otherdata;			//其他数据成员
    Element<T>& operator = (Element<T>& x) {
        key = x.key;  otherdata = x.otherdata;
        return *this;
    }
	
	bool operator == (Element<T>& x) 
        { return key == x.key; }	//判*this与x相等
    bool operator <= (Element<T>& x)
        { return key <= x.key; }	//判*this小于或等于x
    bool operator >= (Element<T>& x)
        { return key >= x.key; }	//判*this大于或等于x 
	bool operator > (Element<T>& x)
        { return key > x.key; }	//判*this大于x
    bool operator < (Element<T>& x)
        { return key < x.key; }	//判*this小于x
	template<class T>
	friend istream& operator >> (istream& in,Element<T>& e)
	{
		in >> e.key;
		return in;
	}
	template<class T>
	friend ostream& operator << (ostream& out,Element<T>& e)
	{
		out << e.key;
		return out;
	}
};
template <class T>
class dataList {			//数据表类定义
private:
    Element <T>* Vector;		//存储排序元素的向量
    int maxSize; 			//向量中最大元素个数
    int currentSize; 			//当前元素个数
public:
	int GetSize(){return currentSize;}
    dataList (int maxSz) : maxSize(maxSz), currentSize(0) 
        { Vector = new Element<T>[maxSize]; }
    int Length() { return currentSize; }	    //取表长度
    void Swap (Element<T>& x, Element<T>& y)
        { Element<T> temp = x;  x = y;  y = temp; }
    Element<T>& operator [](int i) 	//取第i个元素
        { return Vector[i]; } 		
    int Partition (const int low, const int high);//快速排序划分
	
	int Partition1(const int low,const int high);
	

	int Partition2(const int low,const int high);
	
	int getRight(){return currentSize -1;}
	Element<T>& median(const int left,const int right);

	template<class T>
	friend void BubbleSort(dataList<T>& d);
	template<class T>
	friend istream& operator >> (istream& in,dataList<T>& d)
	{
		cout << "请输入要排序的各关键码" << endl;
		while(d.currentSize != d.maxSize)
		{
			in >> d.Vector[d.currentSize ++];
		}
		return in;
	}
	template<class T>
	friend ostream& operator << (ostream& out,dataList<T>& d)
	{
		for(int i = 0;i < d.currentSize;i ++)
			out << d.Vector[i] << ' ';
		return out;
	}


};
template<class T>
int dataList<T>::Partition1(const int low,const int high)
{
	int pivotpos = low;
	Element<T> pivot = Vector[low];
	for(int i = low + 1;i <= high;i ++)
	{
		if(Vector[i] < pivot)
		{
			pivotpos ++;
			if(pivotpos != i)Swap(Vector[pivotpos],Vector[i]);
		}	
	}
	Vector[low] = Vector[pivotpos];
	Vector[pivotpos] = pivot;
/*
	for(int i = 0;i < currentSize;i ++)
		cout << Vector[i] << ' ';

		cout << endl;
*/
		return pivotpos;
}

template<class T>
int dataList<T>::Partition2(const int left,const int right)
{
	int i = left,j = right - 1;
	if(left < right)
	{
		Element<T> pivot = median(left,right);
		cout << "pivot:" << pivot << endl;
		for(;;){
			while(i < j && Vector[i] < pivot) i ++;
			while(i < j && pivot < Vector[j]) j --;
			if(i < j)
			{Swap(Vector[i],Vector[j]);i ++;j --;}
			else break;
		}
		if(Vector[i] > pivot){Vector[right] = Vector[i];Vector[i] = pivot;}
	}
	return i;
}

template<class T>
Element<T>& dataList<T>::median(const int left,const int right)
{
	int mid = (left + right)/2;
	int k = left;
	if(Vector[mid] < Vector[k]) k = mid;
	if(Vector[right] < Vector[k])k = right;

	if(k != left) Swap(Vector[k],Vector[left]);
	if(mid != right && Vector[mid] < Vector[right]) Swap(Vector[mid],Vector[right]);
	return Vector[right];
}


#endif //: