1。 程序基本说明:学计算机的人应该都听说过“快速排序”吧?这个练习程序就是采用了模板和回调函数的小程序。
2。 程序思路:快速排序是一种排序的算法,既然是通用的算法就不应该局限于某种数据类型,而模板和自定义的回调函数就是为了实现算
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 *);
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;
}