【数据】数据结构，查询排序算法思维导图模板

数据结构

一维线性结构

顺序表

顺序表可以实现下标的快速访问

顺序表在中间或者头部插入节点和删除节点必须依次挪动节点

顺序表每次增容固定大小的空间有可能造成空间浪费，但不用每次插入时都动态开辟空间

队列

先进先出

应用

排队问题

事件驱动

堆栈

先进后出

应用

历史记录

括号匹配问题

压栈调用

链表

单链表

定义

链表（Linked List）是通过指针连接起来的一系列节点，每个节点有自身数据，然后指向下一个节点，形成一条数据链。

单链表每次插入节点时都必须动态开辟空间、删除节点时必须释放掉动态开辟的空间

动态结构：内存空间可以动态申请，适合不确定数据量的场景。

查询慢，插入快

查询

单链表必须从头依次遍历查找，时间复杂度为O(n)

插入

在单链表中，一旦定位好要插入的位置，插入结点的时间复杂度是很低的，就是 O(1)。

删除

删除节点快，时间复杂度为O(1)

应用

花名册录入

适合不确定数据量的场景。

升级循环单项链表

循环单项链表

双向链表

定义

双向链表（Doubly Linked List） 是一种链式存储结构，它与单向链表不同之处在于：每个节点（Node）除了存储数据（data）外，有两个指针指向前后

特点

一个节点通常包含三个部分

+-----------+       +-----------+       +-----------+ |   prev    |  <--> |   data    |  <--> |   next    | +-----------+       +-----------+       +-----------+

节点可以向前查找，向后查找

插入操作

(1) 在头部插入

(2) 在尾部插入

查询

查找操作从头节点开始遍历，直到找到目标节点或遍历完链表。

应用

升级循环双向链表

回顾回述问题

循环双向链表

跳表

定义

跳表其实是一种多层的有序的链表。跳表来源于链表，在链表的基础上结合了二分的思想进行改造形成了 k 层子链表作为索引。

特点

跳表的做法就是给链表做索引，而且是分层索引。第一层索引是n/2个，第二层的索引是n/4个，第三层索引是n/8个，即每隔两个数据就记下个索引

索引对象记录了三个数据，一个是要比对的数据值，一个是索引的下个索引，还有就是索引下层的索引或链表。

最底层的链表包含所有元素；如果一个元素出现在第i层的链表中，则它在第i层之下的链表也都会出现；

跳表是需要建立索引的，大概建立n个索引，是用空间换时间的典型算法，只不过跳表所需要的空间不是链表中存储的数据对象。

查询

那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4

也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2的k次方)。

查询的时间平均复杂度为 logn

插入

高效的动态插入，而且插入操作的时间复杂度也是 O(logn)。

对于纯粹的单链表，有序需要遍历每个结点，来找到插入的位置。复杂度会达到O(n)

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。而我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K

删除操作

如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。

因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。

常见问题

跳表是不是很浪费内存？

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。如果我们把每层索引的结点数写出来是一个等比数列。这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值   几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表本质强调

跳表的本质是一个多层的有序链表，同时结合了二分和链表的思想；

由很多层索引组成，每一层索引是通过随机函数随机产生的，每一层都是一个有序的链表，默认是升序；

二维树状结构

HashMap

结构

哈希表首先定义链结点Node。其中Node有三个属性，一个是key，一个value，还有一个是对应链表的point

连续空间中顺序键值对-->链表

特点

信息压缩

插入快速

hash碰撞

范围查询难

排序难

平衡二叉树

结构

左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

特点

插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)

树的深度高了以后，回述和查询效率大大下降

AVL树

结构

由于二叉搜索树在最坏的情况下（顺序写入）会退化成链表，搜索时的时间复杂度高

这里AVL树在节点进行插入、删除、修改的时候进行了自平衡，让整棵树不至于过于倾斜

树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

 某结点的左子树与右子树的高度（深度）差即为该结点的平衡因子（BF、Balance Factor）

图示

右边二叉树中节点值为10的左右子树高度差为2

自平衡手段

如果插入新节点时发现左右子树的平衡因子的绝对值大于2，通过LL、LR、RR、RL的操作保证平衡因子的绝对值小于等于1

特点

AVL树由于自平衡的存在，使得树的高度不会太高，平均搜索的时间复杂度为O(logN)

树的高度较高，需要多次IO操作

B树

结构

B树属于多叉树又名平衡多路查找树

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则

子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉树）

特点

每个节点包含的关键字增多了，在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理

树的节点关键字增多后，树的层级比原来的二叉树少了，减少数据查找的时间复杂度

B+树

结构

B+树是B树的一个升级版

B+树的非叶子节点不保存关键字记录的指针，只进行数据索引

B+树叶子节点保存了父节点的所有关键字记录的指针

B+树叶子节点的关键字从小到大有序排列，相互双向指针

特点

B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多

B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表

B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可

B*树

结构

B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3*m)）

每个节点都有指向兄弟的指针

特点

节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少

总结各种数据结构

前面讲述了大量的数据结构，最后发现B树和B+树是较为合理的，可以作为索引底层的数据结构

评价数据结构是否适合作为索引的标准就是查询数据时磁盘IO的次数，因为磁盘IO的速度比起内存IO要慢上几个数量级

由于B树在非叶子节点同时存储数据和关键字，造成一个节点能够存储的数据个数不会太多，那么B树的高度就会比较高，磁盘IO的次数就会较多

B+树非叶子节点只存储关键字，因此能够存储的关键字更多，B+树的高度就不会太高，一般为3 ~ 4层。因此B+树的高度比B树低，磁盘IO次数更少

综上所述B+树更适合作为索引底层的数据结构

高维图结构

HNSW 

HNSW (Hierarchical Navigable Small World) 索引是一种高效的近似最近邻 (Approximate Nearest Neighbor, ANN) 搜索算法

它主要用于大规模数据集中的高效查询。HNSW 索引的核心原理基于图论和小世界网络（Small World Network）的概念。

构建过程：

初始化：首先，对数据点进行排序，然后选择一个固定大小的邻居窗口，将每个数据点与其邻居连接起来，形成一个初始的邻接列表。 构建层次结构：递归地将这个邻接列表扩展为多层，每一层包含更远的邻居。相邻层之间的节点通过随机重采样连接，形成小世界结构。 添加新节点：当有新数据加入时，会根据其与现有节点的距离插入到适当的层次中，并调整邻接关系。

搜索过程：

查询：对于一个查询点，从根节点开始，沿着层次结构向下搜索，找到最接近的邻居节点。搜索过程中，如果遇到分支点，会优先考虑距离更近的分支。

扩散策略：为了提高搜索精度，HNSW 使用扩散策略，即从当前节点开始，不仅查看直接邻居，还会查看其邻居的邻居，直到达到预设的深度或找到足够数量的候选结果。

优点： 高效：HNSW 在处理大规模数据时非常高效，因为它使用了局部性原理，即相似的数据点在图中通常很接近。 可扩展性：可以动态添加和删除数据，而无需重建整个索引。 内存效率：由于采用了小世界结构，HNSW 可以在内存有限的情况下处理大量数据。

缺点： 精度与空间复杂度：随着图的层数增加，精度提高但空间复杂度也增大。需要权衡搜索精度和内存使用。 不适合高维数据：对于高维数据，HNSW 的性能可能会下降，因为高维空间中的“近似”可能不直观。

排序问题

冒泡排序

冒泡排序算法基础

算法原理

比较相邻元素

如果顺序错误则交换

逐轮减少比较范围

每轮确定一个最大值

时间复杂度分析

最坏情况时间复杂度

O(n^2)

平均情况时间复杂度

O(n^2)

空间复杂度分析

辅助空间需求

常数级空间O(1)

原地排序特性

不需要额外数组

稳定性分析

相同元素相对位置不变

稳定排序算法

冒泡排序的实现

基本实现步骤

循环遍历数组

外层循环控制轮数

内层循环比较交换

相邻元素比较

代码示例

Python实现

def bubble_sort_recursion(self, array=None):         """         # every loop block to find a max object by comparing one by one.         # then using recursion to sort remaining raw_array[0:n-1].         """         n = len(array)         if n < 2:             return array         # using the for loop to find the max number index.         for i in range(0, len(array) - 1):             if array[i] > array[i + 1]:                 temp = array[i]                 array[i] = array[i + 1]                 array[i + 1] = temp         return self.bubble_sort_recursion(array[0:n-1]) + [array[n-1]]

优化策略

标志位优化

提前结束排序

鸡尾酒排序（双向冒泡）

从两端向中间遍历

选择排序

选择排序算法

算法原理

每次找到最小的元素

时间复杂度

平均情况时间复杂度

O(n^2)

选择排序实现

代码示例

python实现

def selected_sort(self, array=None):         """         # every loop block to find a min object, and then to exchange to the first position.         # opt: in one loop to find the min and max object at same time.         """         if array:             self.raw_array = array         for j in range(0, len(self.raw_array) - 1):  # n-1 times loop.             temp = self.raw_array[j]             for ii in range(j + 1, len(self.raw_array)):                 if temp > self.raw_array[ii]:                     temp = self.raw_array[ii]                     self.raw_array[ii] = self.raw_array[j]                     self.raw_array[j] = temp         return self.raw_array

优化策略

同时找到最大最小

def selected_sort_opt(self, array=None):         """         # every loop block to find a min index and max index,         # and then to exchange to the first and last position.         """         if array:             self.raw_array = array         n = len(self.raw_array)         i_left = 0         i_right = n - 1         while i_left < i_right:             index_min, index_max = i_left, i_left             # find the min and max index in one loop from the left to right.             for i in range(i_left, i_right + 1):                 if self.raw_array[index_min] > self.raw_array[i]:                     index_min = i                 if self.raw_array[index_max] < self.raw_array[i]:                     index_max = i             # judge the min and max mun in one loop, and then to exchange the position.             if index_min != i_left:                 tl = self.raw_array[i_left]                 self.raw_array[i_left] = self.raw_array[index_min]                 self.raw_array[index_min] = tl             if index_max == i_left:                 index_max = index_min             if index_max != i_right:                 tr = self.raw_array[i_right]                 self.raw_array[i_right] = self.raw_array[index_max]                 self.raw_array[index_max] = tr             i_left = i_left + 1             i_right = i_right - 1         return self.raw_array

快速排序

快速排序算法

通过标点元素pivot和2个分大小list完成自迭代

一次迭代把元素分到不同的list里

快速排序算法实现

代码案例

python实现

def quick_sort(self, array=None):         """         # using the first element to be the pivot.         # using the left and right pointer to compare the element.         # opt: using the random element to be the pivot.         """         if array is None:             array = self.raw_array         n = len(array)         if n < 2:             return array         # using the first element to be the pivot.         pivot = array[0]         left = list()         right = list()         for i in range(1, n):             if array[i] < pivot:                 left.append(array[i])             else:                 right.append(array[i])         # using recursion to sort the left and right array.         left = self.quick_sort(array=left)         right = self.quick_sort(array=right)         return left + [pivot] + right

优化策略

随机选取标杆point

def quick_sort_opt(self, array=None):         """         # using the random element to be the pivot.         # using the left and right pointer to compare the element.         """         if array is None:             array = self.raw_array         n = len(array)         if n < 2:             return array         # using the random element to be the pivot.         pivot = array[random.randint(0, n - 1)]         left = list()         right = list()         for i in range(0, n):             if array[i] < pivot:                 left.append(array[i])             else:                 right.append(array[i])         # using recursion to sort the left and right array.         left = self.quick_sort(array=left)         right = self.quick_sort(array=right)         return left + right

希尔排序

堆排序

存储问题

检索问题

顺序查找

二分法查找

聊聊精排

“精排”或精细化排序，在数据库查询和搜索场景下，通常表示对搜索结果的一种高级筛选和排序策略

条件限制

权重计算（依据用户喜好、评分等因素）

更加复杂的算法以提供满足用户特定偏好结果的排序方式，动态调整结果权重、相关度排名等。

“索引能力”在此过程中至关重要，因为良好的索引能够显著提高查找的速度，减少搜索结果的计算成本