title: 范型編程_排序
date: 2016-05-02 12:05:57
categories: 算法 #文章文類
tags: [范型編程,STL,Geekband]
sort
- 對(duì)區(qū)域內(nèi)元素進(jìn)行從小到大排序
- 使得 it1 < it2 ,滿足(it1) < (it2)
- 對(duì)象必須提供operator<
partial_sort
- 區(qū)域[_First,Mid)元素是從小到大有序排列
- 區(qū)域(Mid,_Last)是未定義的
binary_search
- 在區(qū)域內(nèi)查找==_Val的元素
- 容器中的元素首先要排序, 如果不先排序,那么使用binary_search將永遠(yuǎn)找不到
e.g
v[] = {1,2,3,10,5}
baniry_search(v.begin(), v.end(), 5)
這里將會(huì)返回false
merge
- 將 <font color=red>排好序的</font> 區(qū)域1和區(qū)域2合并到_Dest中
- 一定要注意是先排序
基于排序集合的一些算法
- includes
- set_union
- set_intersection
- set_differrence
includes
- 判斷區(qū)域1內(nèi)是否包含區(qū)域2
- **區(qū)域1,區(qū)域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中一種標(biāo)準(zhǔn)關(guān)聯(lián)容器（vector,list,string,deque都是序列容器歪沃，而set垃瞧，multiset类咧，map余耽，multimap是標(biāo)準(zhǔn)關(guān)聯(lián)容器）坠陈，它底層使用平衡的搜索樹——紅黑樹實(shí)現(xiàn)，插入刪除操作時(shí)僅僅需要指針操作節(jié)點(diǎn)即可完成辜羊，不涉及到內(nèi)存移動(dòng)和拷貝蝗肪，所以效率比較高。
- 在set中元素都是唯一的贰谣。
- 默認(rèn)情況下會(huì)對(duì)元素自動(dòng)進(jìn)行升序排列顶燕。
- 集合的交(set_intersection)
- 差(set_difference)
- 并(set_union)
- 對(duì)稱差(set_symmetric_difference)
基于堆的算法
- make_heap
- push_heap
- pop_heap
- sort_heap
make_heap
- 將區(qū)域轉(zhuǎn)換成一個(gè)堆
- 對(duì)結(jié)構(gòu)采用max_heap,維持平衡二叉樹
v[]={1,4,200,8,100,5,7}
mak_heap(v,v+7)
mak_heap
push_heap
- 向堆內(nèi)添加元素
- 算法假設(shè)區(qū)域已經(jīng)是一個(gè)堆
- 堆結(jié)構(gòu)采用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()) //加入的是最后一個(gè)元素'95'
-
make_heap后
2.實(shí)現(xiàn)流程
pop_heap
- 從堆中彈出根頂元素
- 算法假設(shè)容器已經(jīng)是個(gè)堆
- 堆結(jié)構(gòu)采用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()) //加入的是最后一個(gè)元素'95'
-
make_heap后
pop_heap實(shí)現(xiàn)流程
sort_heap
- 把堆中的元素進(jìn)行排序
- 對(duì)結(jié)構(gòu)采用max_heap,維持平衡二叉樹
- Sort做法實(shí)際就是不斷pop_heap
