New Page 1

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

    A.第一版

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

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

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

    	法的通用性。

    3。 主要函数介绍：

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

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

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

>     B. 这个函数就是取分界点的函数，由A的函数调用，依靠传入的自定义元素大小比较函数指针进行大小比较。

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

>     C. 这个函数是一个应用的例子，它是针对我采用的数组为int * 类型下的大小比较函数。

>     bool myComp(int *i, int *j)

>     D. 这是个显示结果的辅助函数，最后一个参数也是自定义的将数组元素转为可显示字符的函数指针。另一个myTrans函数是一个实做的

>     例子函数，针对int *[]数组的将int指针数组元素转为字符的函数。

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

>     char* myTrans(int *);

    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;
    }