「アルゴリズム」実験の集計並べ替えと高速並べ替え時間の比較

3360 ワード

最近宿題がたくさんあって、実験がたくさんありますね.のアルゴリズムを先に書いて、先生の要求かどうか分からない.
#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时间用法点击开链接