open-graph-logo

373 次

一、实验目的

  1. 掌握各种常用排序的算法思想;
  2. 掌握各种常用排序的算法实现;
  3. 掌握各种常用排序时间复杂度,比较各种排序的优缺点。

二、实验相关知识

  1. 复习C语言文件读写的相关知识
  2. 复习课本中第9章关于内部排序的相关知识点;

三、实验内容与要求

1.编程实现各种排序算法,并对比各种算法的效率。

【设计要求】在给出的代码素材sort.cpp文件中补充main函数中的swtich语句,以及以下排序函数,并比较各种排序方法在对素材文件中的1.data~5.data待排序序列进行排序时所需要的时间。

void shellsort(int data[],int n);//希尔排序

void bubllesort(int data[],int n);//冒泡排序

void quicksort(int data[],int n);//快速排序

void selectsort(int data[],int n);//简单选择排序

void heapsort(int data[],int n);//堆排序

void mergesort(int data[],int n);//合并排序

void radixsort(int data[],int n) ;//基数排序

四、程序代码及运行结果

【程序代码】

  switch(menu)
	    {
	    	case 1:{	    		
	    		start = clock();
	    		insertsort(data, n);
	    		end = clock();
	    		//Printdata(data ,n);//输出数据 
	    		//Outputdata(data ,n);
	    		printf("排序时间为%d毫秒",end-start);
	    		printf("您可以尝试一下其它的排序方法:\n");
	    		break;
	    	}	    		
		case 2: {
			start = clock();
			shellsort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 3: {
			start = clock();
			bubllesort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 4: {
			start = clock();
			quicksort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 5: {
			start = clock();
			selectsort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 6: {
			start = clock();
			heapsort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 7: {
			start = clock();
			mergesort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
		case 8: {
			start = clock();
			radixsort(data, n);
			end = clock();
			//Printdata(data, n);//输出数据 
			//Outputdata(data, n);
			printf("排序时间为%d毫秒", end - start);
			printf("您可以尝试一下其它的排序方法:\n");
			break;
		}
			default: {
				printf("没有这种排序方式,请选择正确的排序方法:\n");		   
			}	    
	    }
void shellsort(int data[],int n)//希尔排序 
{  
	int i, j, x;
	do
	{
		n = n / 3 + 1;
		for (i = 1; i < n; i++)
		{
			x = data[i];
			for (j = i - 1; j >= 0; j--)
			{
				if (data[j] > x)
					data[j + 1] = data[j];
				else break;
			}
			if (j != i) data[j + 1] = x;
		}
	} while (a > 1);
}
void bubllesort(int data[],int n)//冒泡排序 
{
	bool kk = true;//优化
	for (int a = 0; a < n - 1 && kk; a++)
	{
		kk = false;
		for (int b = a + 1; b < n; b++)//从前往后扫描
		{
			if (data[a] > data[b])//从小到大排序
			{
				int temp = data[b];//交换
				data[b] = data[a];
				data[a] = temp;
				kk = true;
			}
		}
	}
 }
void quicksort(int data[],int n)//快速排序 
{  
	Qsort(data, 1, n);
}
void Qsort(int a[], int left, int right)
{
	int i, j, t, temp;
	if (left > right)//结束的条件
		return;

	temp = a[left]; //temp中存的就是基准数 
	i = left;
	j = right;
	while (i != j)
	{
		while (a[j] >= temp && i < j)//先从右边开始找
			j--;
		while (a[i] <= temp && i < j)//再找左边的 
			i++;
		if (i < j)//交换两个数在数组中的位置 比基准大的,和比基准小的互换位置
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}

	a[left] = a[i];
	a[i] = temp;

	Qsort(a, left, i - 1);//继续处理左边的,递归
	Qsort(a, i + 1, right);//继续处理右边的 ,递归
}
void selectsort(int data[],int n)//简单选择排序 
{  
	int a, b;
	for (b = 1; b < n; b++)
	{
		int min = b;
		for (a = b + 1; a < n; a++)//找最小值
		{
			if (data[a] < data[min])
			{
				min = a;
			}
		}
		if (b != min)
		{
			int temp = data[b];
			data[b] = data[min];
			data[min] = temp;
		}
	}
}
void heapsort(int data[],int n)//堆排序 
{  
	for (int i = n / 2; i >= 0; i--)//建初堆
	{
		int t = data[i];
		int x = data[i];
		int m = i;
		int j = 2 * m;
		bool finished = false;
		while (j <= n && !finished)
		{
			if (j + 1 <= n && data[j] < data[j + 1])
			{
				j = j + 1;
			}
			if (x >= data[j])
			{
				finished = true;
			}
			else {
				data[m] = data[j];
				m = j;
				j = 2 * m;
			}
		}
		data[m] = t;
	}
	for (int i = n - 1; i >= 1; i--)
	{
		int b = data[0];
		data[0] = data[i];
		data[i] = b;
		int t = data[0];//重建堆
		int x = data[0];
		int m = 0;
		int j = 2 * m;
		bool finished = false;
		while (j <= i - 1 && !finished)
		{
			if (j + 1 <= i - 1 && data[j] < data[j + 1])
			{
				j = j + 1;
			}
			if (x >= data[j])
			{
				finished = true;
			}
			else {
				data[m] = data[j];
				m = j;
				j = 2 * m;
			}
		}
		data[m] = t;
	}
}
void mergesort(int data[],int n)//合并排序
{  
	Msort(data, 0, n - 1, data);
}
void Merge(int r1[], int low, int mid, int high, int r2[]) {
	int i = low; int j = mid + 1; int k = low;
	while ((i <= mid) && (j <= high))
	{
		if (r1[i] <= r1[j]) { r2[k] = r1[i]; i++; }
		else { r2[k] = r1[j]; j++; }
		k++;
	}
	while (i <= mid)
	{
		r2[k] = r1[i];
		k++;
		i++;
	}
	while (j <= high)
	{
		r2[k] = r1[j];
		k++;
		j++;
	}
}
void Msort(int r1[], int low, int high, int r3[])//合并排序
{
	int *r2;
	r2 = (int *)malloc((high + 1) * sizeof(int));
	if (low == high)
	{
		r3[low] = r1[low];
	}
	else
	{
		int mid = (low + high) / 2;
		Msort(r1, low, mid, r2);
		Msort(r1, mid + 1, high, r2);
		Merge(r2, low, mid, high, r3);
	}
	free(r2);
}
void radixsort(int data[],int n)//基数排序
{  
	int *radixArrays[RADIX_10];    //分别为0~9的序列空间  
	for (int i = 0; i < 10; i++)
	{
		radixArrays[i] = (int *)malloc(sizeof(int)* (n + 1));
		radixArrays[i][0] = 0;    //index为0处记录这组数据的个数  
	}

	for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位  
	{
		for (int i = 0; i < n; i++)    //分配过程  
		{
			int num = GetNumInPos(data[i], pos);
			int index = ++radixArrays[num][0];
			radixArrays[num][index] = data[i];
		}

		for (int i = 0, j = 0; i < RADIX_10; i++)    //收集  
		{
			for (int k = 1; k <= radixArrays[i][0]; k++)
				data[j++] = radixArrays[i][k];
			radixArrays[i][0] = 0;    //复位  
		}
	}
}

【运行结果】

【算法时间复杂度分析】

填写各个排序算法在读文件1~5的数据进行排序时,需要的时间,单位:毫秒。

直接插入希尔冒泡快速简单选择归并基数
1.data 143161791281511337
2.data 7481821151342406
3.data 7191861171422368
4.data 1001141351416
5.data 28531648462608313915

五、实验心得体会

巩固了文件读写及排序算法的知识。

赞赏

微信赞赏支付宝赞赏

评论

电子邮件地址不会被公开。 必填项已用*标注

CAPTCHAis initialing...

%d 博主赞过: