泛型编程与C++标准模板库 : 浅谈sort()排序函数

以前用sort排序的时候,只知道sort函数有如下两种重载方式.

1. template< class RandomIt >　　void sort( RandomIt first, RandomIt last );
   
2. template< class RandomIt, class Compare >　　void sort( RandomIt first, RandomIt last, Compare comp );

当时对这些参数也不是很懂,只知道一些简单的用法.

1).比如: 如下代码可以使数组a从小到大有序排列.

int a[5] = {1,6,9,4,5};

sort(a,a+5);

2).如下代码可以使用自己设定的排序方式进行排序.

bool cmp(int a, int b)

{

        return  a > b;

}

int main()

{

     int a[5] = {4,3,2,7,8};

     sort(a,a+5,cmp);

     return  0;

}

当然,sort()函数需要包含算法头文件#include<algorithm>.

接下来,我们简单分析一下sort()函数的实现:

我们首先看一下sort()源码,这里截个图,如图1:

通过上图,可以清晰的看出,模板库里面的sort()排序还是比较复杂的,里面嵌套了 快排,堆排,插入几种不同的排序方法,同时,会根据不同的数据,调用不同的排序方案,以达到相对较快的排序目的.

当然,我们这里只是简单的分析一下,sort()源代码.为了能说明白,我们将步骤划分为了几步,一步一步的分析.

第一步:这里就不用模板库的快排堆排了,为了简单起见,直接上冒泡:

///////////////////////////////////
///Date   : 2014年8月1日14:14:35
///IDE    : VS2010
///Author : Dujun Qing
//////////////////////////////////

//1).简单的冒泡排序
#include <iostream>
using namespace std;

void maopao(int a[], int len)
{
	int i,j;
	int t = 0;

	for (i = 1; i < len; ++i)
	{
		for (j = 0; j < len-1; ++j)
		{
			if (a[j] > a[j+1])
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
}

int main(void)
{
	int i, a[] = {17,82,37,89,42,76,67,15};
	int len = sizeof(a)/sizeof(a[0]);

	maopao(a,len);

	for (i = 0; i < len; ++i)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;

	return 0;
}

//2).引入函数指针
#include <iostream>
using namespace std;

//比较函数
bool Max(int a, int b)
{
	return a < b;
}

//bool (*cmp)(int, int):一个函数指针
//表示指向的函数类型为:返回值为bool,同时需要两个int参数
void maopao(int a[], int len, bool (*cmp)(int, int))
{
	int i,j;
	int t = 0;

	for (i = 1; i < len; ++i)
	{
		for (j = 0; j < len-1; ++j)
		{
			if (cmp(a[j], a[j+1]))   //注意此处直接调用函数--传参,获得返回值
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
}

int main(void)
{
	int i, a[] = {17,82,37,89,42,76,67,15};
	int len = sizeof(a)/sizeof(a[0]);

	maopao(a,len,Max);   //第3个参数(函数名):为比较方法

	for (i = 0; i < len; ++i)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;

	return 0;
}

//3).引入模板概念,支持多种类型
#include <iostream>
using namespace std;

//比较函数
template<class T>
bool Max(T a, T b)
{
	return a > b;
}

//函数模板
template<class T, class Func>
void maopao(T a[], int len, Func cmp)
{
	int i,j;
	T t;

	for (i = 1; i < len; ++i)
	{
		for (j = 0; j < len-1; ++j)
		{
			if (cmp(a[j], a[j+1]))   //注意此处直接调用函数--传参,获得返回值
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
}
//重载函数模板,默认按从小到大排序
template<class T>
void maopao(T a[], int len)
{
	int i,j;
	T t;

	for (i = 1; i < len; ++i)
	{
		for (j = 0; j < len-1; ++j)
		{
			if (a[j] > a[j+1])  
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
}

int main(void)
{
	int i, a[] = {17,82,37,89,42,76,67,15};
	int len = sizeof(a)/sizeof(a[0]);

//	maopao(a, len);           //默认按照,从小到大排序
	maopao(a,len,Max<int>);   //第3个参数(函数名):为比较方法

	for (i = 0; i < len; ++i)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;

	return 0;
}

//3).修改排序函数,使其符合sort(a, a+10),sort(a, a+10,cmp)模式,同时将冒泡改为快排
//系统的sort()函数有2种重载方式
//1.sort(迭代器1, 迭代器2);
//2.sort(迭代器1, 迭代器2, 谓词方法);
//说明:其实sort()函数所选择的排序方法是比较复杂的,包括(快排,堆排,插入排序).
//并且sort()会根据不同的数据而选择不同的排序方案,我们这里只以快排为例.
#include <iostream>
using namespace std;

//比较函数
template<class T>
bool Max(T a, T b)
{
	return a > b;
}

//函数模板(采用快速排序)
template<class T, class Func>
void Qsort(T *begin, T *end, Func cmp)
{
	T t = *begin;
	T *pL = begin, *pR = (end-1);

	if (pL >= pR)
	{
		return;
	}
	else
	{
		while (pL < pR)
		{
			while (cmp(t, *pR) && pL < pR)  
			{
				--pR;
			}
			*pL = *pR;
			while (cmp(*pL, t) && pL < pR)
			{
				++pL;
			}
			*pR = *pL;
		}
		*pL = t;
	}
	Qsort(pL+1,end,cmp);
	Qsort(begin,pR-1,cmp);
}
//重载函数模板,默认一种排序方案(小到大)
template<class T>
void Qsort(T *begin, T *end)
{
	T t = *begin;
	T *pL = begin, *pR = (end-1);

	if (pL >= pR)
	{
		return;
	}
	else
	{
		while (pL < pR)
		{
			while (t < *pR && pL < pR)  
			{
				--pR;
			}
			*pL = *pR;
			while (*pL <= t && pL < pR)
			{
				++pL;
			}
			*pR = *pL;
		}
		*pL = t;
	}
	Qsort(pL+1,end);
	Qsort(begin,pR-1);
}

int main(void)
{
	int i, a[] = {17,82,37,89,42,76,67,15};
	int len = sizeof(a)/sizeof(a[0]);
//	Qsort(a,a+len);
	Qsort(a,a+len,Max<int>);

	for (i = 0; i < len; ++i)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;

	return 0;
}

泛型编程与C++标准模板库 : 浅谈sort()排序函数,古老的榕树,5-wow.com