sortlist.h

把数据结构里面的排序算法实现,可以方便大家用来学习。

/*-------------------------------------
 采用顺序表来测试排序算法
----------------------------------------*/
#include "stdafx.h"
#include <iostream>

using namespace std;

const int MaxSize=100;

template <class type> class sortlist;
template <class type> class element{
	friend class sortlist<type>;
private:
	type data;
	//if need other data,you can add them here
public:
	element(){};
	element(type value);
	void SetData(const type value){data=value;}
	type GetData(){return data;}
	element<type> & operator=(element<type> &elem);//编译器应该可以自动产生这样的赋值函数,该行代码有错误,起泡法没有错误
	/*int operator == (type &value);
	int operator != (type &value)*/;
};



template <class type>
element<type>::element(type value)
{
	data=value;
}



template<class type>
element<type> & element<type>::operator=(element<type> & elem)
{
	if(data==elem.data)
		return *this;
	data=elem.data;
	return *this;
}

template <class type> class sortlist{
public:
	element<type> * Arr;
	int CurrentSize;

	sortlist():CurrentSize(0){Arr=new element<type> [MaxSize];}
	~sortlist(){delete []Arr;}
	void swap(element<type> &x,element<type> &y);
	//element<type> &operator[](int n);
	
	//swap sort
	void BubbleSort(sortlist<type> &table);
	void QuickSort(sortlist<type> &table,int low,int high);

	//insert sort
	void InsertSort(sortlist<type> &table);
	void BinaryInsertSort(sortlist<type> &table);
	void ShellSort(sortlist<type> &table);

	//select  sort
	void SelectSort(sortlist<type> &table);

	//merge sort
	void merge(sortlist<type> &sourceTable,sortlist<type> &mergedTable,const int left,const int mid,const int right);
	void mergeone(sortlist<type> &sourceTable,sortlist<type>&mergedTable,int len);
	void MergeSort(sortlist<type> &table);
};

template <class type>
void sortlist<type>::swap(element<type> &x, element<type> &y)
{
	element<type> temp;
	temp=x;
	x=y;
	y=temp;
}

template <class type>
void sortlist<type>::BubbleSort(sortlist<type> &table)//另外一种方法就是不需要参数
{
	int i=0,j=0;
	for(i=table.CurrentSize;i>0;i--)
		for(j=0;j<i-1;j++)
		{
			if(table.Arr[j].GetData()<table.Arr[j+1].GetData())
				swap(table.Arr[j],table.Arr[j+1]);
		}
}

template <class type>
void sortlist<type>::QuickSort(sortlist<type> &table,int low,int high)
{
	int i=low,j=high;
	element<type> pivotloc;
	pivotloc=table.Arr[low];
	while(i<j){
		while(i<j&&table.Arr[j].GetData()>pivotloc.GetData())
			j--;
		if(i<j)
		{
			//table.Arr[i]=table.Arr[j];
			swap(table.Arr[i],table.Arr[j]);
			i++;
		}
		while(i<j&&table.Arr[i].GetData()<pivotloc.GetData())
			i++;
		if(i<j)
		{
			//table.Arr[j]=table.Arr[i];
			swap(table.Arr[j],table.Arr[i]);
			j--;
		}	
		//下面三行，不能移到程序判断外面，不然会产生stack overflow的错误
	table.Arr[i]=pivotloc;//还原基点
	QuickSort(table,low,i-1);
	QuickSort(table,i+1,high);
	}

}

template <class type>

void sortlist<type>::InsertSort(sortlist<type> &table){
	element<type> temp;
	int j;
	for(int i=1;i<table.CurrentSize;i++)
	{
		temp=table.Arr[i];
		j=i;
		while(j>0&&temp.GetData()<table.Arr[j-1].GetData())//为什么这里temp.GetData()用table.Arr[i]代替数据会不对，没道理啊，一样的值。
		{//问题是下面一句可能已经改变table.Arr[i]这个字，虽然i没变，所以以后要多注意这种情况。这跟赋值运算符重载中的self-assignment类似。
			table.Arr[j]=table.Arr[j-1];
			j--;
		}
		table.Arr[j]=temp;
	}
}

template <class type>
void sortlist<type>::BinaryInsertSort(sortlist<type> &table)
{
	element<type> temp;
	int left,right;
	for(int i=1;i<table.CurrentSize;i++)
	{
		left=0;
		right=i-1;
		temp=table.Arr[i];
		while(left<=right)
		{
			int mid=int(right+left)/2;
			if(temp.GetData()>table.Arr[mid].GetData())//技巧啊，注意这里只有当>时，才修改left，因此用table.Arr[left]=temp不会出错。
				left=mid+1;
			else
				right=mid-1;
		}
		for(int k=i;k>left;k--)
			table.Arr[k]=table.Arr[k-1];
		table.Arr[left]=temp;
	}
}



template <class type>
void sortlist<type>::ShellSort(sortlist<type> &table)
{
	element<type> temp;
	int d=table.CurrentSize/2;
	while(d)//when d==0,circle will be stopped
	{
		for(int i=d;i<table.CurrentSize;i++)
		{
			int j=0;
			temp=table.Arr[i];
			for(j=i;j>=d;j-=d)
			{
				if(temp.GetData()<table.Arr[j-d].GetData())
					table.Arr[j]=table.Arr[j-d];
				else break;
			}
			table.Arr[j]=temp;
		}
		d=(int)(d/2);
	}
}

template <class type>
void sortlist<type>::SelectSort(sortlist<type> &table)
{
	int i,j,k;
	for(i=0;i<table.CurrentSize;i++)
	{
		k=i;
		for(j=i+1;j<table.CurrentSize;j++)
		{
			if(table.Arr[k].GetData()>table.Arr[j].GetData())
				k=j;
		}
		if(k!=i)
			swap(table.Arr[k],table.Arr[i]);
	}
}

template <class type>
void sortlist<type>::merge(sortlist<type> &sourceTable, sortlist<type> &mergedTable, const int left, const int mid, const int right)
{
	int i=left,j=mid+1,k=left;
	while(i<=mid&&j<=right)
	{
		if(sourceTable.Arr[i].GetData()<sourceTable.Arr[j].GetData())
		{
			mergedTable.Arr[k]=sourceTable.Arr[i];
			k++;
			i++;
		}
		else
		{
			mergedTable.Arr[k]=sourceTable.Arr[j];
			k++;
			j++;
		}
	}
	if(i<=mid)//必须有=，不然mid这个字没法保存下去
	{
		for(int p=i;p<=mid;p++,k++)
			mergedTable.Arr[k]=sourceTable.Arr[p];
	}
	else
	{
		for(int p=j;p<=right;p++,k++)
			mergedTable.Arr[k]=sourceTable.Arr[p];
	}
}

template <class type>
void sortlist<type>::mergeone(sortlist<type> &sourceTable, sortlist<type> &mergedTable, int len)
{
	int i=0;
	while(i+2*len<=sourceTable.CurrentSize-1)
	{
		merge(sourceTable,mergedTable,i,i+len-1,i+2*len-1);
		i+=2*len;
	}
	if(i+len<=sourceTable.CurrentSize-1)
	{
		merge(sourceTable,mergedTable,i,i+len-1,sourceTable.CurrentSize-1);
	}
	else
	{
		for(;i<=sourceTable.CurrentSize-1;i++)
			mergedTable.Arr[i]=sourceTable.Arr[i];
	}
}

template <class type>
void sortlist<type>::MergeSort(sortlist<type> &table)
{
	sortlist<type> tempTable;
	tempTable.CurrentSize=table.CurrentSize;
	int len=1;
	while(len<table.CurrentSize)
	{
		mergeone(table,tempTable,len);
		len*=2;
		mergeone(tempTable,table,len);
		len*=2;
	}
}