首页 > 代码库 > 数据结构之简单排序的三种玩法
数据结构之简单排序的三种玩法
本文主要介绍,一个简单排序算法都可以有哪几种玩法(以选择排序为例,代码请在cpp文件下运行)
选择排序...总结为三个步骤就是:
1.在一段区间内找最大/最小元素.
2.将最大/最小元素与区间中的第一个值进行交换
3.缩小查找区间
如果你还没有理解?不用担心,请参考:选择排序_百度百科:http://baike.baidu.com/item/选择排序
玩法1:初窥门径
如果理解了选择排序的算法,想要把它实现成一段代码,对于代码能力比较强的小伙伴来说,并不是一件复杂的事情,因此我们达到的第一重境界就是这样:
//选择排序简单实例(升序) void SelectSort(int arr[],size_t sz){ for(size_t i=0; i<sz; ++i){ //缩小对查找区间 int temp = arr[i]; //记录最小/最大值 size_t pos = i; //记录最大/最小值的位置 for(size_t j=i+1; j<sz; ++j){ //在(i,sz)区间内寻找最大/最小的值 if(temp>arr[j]){ temp = arr[j]; //更新最大/最小值 pos = j; //更新最大/最小值得位置 } } arr[pos] = arr[i]; //将区间内最大/最小值与i进行交换 arr[i] = temp; } }
我们能够写出这样的代码,就说明我们的代码功底已经进入了入门的境界.
但这种代码存在这样的问题:
1.只能对特定类型元素,进行排序.(本例为整型)
2.只能进行升序或降序.(本例为升序,如果想实现降序,还得再写一段代码)
玩法2:略有所成
如果有了解函数指针的同学,并能熟练应用回调函数上,那么就可以写出这样的代码:
//回调函数,升序控制 bool Asc(int left,int right){ return left>right; } //回调函数,降序控制 bool Desc(int left,int right){ return left<right; } typedef bool(*CallBack)(int,int); //选择排序简单实例(升序) void SelectSort(int arr[],size_t sz,CallBack compare ){ for(size_t i=0; i<sz; ++i){ //缩小对查找区间 int temp = arr[i]; //记录最小/最大值 size_t pos = i; //记录最大/最小值的位置 for(size_t j=i+1; j<sz; ++j){ //在(i,sz)区间内寻找最大/最小的值 if(compare(temp,arr[j])){ //使用回调函数,控制升/降序 temp = arr[j]; //更新最大/最小值 pos = j; //更新最大/最小值得位置 } } arr[pos] = arr[i]; //将区间内最大/最小值与i进行交换 arr[i] = temp; } }
这样的话,我们可以通过回调函数来控制选择排序的升降序.
但这样的代码,仍然不具备有通用性,因为只能对整型进行排序
玩法3:登堂入室
C++里面有一个可以增强代码复用型的新特性:模板!
STL的六大组件中,有一个组件叫做:函数对象.
因此,第三种境界,我们可以把模板和函数对象结合起来,于是便写出了这样的代码:
//升序排列 template<typename T> class ASC{ public: bool operator()(T left,T right){ return left>right; } }; //降序排列 template<typename T> class DESC{ public: bool operator()(T left,T right){ return left<right; } }; //选择排序 template<typename T,typename Com> void SelectSort(T arr[],size_t sz){ for(size_t i=0; i<sz; ++i){ //缩小对查找区间 int temp = arr[i]; //记录最小/最大值 size_t pos = i; //记录最大/最小值的位置 for(size_t j=i+1; j<sz; ++j){ //在(i,sz)区间内寻找最大/最小的值 if(Com()(temp,arr[j])){ //使用对象函数,控制升/降序 temp = arr[j]; //更新最大/最小值 pos = j; //更新最大/最小值得位置 } } arr[pos] = arr[i]; //将区间内最大/最小值与i进行交换 arr[i] = temp; } }
这样的代码,复用性及通用性又得到了极大的提升!
总结:学海无涯,继续努力!
数据结构之简单排序的三种玩法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。