以前用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<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;
}第四步:上面几步基本上已经实现了模板库sort()函数的功能了,但是传入的参数好像不对,为此我们再做如下调整改变,同时将冒泡排序替换为快排.
//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()排序函数,布布扣,bubuko.com
原文：http://blog.csdn.net/qingdujun/article/details/38342951