sort.h

对以下5种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。通过随机数据比较各算法的关键字比较次数和关键字移动次数

#ifndef sort_h
#define sort_h


#include <stdio.h>
#include<iostream>
#include <assert.h>
#include<cstdlib>
#include<iomanip>

using namespace std;


template <class T>
class SeqList
{
public:
    SeqList (const int size = 100);
    ~SeqList();
	SeqList& operator = (SeqList& );
	void Bubble();//冒泡排序
	void InsertSort();//插入排序
	void SelectSort();//选择排序
	void QuickSort();//快速排序
	void Shell();//希尔排序
	void HalfInsertSort();//折半插入排序
	void MergeSort();//归并排序的非递归算法
	void HeapSort();//堆排序
	void BidirInsert();//二路插入排序
	void Del();//删除线型表里的元素
	int Length() const;//线形表长度
	int Find( const T & x ) const;//查找值为x的位置
    int Insert ( T & x, int i );//将x插入位置i
    bool IsEmpty()const;//判空
    bool IsFull() const;//判满
    T Get( int i );//查找i位置的元素
    void Print();//打印
	T *data;//线型表的表头指针
private:
    int maxsize;//线型表的最大容纳元素个数
    int last;//线型表表尾指针
};


template < class T>
SeqList <T>::SeqList(const int size)
{
    assert (size >= 0);//Tests a string to see if it is NULL, empty, or longer than 0 characters
	
    if (size > 0)
	{
		maxsize = size;
		last = 0;
		data = new T[maxsize];
		if(data == NULL)
			cout<<"内存申请错误!"<<endl;
    }
};


template < class T>
SeqList <T>::~SeqList()
{
	delete[] data;
}


template <class T>
SeqList <T>& SeqList <T>::operator = (SeqList<T>& s)
{
	if (s.last > 0)
	{
		delete[] data;
		maxsize = s.maxsize;
		last = s.last;
		data = new T[maxsize];
		for(int i=1;i<=last;i++)
		{
			data[i] = s.data[i];
		}
    }
	return *this;
}


template <class T>
void SeqList <T>::Bubble()
{
	int a=1;
	int i=0;
	//	int temp;
	int x=0;
	int y=0;
	
	while(a)
	{
		a = 0;
		for(i=1;i<last;i++)
		{
			if(data[i]>data[i+1])
			{
				data[0]=data[i];
				data[i]=data[i+1];
				data[i+1]=data[0];
				a++;
				x+=3;
			}
			y++;
		}
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
}


template <class T>
void SeqList <T>::InsertSort()
{
/*	SeqList<int> sTemp(Length()+1);
int temp=0;

  sTemp.Insert(temp,0);
  for(int i=0;i<Length()+1;i++)
  {
		temp = Get(i);
		sTemp.Insert(temp,i+1);
		}
	*/
	int x = 0;
	int y = 0;
	
	for(int i=2;i<=last;i++)
	{
		data[0] = data[i];
		x++;
		for(int j=i-1;data[0]<data[j];j--)
		{
			data[j+1] = data[j];
			x++;
			y++;
		}
		data[j+1] = data[0];
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
	/*
	Del();
	for(i=0;i<Length()+1;i++)
	{
	temp = sTemp.Get(i+1);
	Insert(temp,i);
	}
	*/
}


template<class T>
void SeqList <T>::SelectSort()
{
	int a;
	int b = 0;
	//	int temp;
	int n = 0;
	int x = 0;
	int y = 0;
	
	for(int i=1;i<Length();i++)
	{
		a = data[i];
		for(n=i;n<Length();n++)
		{
			x++;
			if(data[n+1]<a)
			{
				a = data[n+1];
				b = n+1;
			}
		}
		if(a==data[i])
			continue;
		data[0] = a;
		data[b] = data[i];
		data[i] = data[0];
		y += 3;
	}
	
	cout<<"比较次数为:"<<x<<endl;
	cout<<"移动次数为:"<<y<<endl;
}


template <class T>
void SeqList<T>::QuickSort()
{
	int x = 0,y = 0;
	QSort(*this,1,Length(),x,y);
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
}


template <class T>
void SeqList <T>::Shell()
{
/*	SeqList<int> sTemp(Length()+1);
int temp=0;

  sTemp.Insert(temp,0);
  for(int i=0;i<Length()+1;i++)
  {
		temp = Get(i);
		sTemp.Insert(temp,i+1);
		}
	*/
	int x = 0;
	int y = 0;
	
	for(int t=last/2;t>=1;t=t/2)
	{
		for(int i=t+1;i<=last;i++)
		{
			data[0] = data[i];
			x++;
			for(int j=i-t;j>0&&data[0]<data[j];j=j-t)
			{
				data[j+t] = data[j];
				x++;
				y++;
			}
			data[j+t] = data[0];
		}
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
	/*
	Del();
	for(i=0;i<Length()+1;i++)
	{
	temp = sTemp.Get(i+1);
	Insert(temp,i);
	}
	*/
}


template <class T>
void SeqList <T>::Del()
{
	if(IsEmpty())
		return;
	last=0;
}


template <class T>
int SeqList <T>::Length() const
{
	return last;
}


template <class T>
int SeqList <T>::Find(const T & x ) const 
{
    int i = 1;
    while (i <= last && data[i] != x)
		i++;
    if ( i > last )
		return 0;
    else
		return i;
}


template <class T>
int SeqList <T>::Insert(T & x, int i)
{
    if (i<1||i > last+1 || last == maxsize - 1 )
		return 0;
    else
	{
		last++;
		for (int j = last; j > i; j--)
			data[j] = data[j-1];
		data[i] = x;
		return 1;
    }
}


template <class T>
bool SeqList <T>::IsEmpty()const
{
	if(last == 0)
		return 1;
	else
		return 0;
}


template <class T>
bool SeqList <T>::IsFull() const
{
	if(last == maxsize - 1)
		return 1;
	else
		return 0;
}


template <class T>
T SeqList <T>::Get(int i)
{
	if(i < 1 || i > last)
		return NULL;
	else 
		return data[i];
}


int Partition(SeqList <int> &L,int first,int end,int &x,int &y)//快速排序划分
{
	int Mark=L.data[first];
	int pivotkey=L.data[first];
	while(first<end)
	{
		while(first<end&&L.data[end]>=pivotkey)
		{
			end--;			
			y++;
		}
		if(first<end) 
		{
			L.data[first] = L.data[end];
			L.data[end] = -1;
			x++;
		}
		while(first<end&&L.data[first]<=pivotkey)
		{			
			first++;			
			y++;
		}
		if(first<end) 
		{
			L.data[end] = L.data[first];
			L.data[first] = -1;
			x++;
		}
		y += 2;
	}
	L.data[first] = Mark;
	return first;
}


void QSort (SeqList<int> &L,int low,int high,int &x,int &y)//快速排序
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(L,low,high,x,y);
		if(pivotloc!=0)
			QSort(L,low,pivotloc-1,x,y);
		if(pivotloc!=high)
			QSort(L,pivotloc+1,high,x,y);
	}
}


template <class T>
void SeqList <T>::Print()
{
    if ( last == 0 )
		cout << "It is empty" ;
    else
		for (int i=1;i<=last;i++)
		{
			cout<<setw(5)<<data[i]<<"  ";
			if (i%8 == 0) 
			{
				cout<<endl;
			}
		}
		cout << endl;
}


template <class T>
void SeqList <T>::HalfInsertSort()
{
	int x = 0;
	int y = 0;
	
	for(int i=2;i<=last;i++)
	{
		data[0] = data[i];
		x++;
		
		int low = 1;
		int high = i-1;
		while(low<=high)//在Key[low...high]中折半查找有序插入的位置
		{
			int m=(low+high)/2;
			if(data[0]<data[m])
				high = m-1;
			else
				low = m+1;
			y++;
		}//while
		for(int j=i-1;j>=high+1;--j) 
		{
			data[j+1] = data[j];
			x++;
		}
		
		data[j+1] = data[0];
		y++;
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
}


template <class T>
void Merge(SeqList<T> &r, SeqList<T> & r1, int s, int m, int t,int &y,int &x)
{
	
	int i = s;
	int j = m+1;
	int k = s;
	
	while (i<=m && j<=t)
	{   
		if (r.data[i]<=r.data[j]) 
		{
			r1.data[k++] = r.data[i++];            //取r[i]和r[j]中较小者放入r1[k]
		}
		else 
		{
			r1.data[k++] = r.data[j++]; 
		}
		y++;
		x++;
	}
	if (i<=m) 
		while (i<=m)                  //若第一个子序列没处理完，则进行收尾处理         
		{
			r1.data[k++] = r.data[i++]; 
		}
		
		else  
			while (j<=t)                  //若第二个子序列没处理完，则进行收尾处理        
			{
				r1.data[k++] = r.data[j++];
			}
}


template <class T>
void MergePass(SeqList<T> & r, SeqList<T> &r1, int n, int h,int &y,int &x)//一趟归并
{
	int i = 0;
	
	while (i<=n-2*h+1)                     //待归并记录至少有两个长度为h的子序列
	{
		Merge(r, r1, i, i+h-1, i+2*h-1,y,x);
        i += 2*h;
	}
	if (i<=(n-h)) 
		Merge(r, r1, i, i+h-1, n,y,x);       //待归并序列中有一个长度小于h
	else
		for (int k=i;k<=n;k++)            //待归并序列中只剩一个子序列
			r1.data[k] = r.data[k];
		x++;
}


template <class T>
void SeqList <T>::MergeSort()//归并排序的非递归算法
{ 
	int h=1;
	int x = 0;
	int y = 0;
	int temp;
	
	int n = Length()+1;
	
	SeqList<int> r1(Length()+1);
	for(int i=0;i<Length()+1;i++)
	{
		temp = Get(i);
		r1.Insert(temp,i+1);
	}
	
	while (h<=n)
	{ 
		MergePass(*this,r1,n-1,h,y,x);           //归并
		h = 2*h;
		MergePass(r1,*this,n-1,h,y,x);
		h = 2*h;
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
}


template <class T>
void SeqList <T>::HeapSort()//堆排序
{
	int i;
	int temp;
	int n = Length();
	int x = 0;
	int y = 0;
	
	for (i=n/2; i>=1; i--)                //初始建堆，从最后一个非终端结点至根结点
		Sift(*this,i,n,y,x);     
	for (i=1; i<n; i++)                //重复执行移走堆顶及重建堆的操作
	{
		temp = data[n-i+1];
		data[n-i+1] = data[1];
		data[1] = temp;
		x = x+3;
		Sift(*this,1,n-i,y,x);		
	}
	
	cout<<"比较次数为:"<<y<<endl;
	cout<<"移动次数为:"<<x<<endl;
}


template <class T>
void Sift(SeqList<T> &L1,int k,int m,int &y,int &x)
{
	int temp;
	int i = k; 
	int j = 2*i;                        //置i为要筛的结点，j为i的左孩子
	while (j<=m)                          //筛选还没有进行到叶子
	{
		if (j<m &&L1.data[j]<L1.data[j+1]) 
		{
			j++;                          //比较i的左右孩子，j为较大者
			y++;
		}		
		if (L1.data[i]>L1.data[j])//根结点已经大于左右孩子中的较大者
			break;
		else
		{
			temp = L1.data[i];
			L1.data[i] = L1.data[j];
			L1.data[j] = temp;                   //将根结点与结点j交换
			i = j;
			j = 2*i;                     //被筛结点位于原来结点j的位置
			
			x = x+3;		   
			y++;
		}
	}
}


template <class T>
void SeqList <T>::BidirInsert()
{
	SeqList<int> sTemp(Length()+1);
	
	int x=0,y=0;
	int i;
	int first = 1;
	int final = 1;

	int n = Length()+1;
	
	sTemp.data[1] = data[1]; /* 将第一个元素放入辅助数组 */
	//利用辅助数组 sTemp.data 进行二路插入排序 
	for ( i = 2; i<n; i++ )
	{
		if ( sTemp.data[final] <= data[i] )
		{   
			y++;
			sTemp.data[++final] = data[i];
			x++;
		} 
		else if ( data[i] <= sTemp.data[first] )
		{
			y++;
			first = (first - 1 + n) % n;
			sTemp.data[first] = data[i];
			x++;
		}
		else
		{
			int index;  
			for ( index = (final - 1 + n) % n;;index = (index - 1 + n) % n)
			{
				if ( sTemp.data[index] <= data[i] )
				{
					y++;
					int  mid = final++;
					/* 元素后移 */
					while ( mid != index )
					{
						sTemp.data[(mid + 1) % n] = sTemp.data[mid];x++;
						mid = (mid - 1 + n) % n;
					}
					sTemp.data[(index + 1) % n] = data[i];x++;
					
					break;
				}
			}
		}
	}
	
	// 将 sTemp.data 的内容按顺序复制到 keys 中 
	for ( i = 1; i<n; i++ )
	{
		data[i] = sTemp.data[first];
		x++;
		first = (first + 1) % n;
	}
	
	cout<<"比较次数为"<<y<<endl;
	cout<<"交换次数为"<<x<<endl;
	
}  // End of bidir_insert 




#endif