排序篇

冒泡排序

算法思想：在每次遍历的时候从头到尾比较两个相邻元素大小，将较小的元素“冒”到前面来，最大的元素移向队尾，使元素变得有序。（从小到大排序，若从大到小则相反）参考算法代码

选择排序

算法思想：每一趟从待排序的数据元素中选出最小（大）的一个元素放在已拍好的数列最后。参考算法代码

插入排序

算法思想：每步将一个待排序的记录按其排序的码值大小插到前面已经排好的位置，知道全部插入完为止。参考算法代码

快速排序

算法思想：通过一趟排序将要排序的数据分割成独立的两部分，一部分小于另一部分，然后对两部分再实施快速排序，如此递归进行。参考算法代码

希尔排序

算法思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。

子序列不是被简单的“逐段分割”，而是将相距某个“增量”的记录组成一个子序列，希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。

参考算法代码

堆排序

堆排序的详细介绍链接

参考算法代码

二分法查找

二分法查找的前提是记录已经是有序的。参考算法代码

各个排序算法的时间空间复杂度如下图

树篇

平衡二叉树

AVL树是带有平衡条件的二叉树，这个平衡条件必须容易保持，而且必须保证树的深度是O(logN)。最简单的想法是要求左右子树具有相同的高度。另一种平衡条件是要求每个节点都必须具有相同的左子树和右子树。一颗AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

平衡二叉树的优点

二叉排序树是一种比较有用的折中方案。数组的搜索比较方便，可以直接使用下标，但删除和插入元素比较麻烦。链表，删除和插入元素很快，但查找很慢。二叉排序树既有数组的好处也有链表的好处，只吃动态的插入和查找。如果输入集合确定，所需要的就是查询，可以考虑使用哈希表，如果输入集合不确定，则考虑平衡二叉树\红黑树，保证达到最大效率。

平衡二叉树的主要优点集中在快速查找。

红黑树

红黑树是一种自平衡二叉查找树。红黑树和AVL树一样，可以在O（logN）时间内做查找、插入和删除。红黑树的统计性能要优于平衡二叉树。红黑树并不追求完全平衡-它只要求部分地达到平衡要求，降低了对旋转的要求。若数据是完全静态的，做一个哈希表，性能会更好。

其中set，multiset，map，multimap是一种非线性的树结构，具体的说是采用一种比较高效的特殊的平衡检索二叉树--红黑树结构。

STL

Map & MultiMap

count(const KEY_TYPE &key);返回指定元素出现的次数；
find(const KEY_TYPE &key);查找等于key值得元素，并返回指向该元素的迭代器，如果没有找到，返回指向集合最后一个元素的迭代器；
insert(input_iterator start , input_iterator end);插入start到end的元素到map中；
rbegin()返回一个指向map尾部的逆向迭代器；
rend()返回一个指向map头部的逆向迭代器；
swap()交换两个map，如void swap(map & obj);交换obj和现map中的元素；
void erase(iterator i);删除i元素；void erase(interator start , iterator end);删除从start到end（不包括end）的元素；size_type erase( const key_type &key);删除等于key值得所有元素（返回被删除元素的个数）；

Set & MultiSet的用法与Map & Multimap类似，只是集合特点不一样。

关联容器Set和Map主要特点

其内部实现是采用非线性的红黑树的结构原理；
set和map保证了元素的唯一性，multiset和multimap扩展了这一属性；
元素是有序的集合，默认在插入的时候按升序排列；

可以用greater<>来改变成降序排列

基于以上特点，

关联容器对元素的插入和删除操作比vector要快，因为vector是顺序存储，而关联容器是链式存储；比list要慢，因为即使他们都是链式结构，但list是线性的，而关联容器是红黑树结构，其改变一个元素涉及到其它元素的变动比list要多，并且它们是排序的，每次插入和删除都需要对元素重新排序。
关联容器对元素的检索操作比vector慢，但比list要快很多。vector是顺序的连续存储，当然比不上的，但相对于链式的list快很多是因为list是逐个搜索，它的搜索时间跟容器的大小成正比。而关联容器查找的复杂度基本是Log（N），比如有1000个记录，最多查找10次，有100000个记录最多查找20次。容器越大，关联容器相对于list的优越性就越能体现。
在使用上set区别于vector，deque，list的最大特点是set是内部排序的，这在查询上虽然逊色vector，但是却大大的强于list。

vector，list，deque三者比较

vector是一段连续的内存块，而deque是多个连续的内存块，list是所有数据元素分开保存，可以是任何两个元素没有连续。

vector的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效的随机存储。
list是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素的性能是最好的，而查询性能非常差；适合大量的插入和删除操作而不关心随机存取的需求。
deque是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有比list好的查询性能，也有比vector好的插入、删除性能。如果需要随即存取又关心两端数据的插入和删除，那么deque是最佳之选。

cccreator / cc

7.数据结构与STL #9

排序篇