常见数据结构算法总结_数据结构中常用算法有哪些

1、快速排序法

概念：排序速度非常快，采用分治思想

空间复杂度

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(logn)，所以适合在数据集比较大的时候使用。

时间复杂度

时间复杂度比较复杂，最好的情况是O(n)，最差的情况是O(n^2)，所以平时说的O(nlogn)，为其平均时间复杂度

过程：

在一堆数列中选择出一个数作为基准（一般选择最后一个数或者第一个数作为基准），在这个数列中的所有数中，比基准小的排在左边，比基准大的排在右边。这样交换完了之后，左边的数都是比基准小，而右边的数都是比基准大的。这样将一个数组分成了两个子数组，在子数组中再按照同样的方式进行分组，直到不能再分解为止。

具体参考：https://www.cnblogs.com/caidi/p/5922726.html

优点：速度快，省空间 缺点：非常脆弱

2、堆排序

堆排序的时间复杂度O(NlogN),额外空间复杂度O(1),是一个不稳定排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

创建一个堆 H[0…n-1]，升序为大根堆（父节点的数值比子节点的数值都大），降序为小跟堆（父节点的数值比子节点的数值都小）；

把堆首（最大值）和堆尾互换，剩下的数再构成一个新的根堆，再把堆首值与堆尾值互换，不停地重复这一过程，到最后，直到无法交换为止。

3、归并排序

归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

4、二分查找法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。

否则利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表； 否则查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

时间复杂度为O(logN)。

5、BFPRT算法

解决的问题是从n个元素中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。

主要步骤是：1、首先把数组分为每5个元素为一组，不足5个的忽略。对每组进行排序（如插入排序）求取其中的中位数。

2、把上一步的所有中位数移到数组的前面，对这些中位数递归调用BFPRT算法求得他们的中位数。

3、把上一步得到的中位数作为划分的主元进行整个数组的划分。

4、判断第k个数在划分结果的左边、右边还是恰好是划分结果的本身，前两者递归处理，后者直接返回答案。

6、DFS(深度优先搜索算法)

它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都已经被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

步骤：

先访问顶点v；

依次从v的从未被访问的邻接点出发，对图进行深度优先遍历；直到图中和v有路径相通的顶点都被访问；

若此时还有没被访问的顶点，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

我的理解：

先从树的最高顶点出发，选择一个未被访问过的节点，向下进行遍历，一直到遍历完所有的分支。然后又回到上一个节点，查看有没有未被访问过的节点，如果有，继续遍历这一节点的分支，如果没有，则再往上选择节点，重复这些过程，直到最后所有节点均被访问为止。

7、BFS（广度优先搜索）

广度优先搜索算法是一种图形搜索算法。简单来说，BFS始从根节点开始，沿着树的宽度遍历图的节点。如果所有节点均被访问，则算法中止。BFS属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤

首先将根节点放入队列中。

从队列中取出第一个节点，检查是否为目标节点。如果是，直接返回目标。如果不是，将它未经检验过的子节点加入队列中。再从未经检验过的子节点开始搜索，检查是否为目标，如果是就返回目标，如果否，则将这个子节点的未经检验的节点继续放入队列中。不停重复这个过程，直到最后找到目标。若队列为空，表示整张图都已经检查过了，表面图中没有想要搜索的目标了。可以结束并回传“找不到目标”。

8、Dijkstra

迪杰斯特拉(Dijkstra)算法是典型的最短路径算法，用于计算一个节点到其它任意一个节点的最短路径。

它的主要特点是以起始中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。

基本步骤：

1、通过Dijkstra计算最短路径时，需要先指定起点s(即从顶点s开始计算)。

2、此外，需要引进两个集合S和U。S的作用是存放已经找到最短路径的顶点以及相应的最短路径长度，而U是记录还未找到最短路径的顶点以及该顶点到s的距离。

3、初始时，S中只有起点s;U中是除了s之外的起点，并且U中的顶点的路径是起点s到该顶点的路径。然后，再从U中找到路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后再从U中找出路径最短的顶点，并将其加入到S中；接着更新U中的顶点和顶点所对应的路径。重复该操作，直到遍历完所有顶点。

具体看

https://www.cnblogs.com/skywang12345/p/3711512.html

9、冒泡排序

过程：在需要排序的数列中，把相邻的两个元素进行对比，根据元素的大小交换位置，如果第一个比第二个大，那么就交换位置，在这时候最后一个数应该为最大值。再对其它的元素不断重复以上的过程，除了最后一个数。一直到没有任何一对数字要进行比较为止。

时间复杂度：冒泡排序的最好时间复杂度为O(n)

冒泡排序总的平均时间复杂度为O(n^2)

冒泡排序是一种稳定排序算法。

10、直接插入排序

基本方法：假设有两个元素表，一个为有序表，一个为无序表。从无序表中取出一个数插入到有序表中，那么取出来的数会和有序表中的数进行一一对比，插入到适合的位置中，最后构成一个新的有序表。

重点：使用哨兵，用于临时存储和判断数组边界。

直接插入排序的时间复杂度为O(n^2)，直接插入排序是一种稳定的排序方法。

更详细算法分析参考：https://www.jianshu.com/p/7cf0656e76dd

11、鸡尾酒排序

鸡尾酒排序是冒泡排序的升级版，排序适用于大部分元素已经是有序的情况。

冒泡排序的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。算法的每一轮都是从左到右来比较元素，进行单向的位置交换的。

鸡尾酒的排序元素比较和交换是双向的。

算法步骤：

先进行从左到右得比较一轮元素，得到最大值元素位于数组最右边

再从右到左比较元素，大的元素与小的元素交换，这样使大的元素往右移动

再从左到右进行比较元素，看看是否有序，如果没有元素进行交换即证明已经有序，否则继续重复以上过程。

算法是什么？

在计算机领域中，算法是一系列程序指令，用于处理特定的运算和逻辑问题。

衡量算法的优劣的主要标准是时间复杂度和空间复杂度。

什么是数据结构？

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。

那么时间复杂度和空间复杂度又是什么呢？

一、时间复杂度

一般情况下，算法中的基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示,若有某个辅助函数f(n)，使得当n趋于无穷大的时候，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同量级函数，记T(n)=O(f(n))称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。渐进时间复杂度用大写O来表示，所以也被称为大O表示法。时间复杂度主要讨论的是算法执行的次数。

直白地讲，时间复杂度就是把时间规模函数T(n)简化为一个数量级，这个数量级可以是n,n^2,n3等等。

那么该如何推导出时间复杂度呢？有以下几个原则：

如果运行时间是常数量级，用常数1表示；

只保留时间函数中的最高阶项；

如果最高阶项存在，则省去最高阶项前面的系数。

递归算法的时间复杂度==递归总次数*每次递归的次数

常见的时间复杂度按照从低到高顺序，包括O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。

二、空间复杂度

空间复杂度是对一个算法在运行中临时占用存储空间大小的量度，它同样使用了大O表示法，计算公式为S(n)=O(f(n))，n为问题的规模，f(n)为算法所占存储空间的函数。

空间复杂度：即程序中变量的个数

空间复杂度==递归的深度（即树的高度）

常见的空间复杂度按照从低到高的排序，包括O(1)、O(n)、O(n^2)等。其中递归算法的空间复杂度和递归深度成正比。