基本的C++算法有哪些？开课吧广场

众所周知想要成为C++开发工程师，需要掌握的知识有很多，这不仅包括数据类型、数据结构、数据变量的信息，还需要了解一定的算法信息。那么基本的C++算法有哪些？

基本的C++算法有哪些？开课吧广场

基本的C++算法分为三类：排序算法、树算法、图算法。算法思想有三种：递推、分治、动态规划 以及 贪心算法。

排序算法：（对基本排序算法的时间复杂度分析主要考虑 比较次数、数据交换次数）。

冒泡排序：针对数组、本地排序、需要交换数据。O(1)额外空间。

选择排序：一般针对数组、本地排序、需要交换数据。O(1)的额外空间。

插入排序：可以是针对数组的本地排序，此时需要移动大片数据，但是比较次数是O(N*logN)。如果是针对链表，比较次数是O(N^2)，但是不需要交换数据。

注意：一般排序都是针对数组的本地排序，数组与链表相比，可以随机访问，空间使用效率更高（链表需要存放指针），而链表一般对于插入与删除操作有更好的性能。

基本的C++算法有哪些？开课吧广场

树的算法：树一般用链表实现，通常用树的数据结构实现数据的快速插入、删除、查找。

1、平衡二叉查找树。RB-Tree、 AVL、 Treap、 伸展树（无需存放额外信息）。

2、B树。用于建立文件系统或数据库的索引。B树的设计目标是减少IO访问次数。B树也是一棵平衡树。

3、二项树、二项堆、费波那奇堆。

图的算法：

1、图的表示。有向图、无向图 的 邻接表表示、矩阵表示。

2、广度优先搜索、深度优先搜索。

3、最小生成树。针对无向连通图的，常见的算法有 Kruskal算法和Prim算法。

4、最短路径。有权值的最短路径问题。可以是有向图，可以是无向图。权值可以为负值。

5、求所有点之间的最短路径。矩阵上的动态规划算法。