moresort.c

改进的排序算法分析程序

#include  <iostream>
#include  <time.h>
#include  <conio.h>

using namespace std;

class Sort
{
private:
	int *base;
	int *arr;
	int length;
	int data_type;
	bool is_display;
	void HeapAdjust(int , int) ;          //堆调整
	void Partition(int , int);           //快速排序的数组分割

public:
	Sort(int size, int kind, char display);     //分配数组内存
	~Sort();                       //释放分配的内存

	void Show();               //显示数组的值
	bool Copy();                                //内存拷贝
	void Display();                             //最后输出显示

	void RunTime(int runtime)
	{
		cout << "花费时间" << (long double) runtime / CLOCKS_PER_SEC << endl;
	}  //计算排序算法运行时间

	void BubbleSort();                  //冒泡排序
	void QuickSort();      //快速排序
	void HeapSort();                  //堆排序
	void SelectionSort();            //选择排序
	void InsertSort();              //插入排序
	void ShellSort();              //希尔排序
	void RadixSort();             //基数排序
}
;

Sort::Sort(int size = 100, int kind = 0, char display = 'N')
{
	int i;

	length = size;
	data_type = kind;

	if (display == 'Y' || display == 'y')
		is_display = true;
	else
		is_display = false;

	//基于base数组分配内存并赋随机值
	base = (int*)malloc(sizeof(int) * size);
	if (!base)
	{
		cerr << "The system malloc memory error!" << endl;
		exit(1);
	}
	switch (kind)           //base数组赋值类型选择(0--随机值    1--正序      2--逆序)
	{
		case 0:
			i = clock();
			srand(i);
			for (i = 0;i < size;i++)
				base[i] = ::rand();
			break;
		case 1:
			for (i = 0;i < size;i++)
				base[i] = i;
			break;
		case 2:
			for (i = 0;i < size;i++)
				base[i] = (size - i);
			break;
		default:
			break;
	}

	//基于arr数组分配内存并赋0值
	arr = (int*)malloc(sizeof(int) * length);
	if (!arr)
	{
		cerr << "The system malloc memory error!" << endl;
		exit(1);
	}

	memset(arr, 0, sizeof(arr));
}


Sort::~Sort()
{
	free(base);
	free(arr);
}

/*    显示arr数组值   */
void Sort::Show()
{
	int i;
	if (is_display)
	{
		system("PAUSE");
		for (i = 0;i < length;i++)
			cout << arr[i] << '\t';
		cout << endl << endl << endl;
	}
}

/* 数组拷贝    */
bool Sort::Copy()
{
	int i;

	for (i = 0;i < length;i++)
		arr[i] = base[i];

	return true;
}

/*  冒泡排序    */
void Sort::BubbleSort()
{
	int i, j, t;
	for (i = 0;i < length;i++)
		for (j = i;j < length;j++)
			if (arr[i] > arr[j])
			{
				t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
}

/*   快速排序   */

void Sort::Partition(int low, int high)
{
	int i, j, t;

	if (low < high)
	{
		i = low ;
		j = high;
		t = arr[low];

		while (i < j)
		{
			while (i < j && arr[j] > t)
				j-- ;
			if (i < j)
				arr[i++] = arr[j];
			while (i < j && arr[i] <= t)
				i++ ;
			if (i < j)
				arr[j--] = arr[i];
		}

		arr[i] = t;
		Sort::Partition(low, i - 1);
		Sort::Partition(i + 1, high);
	}
}
void Sort::QuickSort()
{
	Sort::Partition(0, length - 1 );
}


/*   堆排序   */
void Sort::HeapAdjust(int k, int n)
{
	int i, j;
	int tmp;

	i = k;
	j = 2 * i + 1;
	tmp = arr[i];

	while (j < n)
	{
		if ((j < n - 1) && (arr[j] < arr[j + 1]))
			j++;

		if (tmp < arr[j])
		{
			arr[i] = arr[j];
			i = j;
			j = 2 * i + 1;
		}
		else
			break;
	}

	arr[i] = tmp;
}

void Sort::HeapSort()
{
	int k, des;
	long tmp;
	int n = length;

	for (k = n / 2 - 1;k >= 0;k--)  /*建堆*/
		Sort::HeapAdjust(k, n);

	for (des = n - 1;des > 0;des--) /*排序*/
	{
		tmp = arr[0];
		arr[0] = arr[des];
		arr[des] = tmp;
		Sort::HeapAdjust(0, des);
	}
}

/* 选择排序 */
void Sort::SelectionSort()
{
	int i, j, t, mins = 0;

	for (i = 0;i < length;i++)
	{
		int mins = i;

		for (j = i + 1;j < length;j++)
			if (arr[j] < arr[mins])
				mins = j;

		t = arr[i];
		arr[i] = arr[mins];
		arr[mins] = t;
	}
}


/*  插入排序      */
void Sort::InsertSort()
{
	int i, j, t;

	for (i = length - 1; i > 0; i--)     //确定arr数组中最小值，并放在arr[0]做哨兵位
		if (arr[i] < arr[i - 1])
		{
			t = arr[i];
			arr[i] = arr[i - 1];
			arr[i - 1] = t;
		}

	for (i = 2; i < length; i++)
	{
		int j = i;
		t = arr[i];

		while (t < arr[j - 1])
		{
			arr[j] = arr[j - 1];
			j--;
		}
		arr[j] = t;
	}
}

/*  希尔排序  */
void Sort::ShellSort()
{
	int i, j, h, v;

	for (h = 1; h <= length / 9; h = 3 * h + 1)
		;     //查找确定最大增量值

	for (; h > 0;h /= 3)
		for (i = h; i < length; i++)    //直接插入排序的一种改进（与直接插入排序比较）
		{
			j = i;
			v = arr[i];
			while (j >= h && v < arr[j - h])
			{
				arr[j] = arr[j - h];
				j -= h;
			}
			arr[j] = v;
		}
}


/* 基数排序 */
void Sort::RadixSort()
{
	int keysize = 5;
	int n = length;
	int i, j, k, t;
	int d, e, m = 0;
	int *c[10], z[10];

	for (i = 0;i < 10;i++)
		c[i] = (int*)malloc(sizeof(int) * n);

	for (i = 0;i < keysize;i++)
	{
		memset(z, 0, sizeof(z));

		for (j = 0;j < n;j++)
		{
			k = arr[j];
			for (t = 0;t < i;t++)
				k = k / 10;
			k = k % 10;
			*(c[k] + z[k]) = arr[j];
			z[k]++;
		}

		m = 0;
		for (d = 0;d < 10;d++)
		{
			for (e = 0;e < z[d];e++)
			{
				arr[m] = *(c[d] + e);
				m++;
			}
		}
	}

	for (i = 0;i < 10;i++)
		free(c[i]);
}

void Sort::Display()
{
	int start_time, end_time;

	cout << "--------－快速排序----------" << endl;
	if (data_type == 0)
	{
		Sort::Copy();
		start_time = clock();
		Sort::QuickSort();
		end_time = clock();
		Sort::RunTime(end_time - start_time);
		Sort::Show();
	}
	else
		cerr << "正反序情况时，快速排序可能会导致堆栈溢出，故屏蔽测试" << endl << endl;

	cout << "--------－堆排序------------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::HeapSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();


	cout << "--------－希尔排序----------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::ShellSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();


	cout << "--------－基数排序----------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::RadixSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();

	cout << "--------－插入排序----------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::InsertSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();


	cout << "----------选择排序-----------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::SelectionSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();


	cout << "-----------冒泡排序---------" << endl;
	Sort::Copy();
	start_time = clock();
	Sort::BubbleSort();
	end_time = clock();
	Sort::RunTime(end_time - start_time);
	Sort::Show();
}

void main()
{
	int size, kind;
	bool ct;
	char sz = 'N', ch;

	do
	{
		cout << " 输入测试的试验数据个数: (N>0) " << endl;
		do
		{
			cin >> size;
		}
		while (size < 1 && (cout << "数据个数应该大于1,请重新输入:" << endl));

		cout << " 输入测试类型值 : (0--随机数   1--正序  2--逆序) " << endl;
		do
		{
			cin >> kind;
		}
		while (((kind > 2) || (kind < 0)) && (cout << "类型值范围(0-2),请重新输入:" << endl));

		if (size < 50000)
		{
			cout << " 是否显示排序结果(Y/N):" << endl;
			do
			{
				cin >> sz;
			}
			while ((sz != 'Y' && sz != 'N' && sz != 'y' && sz != 'n') && (cout << "请输入(Y or N):" << endl));
		}
		else
			cout << "输出测试值太多( >50000 ),没有必要显示" << endl << endl << endl;
		;
		Sort t(size, kind, sz);
		t.Display();
		cout << endl << "是否继续？(Y/N)" << endl;
		do
		{
			cin >> ch;
		}
		while ((ch != 'Y' && ch != 'N' && ch != 'y' && ch != 'n') && (cout << "请输入(Y or N):" << endl));
		if (ch == 'Y' || ch == 'y')
			ct = true;
		else
			ct = false;
	}
	while (ct == true);

	system("PAUSE");
}