當前位置:首頁 > 資訊 > 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 時間用法 點擊打開鏈接

《算法》實驗一歸并排序與快速排序 時間的比較

版權所有 IT知識庫 CopyRight ? 2009-2015 IT知識庫 IT610.com , All Rights Reserved. 京ICP備09083238號
广东25选5开奖结果