采用模板和回调函数的快速排序小程序

A.第一版

这个小程序是最初的版本。

1。 程序基本说明：学计算机的人应该都听说过“快速排序”吧？这个练习程序就是采用了模板和回调函数的小程序。

2。 程序思路：快速排序是一种排序的算法，既然是通用的算法就不应该局限于某种数据类型，而模板和自定义的回调函数就是为了实现算

	法的通用性。

3。 主要函数介绍：

	A. 排序的递归调用的函数，传进的数组的类型采用了模板，并传进了数组的起始，结束参数，最后一个参数是一个数组元素之间进行

	大小比较的自定义的函数指针。

	template <class T>
	void quickSort(T array[], int start, int end, bool (*pfun)(T , T));

4。 不足之处：

	A. 应该可以写成一个类。

	B. 初始化函数应该也传入用户自定义的初始化数组元素的函数指针。

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const ARRAYSIZE = 20;

bool myComp(int *, int *);

char* myTrans(int *);

template <class T>
int part(T [], int, int, bool (*pfun)(T , T));

template <class T>
void quickSort(T array[], int start, int end, bool (*pfun)(T , T));

template <class T>
void sortArray(T array[], int size, bool (*pfun)(T , T));

template <class T>
void initialize(T array[], int size);

template <class T>
void uninitialize(T array[], int size);

template <class T>
void showArray(T array[], int size, char* (*translate)(T));

template <class T>
void Swap(T &i, T & j);

int main()
{

	int * array[ARRAYSIZE];
	srand(time(0));
	initialize(array, ARRAYSIZE);
	showArray(array, ARRAYSIZE, myTrans);
	sortArray(array, ARRAYSIZE, myComp);
	cout<<endl;
	cout<<endl;
	cout<<"now i see"<<endl;
	showArray(array, ARRAYSIZE, myTrans);
	uninitialize(array, ARRAYSIZE);

	return 0;
}

template <class T>
void Swap(T &i, T & j)
{
	T hold;
	hold = i;
	i = j;
	j = hold;
}

template <class T>
void quickSort(T array[], int start, int end, bool (*pfun)(T , T))
{
	

	int mid;

	if (start < end)
	{
		mid = part(array, start, end, pfun);

		quickSort(array, start, mid, pfun);
		quickSort(array, mid + 1,end, pfun);
	}
}

template <class T>
void showArray(T array[], int size, char* (*translate)(T))
{
	for (int i=0; i < size; i++)
	{
		cout<<"array["<<i<<"] = "<<translate(array[i])<<(((i + 1)% 4==0)?"\n":"\t");
	}

}

bool myComp(int *i, int *j)
{
	return (*i > *j);
}

char *myTrans(int *i)
{
	char *result =new char;
	itoa(*i, result, 10);
	return result;
}

template <class T>
void sortArray(T array[], int size, bool (*pfun)(T , T))
{
	quickSort(array, 0, size - 1, pfun);	
}

template <class T>
void initialize(T array[], int size)
{	
	int j;
	for (int i=0; i < size; i++)
	{
		int *p= new int;
		*p = i;
		array[i] = p;
	}
	for (i=0; i< size; i++)
	{
		j = rand() % size;
		Swap(array[i], array[j]);
	}
}

template <class T>
void uninitialize(T array[], int size)
{
	for (int i=0; i< size; i++)
	{
		delete array[i];
	}
}

template <class T>
int part(T array[], int start, int end, bool (*pfun)(T , T))
{
	int result =start;
	int i= start, j = end;
	while (i<j)
	{	
		while (pfun(array[j], array[result])&&j>result)
		{			
			j--;
		}
		if (j > result)
		{
			Swap(array[j], array[result]);
			result = j;
		}

		while (!pfun(array[i],array[result])&&i<result)
		{
			i++;
		}
		if (i< result)
		{
			Swap(array[i], array[result]);
			result = i;
		}	
	}
	return result;
}