//选择排序
#include "stdafx.h"
#include<iostream>
#include<algorithm> //swap()
#include<string> //string类型
#include<conio.h>
#include"SortTestHelper.h"
using namespace std;

/*
思想：假设从小到大排序，前边为排序好的序列，
从剩余未排序的元素中找出最小的元素，与未排序的第一个元素交换值。
参数：待排序数组，数组元素个数；
时间复杂度为
*/
template<typename T>
void selectionSort(T a[],int n)
{
	for(int i=0; i<n; i++)
	{
		int minIndex=i;
		for(int j=i+1; j<n; j++)
		{
			if(a[minIndex]>a[j])
				minIndex = j;
		}
		swap(a[i],a[minIndex]);
	}
}
int main()
{
	const int n=1000;
	int *arr=SortTestHelper::generateRandomArray(n,0,n);
	
	SortTestHelper::printArray(arr,n);
	SortTestHelper::testSort("selectionSort",selectionSort,arr,n);
	delete[] arr; //内存泄漏危险
	//getch();
	return 0;
}


//头文件

#ifndef CTEST_SORTTRSTHELPER_H
#define CTEST_SORTTRSTHELPER_H

#include<ctime> //time(NULL)
#include<cassert> //assert(),错了会中断
#include<string>
using namespace std;
namespace SortTestHelper
{
	/*
	随机生成算法测试用例：生成具有n个元素的随机数组，范围[RangeL,RangeR]
	*/
	int *generateRandomArray(int n, int RangeL, int RangeR)
	{
		assert(RangeL<=RangeR); //检测函数 
		srand(time(NULL)); 
		int *arr=new int[n]; //使用时记得delete[] arr;
		for(int i=0; i<n; i++)
		{
			arr[i]=rand()%(RangeR-RangeL +1) + RangeL;
		}
		return arr;
	}

	template<class T>
	void printArray(T a[],int n) //模板函数：封装打印函数
	{
		for(int i=0; i<n; i++)
		{
			cout<<a[i]<<'\t';
		}
		cout<<endl;
	}

	/*
	测试算法性能：测试函数执行时间的函数
	思想：利用调用前后时钟周期的差，与每秒时钟周期数的比值，计算得到运行了多少秒
	参数：函数名，函数的指针，测试数组，测试数组大小
	*/
	template<typename T>
	void testSort( string sortName, void(*sort) (T[], int), T arr[], int num)
	{
		colck_t startTime= clock(); //clock()时钟周期，返回值clock_t
		sort(arr,num);
		colck_t startTime= clock();

		assert(isSorted(arr,num)); //判断正确性,如果不对，会中断 
		cout<<"sortName()执行时间："<<double(endTime-startTime)/CLOCK_PER_SEC<<"s"<<endl;
		return;
	}

	/*
	测试正确性
	思想：是否出现没有排好序的情况
	*/
	template<class T>
	bool isSorted(T arr[], int n)
	{
		for(int i=0; i<n-1; i++)
		{
			if(arr[i]>arr[i+1])
				return false;
		}
		return true;
	}
}

#endif