当前位置:首页 > 资讯 > info6 > 正文

《算法》实验一归并排序与快速排序 时间的比较

发表于: 2014-04-16   作者:chen_xinjia   来源:转载   浏览:
摘要: 最近好多作业,好多实验呀。。算法先写出来,也不知道是不是老师的要求#include"stdafx.h" #include #include #include #include"stdlib.h" usingnamespacestd; #definesize100000//要很大才有比较结果,不然为0.。是因为计算机太快了吗?》_《 intA[size]={7,2,55,89,31,3,6,45,6

最近好多作业,好多实验呀。。算法先写出来,也不知道是不是老师的要求

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include<time.h>
#include "stdlib.h" 
using namespace std;
#define size 100000//要很大才有比较结果,不然为0.。是因为计算机太快了吗?   》_《
int A[size] = { 7, 2, 55, 89, 31, 3, 6, 45, 64, 30 }, B[size], C[size];
////////////////////////////////////////////////////////////////////////
//////////////生成N个随机数
void generation()
{
	srand((unsigned)time(0)); //要放在外面不然随机数是一样的;因为时间一样,种子?一样,rand出来的数值一样的
	for (int i = 0; i < size; i++)
	{

		A[i] = rand() % 1000000;// 产生随机数
		B[i] = A[i];
		C[i] = A[i];

	}
}
///////////////////////////////////////////////////////////////////////
//////////////归并排列
void MERGE(int low, int mid, int high)//
{
	int temp = low;
	int a = low, b = mid + 1;
	while (temp <= high)
	{
		if (a == mid + 1)
		{
			for (int i = b; b <= high; b++)
			{
				B[temp++] = A[b];
			}
			break;
		}
		if (b == high + 1)
		{
			for (int i = a; a <= mid; a++)
			{
				B[temp++] = A[a];
			}
			break;
		}
		if (A[a] < A[b])
		{
			B[temp++] = A[a];
			a++;
		}
		else
		{
			B[temp++] = A[b];
			b++;
		}
	}
	for (int i = 0; i < 10; i++)
	{
		A[i] = B[i];
	}
}
void mergesort(int low, int high)//
{
	int mid;
	if (low < high)
	{
		mid = (low + high) / 2;
		mergesort(low, mid);
		mergesort(mid + 1, high);
		MERGE(low, mid, high);
	}
}////////////////////////////////////////////
//以下为快速排列
int  SPLIT(int low, int high)
{
	int w, temp;
	int i = low, x = C[low];
	for (int j = low + 1; j <= high; j++)
	{
		if (C[j] <= x)
		{
			i++;
			if (i != j)
			{
				temp = C[i];
				C[i] = C[j];
				C[j] = temp;
			}
		}
	}
	temp = C[low];
	C[low] = C[i];
	C[i] = temp;
	w = i;
	return w;
}
void quicksort(int low, int high)
{

	int w;
	if (low < high)
	{
		w = SPLIT(low, high);
		quicksort(low, w - 1);
		quicksort(w + 1, high);
	}
}
/////////////////////////////////////////
int main()
{
	int m, k = 1, mtime = 0, qtime = 0;
	cout << "请输入要比较的次数:" << endl;
	cin >> m;
	int n = size;
	while (m--)
	{
		cout << "----------------------------------------" << endl;
		cout << "第 " << k++ << " 次比较结果:" << endl;
		generation();
		clock_t start_time = clock();
		mergesort(0, n - 1);
		/*	for (int i = 0; i < n; i++)
			{
			cout << " " << A[i];
			}*/
		clock_t end_time = clock();//获取时间,精确到ms;
		mtime += (end_time - start_time);
		cout << "mergesort 's running time is: " << end_time - start_time << "ms" << endl;//输出运行时间


		clock_t start_time1 = clock();
		quicksort(0, n - 1);
		/*for (int i = 0; i < 10; i++)
		{
		cout << " " << C[i];
		}*/
		clock_t end_time1 = clock();
		qtime += (end_time1 - start_time1);
		cout << "quicksort's running time is: " << end_time1 - start_time1 << "ms" << endl;//输出运行时间
	}
	cout << endl << "=========================================" << endl;
	cout << "mergesort 's average running time is: " << mtime / k << endl;
	cout << "quicksort 's average running time is: " << qtime / k << endl;
	return 0;
}


借鉴借鉴~~~~   rand 时间用法 点击打开链接

《算法》实验一归并排序与快速排序 时间的比较

编辑推荐
最近在做一个算法实验:归并排序和快速排序的比较。 这两种算法在排序方面是非常非常的通俗的了,权
快速排序与归并排序的比较(C语言) 修改后的测试结果:(可是修改之后随机数排序时间的差距还是很大?
对于非比较排序算法,如计数排序、基数排序,大家如果感兴趣,可以查看博客http://10740184.blog.51
上节分析了O(n^2)的算法,这节就分析O(nlgn)的算法-归并,快速和堆排序。 一:综述 O(nlgn) 的算法
这两天一直研究递归和dp,以前虽然了解过,但是不透彻,感觉自己对递归过程的建栈和调用过程一知半
快速排序: 快排效率高,时间复杂度最理想为 O(nlogn) ,最差时间为O(n^2),该算法不稳定。其主要思
一、归并排序:(MergeSort) 将数组分成两半,先对每一半分别排序,然后把有序的两半归并(merge)
归并排序法是一个基于分治法的比较排序方法,其最差情况复杂度为O(nlogn),而快速排序法的复杂度在
在算法系列(三)排序算法上篇 一文中,介绍了冒泡排序,插入排序和选择排序算法。这篇文章继续讲解
快速排序和归并排序都是采用了分治法的策略 分治法是将大的问题逐渐分解成单位元素的问题,然后再从
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号