「アルゴリズム」実験の集計並べ替えと高速並べ替え時間の比較
3360 ワード
最近宿題がたくさんあって、実験がたくさんありますね.のアルゴリズムを先に書いて、先生の要求かどうか分からない.
参考~~~~rand时间用法点击开链接
#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时间用法点击开链接