范型编程_排序

2016-05-04 本文已影响34人 alamu

title: 范型编程_排序
date: 2016-05-02 12:05:57
categories: 算法 #文章文类
tags: [范型编程,STL,Geekband]

sort

对区域内元素进行从小到大排序
使得 it1 < it2 ,满足(it1) < (it2)
对象必须提供operator<

partial_sort

区域[_First,Mid)元素是从小到大有序排列
区域(Mid,_Last)是未定义的

binary_search

在区域内查找==_Val的元素
容器中的元素首先要排序, 如果不先排序,那么使用binary_search将永远找不到

e.g  
v[] = {1,2,3,10,5} 
baniry_search(v.begin(), v.end(), 5) 
这里将会返回false

merge

将 <font color=red>排好序的</font> 区域1和区域2合并到_Dest中
一定要注意是先排序

基于排序集合的一些算法

includes
set_union
set_intersection
set_differrence

includes

判断区域1内是否包含区域2
**区域1,区域2都是排好序的
包含则返回true

e.g
v1[]={1,2,3,4,5,6,7}
v2[]={1,4,6}
includes(v1.begin(),v1.end(),v2.begin(),v2.end()) 返回true

v1[]={1,2,3,4,5,6,7}
v2[]={4,9}
includes(v1.begin(),v1.end(),v2.begin(),v2.end()) 返回false

集合算法

set是STL中一种标准关联容器（vector,list,string,deque都是序列容器，而set，multiset，map，multimap是标准关联容器），它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。

在set中元素都是唯一的。
默认情况下会对元素自动进行升序排列。

集合的交(set_intersection)
差(set_difference)
并(set_union)
对称差(set_symmetric_difference)

基于堆的算法

make_heap
push_heap
pop_heap
sort_heap

make_heap

将区域转换成一个堆
对结构采用max_heap,维持平衡二叉树

v[]={1,4,200,8,100,5,7}
mak_heap(v,v+7)

mak_heap

push_heap

向堆内添加元素
算法假设区域已经是一个堆
堆结构采用max_heap,维持平衡二叉树

e.g
v[]={100,90,99,70,80,30,45,20,35,10,95}

make_heap(v,v+(v.size()-1), v+v.size()) //加入的是最后一个元素'95'

make_heap后

2.实现流程

pop_heap

从堆中弹出根顶元素
算法假设容器已经是个堆
堆结构采用max_heap,维持平衡二叉树

e.g
v[]={100,90,99,70, 25,30,45,20,35,10,95}