数据结构详细解析与代码实现
2023-12-12 20:52:30 13 举报AI智能生成
数据结构golang示例
作者其他创作
大纲/内容
时间复杂度
在进行算法分析时，语句的执行总次数T(n)是关于时间规模n的函数，进而分析T(n)随n的变化情况确定T(n)。T(n)=O(f(n))，问题规模n的增大，是否的执行时间的增长率和f(n)相同。
O
常数阶
线性阶
for循环内时间复杂度为O(1)
对数阶
平方阶
O表示法保留O(n^2)
各时间复杂度耗时依此从小到大
一般情况我们讨论的运行时间是最坏情况的运行时间，也就是不会再差了
线性表
定义
若线性表表示为
ai是ai+1的直接前驱，ai+1是ai的直接后继
长度为0是称为空表
实现
顺序存储
相邻两个元素的地址也是相邻的
伪代码
操作
插入
时间复杂度O(n)
删除
时间复杂度O(n)
链式存储
通过指针将各个部分联系起来
头指针与头结点
单链表
所有节点都只有一个Next指针指向下一个，没有pre指针指向上一个
插入C
首先要找到A（C插入后的直接前驱），有指针指向A，这个指针称为cur。现实情况A不一定是第一个节点
然后C.Next指向cur（确实就是A）的Next
最后cur（也就是A）的Next指向C
删除C
首先还是找到A（C的直接前驱），用cur指针指向A
用一个temp指针保存C
其次，cur的Next指针指向C的Next
其实上一步就结束了，看情况看C的Next指针要不要指向空
循环链表
双链表
每个节点既有指向上一个节点的指针也有指向下一个节点的指针
带头结点的双向链表
空表
往A后面插入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)
删除C
第一步找到C
cur.Next.Pre = cur.Pre (B的Next指向A) cur.Pre.Next = cur.Next (A的Next指向B)
C的pre和Next看情况是否置空
单链表与顺序存储的优缺点
差分数组
LeetCode推荐
21. 合并两个有序链表
19. 删除链表的倒数第 N 个结点
23. 合并K个升序链表
141. 环形链表
栈与队列
栈
定义
FILO：后进先出
API
实现
顺序存储实现
golang实现
链式存储实现
使用
递归
队列
定义
队列只允许一端进行插入操作，另一端进行删除操作的线性表
实现
接口
链式存储
顺序存储
单调栈\单调队列
TODO
循环队列
TODO
LeetCode推荐
20. 有效的括号
232. 用栈实现队列
225. 用队列实现栈
51. N 皇后
串
字符串
KMP
树
字典树Trie
线段树Segment Tree
红黑树 Red -Black Tree
二分查找树
二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点
查找key
如果 key 大于根节点，则在右子树中进行查找；
如果 key 小于根节点，则在左子树中进行查找；
如果 key 等于根节点，也就是找到了这个节点，返回根节点即可。
插入key
特殊场景
当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)
自平衡二叉树
为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。
每个节点的左子树和右子树的高度差不能超过 1
B树
为了解决降低树的高度的问题，后面就出来了 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树的区别
叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
堆
堆是一棵完全二叉树
大顶堆
所有节点的值都大于它的左子节点和右子节点
采用数组的方式实现大顶堆，位置k的左子树所在的位置为2*k+1，右子树是2*k+2
小顶堆
所有节点的值都小于它的左子节点和右子节点
图
邻接矩阵
最短路径
查找
二分查找
时间复杂度 O(logn)
并查集Union-Find
跳表
排序
定义
稳定性
序列里有两个相同的值，一个在前称为a，一个在后称为b，排完序后a还是在b的前面，该排序算法称为稳定的。如果不能保证a一定在b的前面，该排序算法称为不稳定
内排序与外排序
内排序
整个排序的过程中都是在内存进行
外排序
排序的数据集太大，内存放不下，需要内存和外存进行多次数据交换
前言
排序会用到的方法
交换数组第i和第j个元素
交换数组第i和第j个元素，仅限整型且i不等于j
^是异或
二进制表示时，同一位相同异或结果为0，不同结果为1
0001
0110
0110
这两个二进制数的异或结果为0111
0^任何数=任何数
两个相同的数异或等于0
各个排序可视化
想知道自己排序算法对不对做这道题
冒泡排序
思想
是一种交换排序，凉凉比较相邻记录的关键字，如果反序则交换，正序则跳过，直到没有反序为止
实现
func BubbleSort(nums []int) []int {
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums) - i - 1; j++ {
if nums[j] > nums[j+1] {
Swap(nums, j, j+1)
}
}
}
return nums
}
func Swap(nums []int, i, j int) {
nums[i] ^= nums[j]
nums[j] ^= nums[i]
nums[i] ^= nums[j]
}
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums) - i - 1; j++ {
if nums[j] > nums[j+1] {
Swap(nums, j, j+1)
}
}
}
return nums
}
func Swap(nums []int, i, j int) {
nums[i] ^= nums[j]
nums[j] ^= nums[i]
nums[i] ^= nums[j]
}
图中绿色部分表示已经排好序
外层第i次循环我习惯称为第i趟，每一趟都会确认一个剩下数据中的最大值。
相当于第一趟确认最大值，第二趟确认第二大的值，第i趟确认第i大的值
这里其实也可以写成j < len(nums)，但没必要，因为在做无用功，这一部分已经排好序了
优化
func BubbleSort(nums []int) []int {
change := true
for i := 0; i < len(nums) && change; i++ {
change = false
for j := 0; j < len(nums) - i - 1; j++ {
if nums[j] > nums[j+1] {
Swap(nums, j, j+1)
change = true
}
}
}
return nums
}
change := true
for i := 0; i < len(nums) && change; i++ {
change = false
for j := 0; j < len(nums) - i - 1; j++ {
if nums[j] > nums[j+1] {
Swap(nums, j, j+1)
change = true
}
}
}
return nums
}
新增一个标签，判断当前数据是否已经有序
时间复杂度
比较次数
复杂度O(n^2)
最好情况的时间复杂度
数列有序的情况下复杂度为O(n)
空间复杂度
O(1)
简单选择排序
定义
简单来说就是每次取剩余值中的最小值放到前面。
实现
func SelectSort(nums []int) []int {
for i := range nums {
minPos := i//记录本轮最小值所在的位置
for j := i + 1; j < len(nums); j++ {
if nums[minPos] > nums[j] {
minPos = j
}
}
if i != minPos {
Swap(nums, minPos, i)
}
}
return nums
}
for i := range nums {
minPos := i//记录本轮最小值所在的位置
for j := i + 1; j < len(nums); j++ {
if nums[minPos] > nums[j] {
minPos = j
}
}
if i != minPos {
Swap(nums, minPos, i)
}
}
return nums
}
时间复杂度
O(n^2)
空间复杂度
O(1)
直接插入排序
定义
图解
当前在排的节点一个一个向前比较，直到找到自己的位置
为了避免多次交换，一般而言都是找到位置后，位置之后的数据向后移动一位，再把当前数据放进去
实现
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
}
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)
一般而言，少量的数据无序的情况下直接插入排序的性能很优秀
空间复杂度
O(1)
希尔排序
定义
使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组
换句话，将h个有序的数组交织在一起组成的一个数组
通过将数组不断变为h有序（h从大到小直到1），当h=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
}
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
}
注：最后一个增量必须是1
实现二
插入排序的一个变种，采用分而治之的思想
直接插入排序再少量数据或者少量数据无序的情况下性能是否优秀，因此希尔排序是将数列划分为多个很小部分或者无序数据很小的部分，对这些部分进行排序后再不断进行合并
时间复杂度
不同增量序列的时间复杂度不同
当增量数据是这个时
复杂度
空间复杂度
O(1)
归并排序
定义
将一个数组（递归地）分成两半分别排序，再对这两个有序数组合并成一个有序的大数组
自顶向下归并排序
var tmpNums []int
func MergeSort(nums []int) []int {
tmpNums = make([]int, len(nums))
merge(nums, 0, len(nums)-1)
return nums
}
func merge(nums []int, start, end int) {
if start == end {
return
}
merge(nums, start, (start + end) >> 1)
merge(nums, (start + end) >> 1 + 1, end)
for i := start; i <= end; i++ {
tmpNums[i] = nums[i]
}
p1, p2, pos := start, (start + end) >> 1 + 1, start
for p1 <= (start + end) >> 1 && p2 <= end {
if tmpNums[p1] < tmpNums[p2] {
nums[pos] = tmpNums[p1]
pos++
p1++
}else{
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
for p1 <= (start + end) >> 1 {
nums[pos] = tmpNums[p1]
pos++
p1++
}
for p2 <= end {
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
func MergeSort(nums []int) []int {
tmpNums = make([]int, len(nums))
merge(nums, 0, len(nums)-1)
return nums
}
func merge(nums []int, start, end int) {
if start == end {
return
}
merge(nums, start, (start + end) >> 1)
merge(nums, (start + end) >> 1 + 1, end)
for i := start; i <= end; i++ {
tmpNums[i] = nums[i]
}
p1, p2, pos := start, (start + end) >> 1 + 1, start
for p1 <= (start + end) >> 1 && p2 <= end {
if tmpNums[p1] < tmpNums[p2] {
nums[pos] = tmpNums[p1]
pos++
p1++
}else{
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
for p1 <= (start + end) >> 1 {
nums[pos] = tmpNums[p1]
pos++
p1++
}
for p2 <= end {
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
时间复杂度
树的高度是logN，每一层都要进行O(n)的操作，所以时间复杂度是O(NlogN)
空间复杂度
O(N)
自底向上归并排序
func MergeSort2(nums []int) []int {
tmpNums := make([]int, len(nums))
for sz := 1; sz < len(nums); sz *= 2 {
for i := 0; i + sz < len(nums); i += sz * 2 {
end := min(i + sz * 2, len(nums))
for j := i; j < end; j++ {
tmpNums[j] = nums[j]
}
p1, p2, pos := i, i + sz, i
for p1 < i + sz && p2 < end {
if tmpNums[p1] < tmpNums[p2] {
nums[pos] = tmpNums[p1]
pos++
p1++
}else{
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
for p1 < i + sz {
nums[pos] = tmpNums[p1]
pos++
p1++
}
for p2 < end {
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
}
return nums
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
tmpNums := make([]int, len(nums))
for sz := 1; sz < len(nums); sz *= 2 {
for i := 0; i + sz < len(nums); i += sz * 2 {
end := min(i + sz * 2, len(nums))
for j := i; j < end; j++ {
tmpNums[j] = nums[j]
}
p1, p2, pos := i, i + sz, i
for p1 < i + sz && p2 < end {
if tmpNums[p1] < tmpNums[p2] {
nums[pos] = tmpNums[p1]
pos++
p1++
}else{
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
for p1 < i + sz {
nums[pos] = tmpNums[p1]
pos++
p1++
}
for p2 < end {
nums[pos] = tmpNums[p2]
pos++
p2++
}
}
}
return nums
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
时间复杂度
O(nlogn)
空间复杂度
O(N)
快速排序
算法流程
待排序数组
选择第一个元素作为主元，设置两个指针left,right，left自左向右，right自右向左移动
right先移动，找到第一个小于主元的元素
right的元素移动到left的位置，那么right所在位置就空了
left从左向右移动，找到第一个大于主元的元素
left元素移动到right位置，left空了
以此类推，接下来继续移动right，再left，直到left>=right就结束
再把主元放上去就行了，主元左边是小于它的数，主元右边是大于它的数
最后主元左边的数组和右边的数组分别做同样的操作，直到左边和右边都排好序，那么整个数组就拍好了
快排还有其他实现方式，道理类似
代码实现
func QuickSort(nums []int) []int {
partition(nums, 0, len(nums) - 1)
return nums
}
//左闭右闭
func partition(nums []int, start, end int) {
if start >= end {
return
}
originStart, originEnd := start, end
pivot := nums[start]
for start < end {
for ; start < end && nums[end] >= pivot; end-- {}
if start < end {
Swap(nums, start, end)
}
for ; start < end && nums[start] <= pivot; start++ {}
if start < end {
Swap(nums, start, end)
}
}
nums[start] = pivot
partition(nums, originStart, start - 1)
partition(nums, end + 1, originEnd)
}
partition(nums, 0, len(nums) - 1)
return nums
}
//左闭右闭
func partition(nums []int, start, end int) {
if start >= end {
return
}
originStart, originEnd := start, end
pivot := nums[start]
for start < end {
for ; start < end && nums[end] >= pivot; end-- {}
if start < end {
Swap(nums, start, end)
}
for ; start < end && nums[start] <= pivot; start++ {}
if start < end {
Swap(nums, start, end)
}
}
nums[start] = pivot
partition(nums, originStart, start - 1)
partition(nums, end + 1, originEnd)
}
对于极端情况（数组顺序或者逆序）时间复杂度为O(n^2)
为了避免极端情况
func partition(nums []int, start, end int) {
if start >= end {
return
}
originStart, originEnd := start, end
t := start + rand.Intn(end - start + 1)
if start != t {
Swap(nums, start, t)
}
pivot := nums[start]
for start < end {
for ; start < end && nums[end] >= pivot; end-- {}
if start < end {
Swap(nums, start, end)
}
for ; start < end && nums[start] <= pivot; start++ {}
if start < end {
Swap(nums, start, end)
}
}
nums[start] = pivot
partition(nums, originStart, start - 1)
partition(nums, end + 1, originEnd)
}
if start >= end {
return
}
originStart, originEnd := start, end
t := start + rand.Intn(end - start + 1)
if start != t {
Swap(nums, start, t)
}
pivot := nums[start]
for start < end {
for ; start < end && nums[end] >= pivot; end-- {}
if start < end {
Swap(nums, start, end)
}
for ; start < end && nums[start] <= pivot; start++ {}
if start < end {
Swap(nums, start, end)
}
}
nums[start] = pivot
partition(nums, originStart, start - 1)
partition(nums, end + 1, originEnd)
}
选取主元时不选第一个，即随机选一个和第一个交换再走原逻辑
时间复杂度
加上随机后基本不会达到最差情况O(n^2)，一般而言O(nlogn)
三向切分快速排序
堆排序
定义
什么是堆
LeetCode推荐
791. 自定义字符串排序
0 条评论
下一页
