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

?

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

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 .

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

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

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

?

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

?

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

?

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

//1).简单的冒泡排序
#include 
  
   
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<
   
     第二步:用冒泡排序,模拟sort()函数的两种重载方式,第二种重载方式明显要引入函数指针.
    
?
    
?
    
//2).引入函数指针
#include 
     
      
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<
      
       第三步:将上述代码,模板化,使其能支持多种类型的数据排序.
       
?
       
?
       
//3).引入模板概念,支持多种类型
#include 
        
         
using namespace std;

//比较函数
template
         
           bool Max(T a, T b) { return a > b; } //函数模板 template
          
            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
           
             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
            
             ); //第3个参数(函数名):为比较方法 for (i = 0; i < len; ++i) { cout<
             
              第四步:上面几步基本上已经实现了模板库sort()函数的功能了,但是传入的参数好像不对,为此我们再做如下调整改变,同时将冒泡排序替换为快排.
              
?
              
?
              
//3).修改排序函数,使其符合sort(a, a+10),sort(a, a+10,cmp)模式,同时将冒泡改为快排
//系统的sort()函数有2种重载方式
//1.sort(迭代器1, 迭代器2);
//2.sort(迭代器1, 迭代器2, 谓词方法);
//说明:其实sort()函数所选择的排序方法是比较复杂的,包括(快排,堆排,插入排序).
//并且sort()会根据不同的数据而选择不同的排序方案,我们这里只以快排为例.
#include 
               
                
using namespace std;

//比较函数
template
                
                  bool Max(T a, T b) { return a > b; } //函数模板(采用快速排序) template
                 
                   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
                  
                    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
                   
                    ); for (i = 0; i < len; ++i) { cout<
                    
                     
?