sort_compare.cpp

数据结构中的排序算法的比较

#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;
#define MAXSIZE 10000
int init[MAXSIZE];
int t[MAXSIZE];
int size;
int move,compare;

void Swap(int a, int b)
{
	int temp = t[a];
	t[a] = t[b];
	t[b] = temp;
	move += 3;
	return ;
}

void Shift(int a, int b)
{
	t[a] = t[b];
	move ++;
}

void Random(int size)
{
//	init = new int [size];
//	t = new int [size];
	if( size > MAXSIZE )
		size = MAXSIZE;
	for(int i=0; i<size; i++)
		init[i] = rand();
}

void Copy()
{
	for(int i=0; i<size; i++)
		t[i] = init[i];
	return ;
}

void BubbleSort()
{
	for(int i=0; i<size-1; i++)
		for(int j=i+1; j<size; j++)
		{
			if( t[i] > t[j] )
				Swap(i,j);
			compare++;
		}
}

void InsertSort()
{
	for(int i=1; i<size; i++)
	{
		int temp = t[i];
		int j(i);
		while(j > 0 && temp < t[j-1])
		{
			compare++;
			Shift(j,j-1);
			j--;
		}
		t[j] = temp;
		move++;
	}
}

void SelectSort()
{
	for(int i=0; i<size-1; i++)
	{
		int temp(i);
		for(int j=i+1; j<size; j++)
		{
			if( t[j] < t[temp] )
				temp = j;
			compare++;
		}
		if( temp != i )
			Swap(i,temp);
	}
}
/*
void Qsort(int low, int high)
{
	if( low >= high )return ;
	int temp = t[low];
	int l = low;
	int h = high;
	while(l < h)
	{
		while(l < h && t[h] > temp && compare++)--h;
		Shift(l,h);
		while(l < h && t[l] < temp && compare++)++l;
		Shift(h,l);
	}
	Shift(l,low);
	Qsort(low,l-1);
	Qsort(l+1,high);
}
*/
void Qsort(int low,int high)
{
	if( low < high )
	{
		int l = low;
		int h = high;
		int p = (low+high)/2;
		do
		{
			while(t[l] < t[p] && compare++)l++;
			while(t[p] < t[h] && compare++)h--;
			if( l <= h )
			{
				if( p == l )
					p = h;
				else
					if( p == h )
						p = l;
				Swap(l,h);
				l++;
				h--;
			}
		}while( l <= h );
		Qsort(low,h);
		Qsort(l,high);
	}
}
void QuickSort()
{
	Qsort(0,size-1);
}

void ShellInsert(int gap)
{
	for(int i=gap; i<size; i++)
	{
		int temp(t[i]);
		int j(i);
		while(j>=gap && temp < t[j-gap])
		{
			Shift(j,j-gap);
			j -= gap;
			compare++;
		}
		t[j] = temp;
		move++;
	}
}

void FilterDown(int start,int end)
{
	int i=start;
	int j=2*i+1;
	int temp=t[i];
	while(j<=end)
	{
		compare++;
		if(j < end && t[j] < t[j+1])
			j++;
		compare++;
		if(temp >= t[j])break;
		else
		{
			Shift(i,j);
			i=j;
			j=2*j+1;
		}
	}
	t[i] = temp;
	move++;
}

void HeapSort()
{
	for(int i=(size-2)/2;i>=0;i--)
		FilterDown(i,size-1);//形成初始堆
	for(i=size-1;i>=1;i--)
	{
		Swap(0,i);
		FilterDown(0,i-1);//重建最大堆
	}
}

void ShellSort()
{
	int gap(size/2);//增量的初始值
	while(gap)
	{
		ShellInsert(gap);
		gap /= 2;
	}
}
void DisPlay()
{
	cout<<"\n排序结果如下:";
	int i,j(0);
	for(i=0; i<size; i++)
	{
		if( !(j%7) )
			cout<<endl;
		cout<<setw(7)<<t[i];
		j++;
	}
	cout<<endl;
}
int main()
{
	cout<<"请输入测试数据的个数(0<size<10000),以size为0作为程序的结束:";
	int cnt(0);
	while(cin>>size && size )
	{	
		cout<<"************************************";
		cout<<"第 "<<++cnt<<" 次测试的结果如下：\n";
		Random(size);
		Copy();
		move = compare = 0;
		BubbleSort();
	//	DisPlay();
		cout<<"冒泡排序的比较次数是--------"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		Copy();
		move = compare = 0;
		InsertSort();
	//	DisPlay();
		cout<<"直接插入排序的比较次数是----"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		Copy();
		move = compare = 0;
		SelectSort();
	//	DisPlay();
		cout<<"选择排序的比较次数是--------"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		Copy();
		move = compare = 0;
		QuickSort();
	//	DisPlay();
		cout<<"快速排序的比较次数是--------"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		Copy();
		move = compare = 0;
		ShellSort();
	//	DisPlay();
		cout<<"希尔排序的比较次数是--------"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		Copy();
		move = compare = 0;
		HeapSort();
	//	DisPlay();
		cout<<"堆排序的比较次数是----------"<<setw(10)<<compare<<"移动次数是---"<<setw(10)<<move<<'.'<<endl;
		cout<<"\n\n请输入测试数据的个数(size),以size为0作为程序的结束:";
	}
	return 0;
}