首页 > 代码库 > 泛型编程与C++标准模板库 : 浅谈sort()排序函数
泛型编程与C++标准模板库 : 浅谈sort()排序函数
以前用sort排序的时候,只知道sort函数有如下两种重载方式.
- template< class RandomIt > void sort( RandomIt first, RandomIt last );
- 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; }
第二步:用冒泡排序,模拟sort()函数的两种重载方式,第二种重载方式明显要引入函数指针.
//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; }
原文地址:http://blog.csdn.net/qingdujun/article/details/38342951
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。