算法效率测试(以排序算法为例)

在慕课网学习了一段时间后，觉得可以了，借鉴讲师们说的和自己的经验，总结下如何测试一个程序代码的效率和开销问题。

以  排序算法为例，具体分析如下：

//main()函数，.cpp文件
// Created by Ant on 07/16/2017
//默认排成升序
//
#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
#include "STL_Sort.h"
#include "SelectionSort.h"
#include "InsertionSort.h"

using namespace std;

int
main() {
	const int SIZE = 10000, left = 1, right = 1000;
	cout << "SIZE = " << SIZE << endl<<endl;
	//生成任一随机数组
	int* arr = SortTestHelper::RandomArray<int>(SIZE, left, right);
	//完全拷贝原始数组元素
	int* arrCo1 = SortTestHelper::CopyArray<int>(arr, SIZE);
	int* arrCo2 = SortTestHelper::CopyArray<int>(arr, SIZE);

	SortTestHelper::PrintArray(arr, 50);	//输出原始数组，乱序
	SortTestHelper::SortingTime("STL_Sort", STL_Sort, arr, SIZE);
	SortTestHelper::PrintArray(arr, 100);	//输出已排好序数组，可用于检查排序结果
	cout << endl;
	
	SortTestHelper::PrintArray(arrCo1, 50);	//可用于确认数组拷贝是否成功
	cout << endl;
	SortTestHelper::SortingTime("DirectSelectionSort", DirectSelectionSort, arrCo1, SIZE);
	SortTestHelper::SortingTime("DirectInsertionSort", DirectInsertionSort, arrCo2, SIZE);
	cout << endl;


	//生成几乎有序数组
	int* test = SortTestHelper::RandomArray<int>(SIZE, 100);
	int* testCo1 = SortTestHelper::CopyArray<int>(test, SIZE);
	int* testCo2 = SortTestHelper::CopyArray<int>(test, SIZE);

	
	SortTestHelper::SortingTime("STL_Sort", STL_Sort, test, SIZE);
	SortTestHelper::SortingTime("DirectSelectionSort", DirectSelectionSort, testCo1, SIZE);
	SortTestHelper::SortingTime("DirectInsertionSort", DirectInsertionSort, testCo2, SIZE);
	cout << endl;

	delete[] arr;
	delete[] arrCo1;
	delete[] arrCo2;

	delete[] test;
	delete[] testCo1;
	delete[] testCo2;
	return 0;
}

排序算法的简单实现：

插入排序

InsertionSort.h文件

#ifndef Sorting_algorithm_InsertionSort_H
#define Sorting_algorithm_InsertionSort_H


//一、直接插入排序
template<typename T>
void	DirectInsertionSort(T a[], int n) {

	for (int i = 1; i < n; ++i) {	//外层循环从第二个元素开始

		//在a[0]~a[i-1]之间寻找a[i]的合适插入位置，即一直是降序直到第一次符合升序要求处，并最终用j记录
		T	temp = a[i];	//必须先存下a[i],否则a[j] = a[j - 1]在第一次移位时会修改a[i]
		int	j ;		//j将是合适位置
		for ( j = i; j > 0 &&  a[j - 1] > temp; --j) {
			a[j] = a[j - 1];//把前边的元素往后挪，用这一操作替换掉每一次的数值交换swap，能减少开销
		}
		//找到合适插入位置j，第二次循环提前终止
		a[j] = temp;
	}
}



//二、




#endif // !Sorting_algorithm_InsertionSort_H

选择排序

SelectionSort.h文件

#ifndef Sorting_algorithm_SelectionSort_H
#define Sorting_algorithm_SelectionSort_H


//直接选择排序
template<typename T>
void	DirectSelectionSort(T a[], int n) {

	for (int i = 0; i < n - 1; ++i) {

	// 先用 k 来存储a[i+1]~a[n-1]之间的最小值的下标索引值,避免多余的数值交换操作swap，选择排序即选出a[MinIndex]
		int	k = i;
		for (int j = i + 1; j < n; ++j ) {
			if (a[j] < a[k])
				k = j; //不断更换成更小的元素值的下标，直至找到最小的
		}
		if (k != i) {
			T	temp = a[i];  a[i] = a[k];  a[k] = temp;
		}
	}
}

#endif // !Sorting_algorithm_SelectionSort_H

STL标准库函数sort()函数：

SortTestHelper.h

//
//Created by Ant on 07/14/2017
//
#ifndef Sorting_algorithm_STL_Sort_H
#define Sorting_algorithm_STL_Sort_H

#include <algorithm>

template<typename T>
void STL_Sort(T arr[], int SIZE) {
	sort(arr, arr + SIZE);
}

#endif // !Sorting_algorithm_STL_Sort_H

算法性能测试辅助文件

//Be helpful to test sorting algorithm
//Created by Ant on 07/14/2017
//
#ifndef Sorting_algorithm_SortTestHelper_H
#define Sorting_algorithm_SortTestHelper_H

#include <iostream>
#include <ctime>
#include <cassert>
#include <ctime>
#include <string>
#include <algorithm>
using namespace std;

namespace SortTestHelper {

	
	//生成含有SIZE个元素的随机数组，每个元素的随机范围是闭区间[rangeL,rangeR]，用于测试排序算法
	template<typename T>
	T*	RandomArray(int SIZE, int rangeL, int rangeR) {

		assert(rangeL <= rangeR);//确保函数的健壮
		T* arr = new T[SIZE];

		srand(time(NULL));
		for (int i = 0; i < SIZE; ++i)
			arr[i] = T(rand()) / RAND_MAX + rand() % (rangeR - rangeL + 1) + rangeL;
		return arr;
	}




	//生成含有SIZE个元素的近乎有序的随机数组，用于凸显插入排序排算法的优势
	template<typename T>
	T*	RandomArray(int SIZE, int swapTimes) {

		assert(SIZE >= swapTimes);//确保函数的健壮

		T* arr = new T[SIZE];
		for (int i = 0; i < SIZE; ++i) {
			arr[i] = i + T(rand())/RAND_MAX ;
		}

		srand(time(NULL));
		for (int i = 0; i < swapTimes; ++i) {
			int	x = rand() % SIZE;
			int y = rand() % SIZE;
			swap(arr[x], arr[y]);
		}
		return arr;
	}




	//拷贝数组
	template<typename T>
	T*	CopyArray(T a[], int SIZE) {
		T* arr = new T[SIZE];
		copy(a, a + SIZE, arr);
		return arr;
	}

	//输出数组
	template<typename T>
	void	PrintArray(T arr[], int SIZE) {
		for (int i = 0; i < SIZE; ++i)
			cout << arr[i] << " ";
		cout << endl;
	}
	




	//判断数组是否已有序(默认排序成功时为升序）
	template<typename T>
	bool isSorted(T arr[], int SIZE) {
		for (int i = 0; i + 1 < SIZE; ++i) {
			if (arr[i] > arr[i + 1])
				return	false;
		}
		return	true;
	}




	//输出某一具体排序函数运行所需时间
	template<typename T>
	void SortingTime(string sortName, void(*sort)(T[], int), T arr[], int SIZE) {

		clock_t startTime = clock();
		sort(arr, SIZE);
		clock_t endTime = clock();

		assert( isSorted(arr, SIZE) );
		cout << "Sorted successfully!\t";
		cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	}
}

#endif // !Sorting_algorithm_SortTestHelper_H

附上一些测试结果:

说明一点，插入排序算法是很值得让人注意的，当 参与排序的数据 是 趋于有序的时候，插入排序算法将会趋于O（N）的算法复杂度，这将是效率最高的排序算法，不过其最坏的算法复杂度同选择排序都是O（N^2），所以又让人爱很不得了……

不过有一点应用是可以肯定的，那就是当使用其他O（NlonN）排序算法实现到最后所以数据趋于整体有序的时候，再通过使用插入排序算法实现后续部分，这将会大大的优化和提高算法效率。明白我说的？好吧。

以上是自己对相关算法的简单实现，设计还不够完善，待更，持续更新中……