小灰的算法之旅

1.算法和数据结构

  1. 算法是什么? 算法是一系列程序指令,用来处理特定运算和逻辑问题。
  2. 什么是数据结构? 数据结构是数据的组织、管理和存储格式,其使用的目的是为了高效的访问和修改。 数据结构包含数组,链表。以及树,图这种复杂的数据结构。 3.什么是时间复杂度? T(n) = O(f(n)) 4.什么是空间复杂度? S(n) = O(f(n))

2.数据结构基础

  • 数组VS链表
VS 查找 更新 插入 删除
数组 O(1) O(1) O(n) O(n)
链表 O(n) O(1) O(1) O(1)
  • 栈和队列

    • 是先入后出FILO(First In Last Out) 入栈:PUSH 出栈:POP 可以用来实现递归逻辑,以及面包屑导航(浏览器浏览历史回退)

    • 队列是先入先出FIFO(First In First Out) 队头:Front 队尾:Rear 入队:enquere 出队:dequeue

  • 散列表(哈希表 hash table) 散列表也叫哈希表,是存储Key-Value的集合,对于一个key,散列表可以在接近 O(1)的时间内完成读写操作。散列表通过哈希函数实现key和数组下标的转换,通过开放寻址法和链表法来解决冲突。 哈希函数:通过哈希函数,可以将字符串和其他类型的Key,转换成数组下标index 例如Key=abcd,index= HashCode(“abcd”)%Array.length = 1420036703%8 = 7 hashcode: 区分不同对象的唯一标识,整形变量,通过取模运算获得(java为了优化性能,采用位运算) 解决冲突: 开放寻址法: 链表法:(java采用此方法)【数组+链表的结合】 扩容:HashMap.size >= Capicity × LoadFactor 时扩容 Capicity:当前HashMap长度 LoadFactor:负载因子,默认为0.75f 创建一个新的hashMap,容量为原来两倍并重新散列,JDK 8之后,会把Entry链表转为红黑树这种数据结构。

3.树

:树是n个节点的有限集,有且仅有一个特定的称为根的节点。当n>=1时,其余节点可以分为m个互不相交的有限集,每一个集合本身又是一个树,并成为根的子树。 二叉树:二叉树是树的一种特殊形式,每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式。 满二叉树:一个树的所有非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上 完全二叉树:有一个n节点的二叉树,按照层级顺序编号,则所有的节点编号从1到n,如果这个树所有节点和同样深度的满二叉树的编号从1到n的节点位置相同,则为完全二叉树。

二叉树可以用 1.链式存储结构:data,left,right 2.数组:如果父节点下标是parant,则左孩子节点下标为2 × parent+1,右孩子节点为2 × parent+2,如果孩子节点为child,则父节点下标为(child-1)/2 来表达。

主要作用:查找操作、维持相对顺序

二叉查找树:除满足二叉树的特点外,还需满足下面3个条件 - 如果 左子树不为空,则左子树上所有节点的值均小于根节点的值。 - 如果右子树不为空,则右子树上所有节点的值均大于根节点的值。 - 左、右子树都是二叉查找树。 对于一个节点分布相对均很的二叉查找树来说,搜索节点的时间复杂度就是O(logn),和树的深度是一样的。

因为二叉查找树要求左子树小于父节点,右子树大于父节点,保证二叉树的有序性,因此二叉查找树还有另外一个名字 二叉排序树(binary sort tree) 二叉树的自平衡有很多种:红黑树、AVL树、树堆等

二叉树的遍历: - 深度优先遍历(1.前序遍历【根,左,右】,2.中序遍历【左,根,右】,3.后续遍历【左,右,根】) - 广度优先遍历(4.层序遍历)

深度优先遍历实现可以用递归,也可以用栈来实现。 广度优先遍历实现可以用队列。

二叉堆:本质上是一种完全二叉树 最大堆:任何一个父节点的值,都大于或等于它左右孩子节点的值。 最小堆:任何一个父节点的值,都小于或等于它左右孩子节点的值。 二叉堆的根节点叫做堆顶。 二叉堆的自我调整:把一个不符合堆性质的完全二叉树,调整为一个堆 - 1.插入节点 - 2.删除节点 - 3.构建二叉堆

优先权队列:二叉堆来实现

4.排序

O(n²)的排序 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 O(nlogn)的排序 1.快速排序 2.归并排序 3.堆排序 时间复杂度为线性的排序算法 1.计数排序 2.桶排序 3.基数排序

根据稳定性还可划分为:稳定排序和不稳定排序

冒泡排序:把相邻的两个元素比较,当一个元素大于右侧相邻的元素时,交换他们的位置;当一个元素小于等于右侧相邻元素时,位置不变。 快速排序:每一轮挑选一个基准元素(pivot),并让其他比它大的元素移动到数的一边,比它小的元素移动到数列的另一边,从而把数列拆分成两个部分。这种思路叫分治法。 元素的交换又两种实现: 1.双边循环法 2.单边循环法

非递归实现采用栈的形式。

堆排序:

1.把无序数组构建成二叉堆,需要 从小到大排序,则构建最大堆。需要从大到小排序,则构建最小堆。 2.循环删除堆顶元素,替换到二叉堆的末尾,调整堆生产新的堆顶。

参考: 小灰的算法之旅