heapsort.h

各种排序算法BubbleSort、DichotomySort、HeapSort、InsertSort、MergeSort、QuickSort、ShellSort、

#ifndef HEAPSORT_H
#define HEAPSORT_H
#include<iostream.h>
#include"sort.h"

template <class T>
class MaxHeap      
{
	private:
		T* heapArray;       //存放堆数据的数组
		int CurrentSize;       //当前堆中元素的数目
		int maxSize;           //堆的容量
		void swap(int pos_x,int pos_y);  //交换位置X和Y的元素
		void BuildHeap();         //建堆
	public:
	    int compare;
		int move;
		MaxHeap(const int n,T *);       //构造函数，n表示初始化堆的最大元素数目
		//~MaxHeap(); 
		int get(){return CurrentSize;}
		bool isLeaf(int pos) const;   //如果是叶结点，返回true
		int leftChild(int pos) const;   //返回左子女的位置
		int rightChild(int pos)const;   //返回右子女的位置
		int parent(int pos) const;       //返回父结点的位置
		bool Remove(int pos,T &node);     //删除给定下标的元素
		bool insert(const T &newNode);     //向堆中插入新元素
		T& RemoveMax();                   //从堆顶删除最小值
		void SiftUp(int position);       //从position向上开始调整，使序列成为堆
		void SiftDown(int left);        //筛选法函数，参数left表示开始处理的数组下标
        bool empty();
};
template < class T>
MaxHeap<T>::MaxHeap(const int n , T *tempArray)
{
	compare = 0;
	move = 0;
	if(n <= 0)
	return;
	//CurrentSize=0;
	CurrentSize=maxSize=n;
	//heapArray=new T[maxSize];
    heapArray=tempArray;
	BuildHeap();
}
//template <class T>
//MaxHeap<T>::~MaxHeap()
//{
//	delete []heapArray;
//}
template <class T>                
bool MaxHeap<T>::isLeaf(int pos) const   //如果是叶结点，返回true 
{                               
     return (pos >= CurrentSize/2) && (pos < CurrentSize);
}
template <class T>
void MaxHeap<T>::swap(int pos_x,int pos_y)
{
     T  temp = heapArray[pos_x];
     heapArray[pos_x] = heapArray[pos_y];
	 heapArray[pos_y] = temp;
	 move+=3;
}
template <class T>
bool MaxHeap<T>::empty()
{
	return CurrentSize == 0;
}
template <class T>
void MaxHeap<T>::BuildHeap()
{
	for(int i = CurrentSize/2-1 ; i >= 0 ; i--)    //反复调用筛选函数，只需调用CurrentSize/2-1次
		SiftDown(i);   
}
template <class T>	
int MaxHeap<T>::leftChild(int pos) const   //返回左子女的位置
{
	return 2*pos+1;
}
template <class T>
int MaxHeap<T>::rightChild(int pos)const   //返回右子女的位置
{
	return 2*pos+2;
}
template <class T>
int MaxHeap<T>::parent(int pos) const       //返回父结点的位置
{
	return (pos-1)/2;
}
template <class T>
bool MaxHeap<T>::Remove(int pos,T &node)     //删除给定下标的元素
{
	if( ( pos < 0 ) || ( pos >= CurrentSize ) )
		return false;
	T temp  = heapArray[pos];
	heapArray[pos] = heapArray[--CurrentSize];
	SiftUp(pos);
	SiftDown(pos);
	node = temp;
	return true;
}
template <class T>
bool MaxHeap<T>::insert(const T &newNode)     //向堆中插入新元素
{
	if( CurrentSize == maxSize )
		return false;
	heapArray[CurrentSize] = newNode;
	SiftUp(CurrentSize);
	CurrentSize++;
	return true;
}
template <class T>
T& MaxHeap<T>::RemoveMax()                   //从堆顶删除最大值
{
	if(CurrentSize == 0)
	{
		cout<<"已经为空，不能删除。"<<endl;
		exit(1);
	}
	else
	{
		swap(0 , --CurrentSize);
		if( CurrentSize > 1)
			SiftDown(0);
		return heapArray[CurrentSize];
	}
    move++;
}
template <class T>
void MaxHeap<T>::SiftUp(int position)       //从position向上开始调整，使序列成为堆
{
	int tempPos = position;
	T temp = heapArray[tempPos];
	while( ( tempPos > 0 ) && ( heapArray[parent(tempPos)] < temp ) )
	{
		heapArray[tempPos] = heapArray[parent(tempPos)];	
		tempPos = parent(tempPos);
			compare++;
		    move++;
	}
	heapArray[tempPos] = temp;
	compare++;
	move++;
}
template <class T>
void MaxHeap<T>::SiftDown(int left)        //筛选法函数，参数left表示开始处理的数组下标
{
	int i = left;         //标示父结点
	int j = leftChild(i);   //标示关键值较小的子结点
	T temp = heapArray[i];    //保存父结点
	while(j < CurrentSize)
	{
		compare++;
		if( (j<CurrentSize-1) && ( heapArray[j] < heapArray[j+1]) )
			j++;
		if(temp < heapArray[j])
		{
			heapArray[i] = heapArray[j];
			i = j;
			j = leftChild(j);
			move++;
		}
		else break;
	}
	heapArray[i]=temp;
}
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
template <class Elem>
class HeapSort:public sort<Elem>
{
	public:
		HeapSort(){compareNum = 0 ; moveNum = 0;};
		void Sorts(Elem Array[],int n);
		void print_h(Elem Array[], int n);
	private:
		int compareNum;
		int moveNum;
};
template <class Elem>
void HeapSort<Elem>::Sorts(Elem Array[],int n)
{
	MaxHeap<Elem> max_heap = MaxHeap<Elem>(n,Array);
	for(int i = 0 ; i < n ; i++)
	{
		Array[n-i-1]=max_heap.RemoveMax();	
	}
	compareNum = max_heap.compare;
	moveNum = max_heap.move;
}
template<class Elem>
void HeapSort<Elem>::print_h(Elem Array[], int n)
{
	cout<<"       堆排序      "<<endl;
	cout<<"+++++++++++++++++++"<<endl;
	cout<<"比较次数: "<<compareNum<<endl;
	cout<<"移动次数: "<<moveNum<<endl;
	//print(Array, n);
}
#endif