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}
make_heap(v,v+(v.size()-1), v+v.size()) //加入的是最后一个元素'95'
-
make_heap后
pop_heap实现流程
sort_heap
- 把堆中的元素进行排序
- 对结构采用max_heap,维持平衡二叉树
- Sort做法实际就是不断pop_heap
