sort_cjj.cpp

改进的排序算法分析程序

#include <iostream>
#include <iomanip>

using namespace std;

#include <stdlib.h>
#include <time.h>
#include <math.h>

#include <windows.h>

#include "InsertSort.h"
#include "ShellSort.h"
#include "BubbleSort.h"
#include "BinaryInsertSort.h"
#include "TableInsertSort.h"
#include "QuickSort.h"

#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))

#define N 10000			//排序元素的数目
#define SORT BubbleSort	//排序方法

class timer //单位ms
{
public:
	timer()
	{
		QueryPerformanceFrequency(&litmp);
		dfFreq   =   (double)litmp.QuadPart;
	}
	void start()
	{
		start_t = clock();
		
		QueryPerformanceCounter(&litmp); 
		QPart1   =   litmp.QuadPart;  
	}
	clock_t time()
	{
		return (clock() - start_t);
	}
	double usTime()
	{
		QueryPerformanceCounter(&litmp);
		QPart2 = litmp.QuadPart;   
		
		dfMinus = (double)(QPart2 - QPart1);
		dfTim = dfMinus / dfFreq;

		return dfTim;
	};
private:
	clock_t start_t;
	
	LARGE_INTEGER	litmp;   
	LONGLONG		QPart1,QPart2;   
	double			dfMinus, dfFreq, dfTim;
};

int KCN, RMN;
timer TIMER;

void test(int a[])
{
	TIMER.start();

	SORT < int > (a, N, KCN, RMN);

	cout << "\tTimeSpared: " << TIMER.time() << "ms; " << TIMER.usTime() << "us." << endl;
	cout << "KCN=" << left << setw(11) << KCN;
	cout << "KCN/N=" << left << setw(11) << (double)KCN / N;
	cout << "KCN/N^2=" << left << setw(11) << (double)KCN / N / N;
	cout << "KCN/NlogN=" << left << setw(11) << (double)KCN / N / log((double)N)*log(2.0) << endl;
	cout << "RMN=" << left << setw(11) << RMN;
	cout << "RMN/N=" << left << setw(11) << (double)RMN / N;
	cout << "RMN/N^2=" << left << setw(11) << (double)RMN / N / N;
	cout << "RMN/NlogN=" << left << setw(11) << (double)RMN / N / log((double)N)*log(2.0) << endl;
}

int main()
{
	int i;

	//randomize();为了在相同情况下比较各个排序算法，不加这句
	int* ascending = new int[N]; //升序序列
	int* descending = new int[N]; //降序序列
	int* randomness = new int[N]; //随机序列

	for (i = 0; i < N; i++)
	{
		ascending[i] = i;
		randomness[i] = i;
		descending[i] = N - i - 1;
	}

	for (i = 0; i < N; i++)
		swap(randomness[i], randomness[random(N)]);

	cout << "Sort ascending N=" << N;
	test(ascending);
	cout << "Sort randomness N=" << N;
	test(randomness);
	cout << "Sort descending N=" << N;
	test(descending);

	return 0;
}