数据结构详细解析与代码实现

在进行算法分析时，语句的执行总次数T(n)是关于时间规模n的函数，进而分析T(n)随n的变化情况确定T(n)。T(n)=O(f(n))，问题规模n的增大，是否的执行时间的增长率和f(n)相同。

常数阶

for循环内时间复杂度为O(1)

线性阶

对数阶

O表示法保留O(n^2)

平方阶

各时间复杂度耗时依此从小到大

O

一般情况我们讨论的运行时间是最坏情况的运行时间，也就是不会再差了

时间复杂度

ai是ai+1的直接前驱，ai+1是ai的直接后继

长度为0是称为空表

若线性表表示为

定义

相邻两个元素的地址也是相邻的

伪代码

时间复杂度O(n)

插入

删除

操作

顺序存储

通过指针将各个部分联系起来

头指针与头结点

所有节点都只有一个Next指针指向下一个，没有pre指针指向上一个

首先要找到A（C插入后的直接前驱），有指针指向A，这个指针称为cur。现实情况A不一定是第一个节点

然后C.Next指向cur（确实就是A）的Next

最后cur（也就是A）的Next指向C

插入C

find cur

C.Next = cur.Next

cur.Next = C

顺序不能错

首先还是找到A（C的直接前驱），用cur指针指向A

用一个temp指针保存C

其次，cur的Next指针指向C的Next

其实上一步就结束了，看情况看C的Next指针要不要指向空

删除C

单链表

循环链表

空表

带头结点的双向链表

每个节点既有指向上一个节点的指针也有指向下一个节点的指针

首先找到A（C插入位置的前一个节点）

C.Next = cur.Next (C的Next指向B)， C.Pre = cur (C的Pre指向A)

C.Pre.Next = C (A的Next指向C)      C.Next.Pre = C (B的pre指向C)  

往A后面插入C

方法不唯一

第一步找到C

cur.Next.Pre = cur.Pre (B的Next指向A)  cur.Pre.Next = cur.Next (A的Next指向B)

C的pre和Next看情况是否置空

双链表

链式存储

实现

单链表与顺序存储的优缺点

差分数组

21. 合并两个有序链表

19. 删除链表的倒数第 N 个结点

23. 合并K个升序链表

141. 环形链表

LeetCode推荐

线性表

FILO：后进先出

API

golang实现

顺序存储实现

链式存储实现

递归

使用

栈

队列只允许一端进行插入操作，另一端进行删除操作的线性表

接口

队列

TODO

单调栈\\单调队列

循环队列

https://leetcode.cn/problems/valid-parentheses/

20. 有效的括号

232. 用栈实现队列

225. 用队列实现栈

https://leetcode.cn/problems/n-queens/

51. N 皇后

栈与队列

字符串

KMP

串

字典树Trie

线段树Segment Tree

红黑树 Red -Black Tree

二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点

如果 key 大于根节点，则在右子树中进行查找；

如果 key 小于根节点，则在左子树中进行查找；

如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。

查找key

当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)

特殊场景

插入key

二分查找树

为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。

每个节点的左子树和右子树的高度差不能超过 1

自平衡二叉树

为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。

B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。

假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点

查询过程，查找0009

B树

MySQL 中索引的数据结构就是采用了 B+ 树

叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；

所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；

非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。

B+树与B树的区别

B+树

堆是一棵完全二叉树

所有节点的值都大于它的左子节点和右子节点

采用数组的方式实现大顶堆，位置k的左子树所在的位置为2*k+1，右子树是2*k+2

大顶堆

所有节点的值都小于它的左子节点和右子节点

小顶堆

堆

树

邻接矩阵

最短路径

图

时间复杂度 O(logn)

二分查找

并查集Union-Find

跳表

查找

序列里有两个相同的值，一个在前称为a，一个在后称为b，排完序后a还是在b的前面，该排序算法称为稳定的。如果不能保证a一定在b的前面，该排序算法称为不稳定

稳定性

整个排序的过程中都是在内存进行

内排序

排序的数据集太大，内存放不下，需要内存和外存进行多次数据交换

外排序

内排序与外排序

交换数组第i和第j个元素

二进制表示时，同一位相同异或结果为0，不同结果为1

这两个二进制数的异或结果为0111

00010110

0^任何数=任何数

两个相同的数异或等于0

^是异或

交换数组第i和第j个元素，仅限整型且i不等于j

排序会用到的方法

前言

各个排序可视化

想知道自己排序算法对不对做这道题

是一种交换排序，凉凉比较相邻记录的关键字，如果反序则交换，正序则跳过，直到没有反序为止

思想

相当于第一趟确认最大值，第二趟确认第二大的值，第i趟确认第i大的值

这里其实也可以写成j < len(nums)，但没必要，因为在做无用功，这一部分已经排好序了

外层第i次循环我习惯称为第i趟，每一趟都会确认一个剩下数据中的最大值。

图中绿色部分表示已经排好序

新增一个标签，判断当前数据是否已经有序

优化

复杂度O(n^2)

比较次数

数列有序的情况下复杂度为O(n)

最好情况的时间复杂度

O(1)

空间复杂度

冒泡排序

简单来说就是每次取剩余值中的最小值放到前面。

O(n^2)

简单选择排序

为了避免多次交换，一般而言都是找到位置后，位置之后的数据向后移动一位，再把当前数据放进去

当前在排的节点一个一个向前比较，直到找到自己的位置

图解

func InsertSort(nums []int) []int { for i := range nums {  pos := 0//保存当前在排序的数字插入点  //这段代码可换成二分查找，因为前面部分是有序的  for j := i - 1; j >= 0; j-- {   if nums[j] < nums[i] {    //到达指定位置    pos = j + 1    break   }  }  if pos == i {   continue  }  tmp := nums[i]//保存当前在排序的值，避免被覆盖  for k := i; k >= pos; k-- {   nums[k] = nums[k-1]  }  nums[pos] = tmp } return nums}

最大比较次数

最大移动次数

数列有序的情况下O(n)

一般而言，少量的数据无序的情况下直接插入排序的性能很优秀

最好情况下的时间复杂度

直接插入排序

使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组

换句话，将h个有序的数组交织在一起组成的一个数组

通过将数组不断变为h有序（h从大到小直到1），当h=1时，整个数组就有序了

注：最后一个增量必须是1

func ShellSort(nums []int) []int { increment := len(nums) for {  increment = increment / 3 + 1  for i := 0; i < increment; i++ {   for j := i + increment; j < len(nums); j += increment {    tmp := nums[j]    //pos记录tmp即将插入的位置    pos := j    for k := j - increment; k >= 0; k -= increment {     if nums[k] > nums[j] {      pos = k     }else{      break     }    }    if pos == j {     continue    }    //类似插入排序，大于tmp的元素后移increment位，为了给tmp腾位置    for k := j; k > pos; k -= increment {     nums[k] = nums[k - increment]    }    nums[pos] = tmp   }  }  if increment <= 1 {   break  } } return nums}

实现一

实现二

直接插入排序再少量数据或者少量数据无序的情况下性能是否优秀，因此希尔排序是将数列划分为多个很小部分或者无序数据很小的部分，对这些部分进行排序后再不断进行合并

插入排序的一个变种，采用分而治之的思想

复杂度

当增量数据是这个时

不同增量序列的时间复杂度不同

希尔排序

将一个数组（递归地）分成两半分别排序，再对这两个有序数组合并成一个有序的大数组

树的高度是logN，每一层都要进行O(n)的操作，所以时间复杂度是O(NlogN)

O(N)

自顶向下归并排序

O(nlogn)

自底向上归并排序

归并排序

待排序数组

right先移动，找到第一个小于主元的元素

right的元素移动到left的位置，那么right所在位置就空了

left从左向右移动，找到第一个大于主元的元素

left元素移动到right位置，left空了

以此类推，接下来继续移动right，再left，直到left>=right就结束

再把主元放上去就行了，主元左边是小于它的数，主元右边是大于它的数

最后主元左边的数组和右边的数组分别做同样的操作，直到左边和右边都排好序，那么整个数组就拍好了

快排还有其他实现方式，道理类似

算法流程

对于极端情况（数组顺序或者逆序）时间复杂度为O(n^2)

选取主元时不选第一个，即随机选一个和第一个交换再走原逻辑

为了避免极端情况

代码实现

加上随机后基本不会达到最差情况O(n^2)，一般而言O(nlogn)

三向切分快速排序

快速排序

什么是堆

堆排序

791. 自定义字符串排序

排序

数据结构（Golang版本）