数据结构-学习记录

数据结构的分类
1.逻辑结构-----集合、树形，图型、树型、线性结构
2.物理结构-----顺序存储、链式存储。（查找，插入，删除）

时间复杂度、控件复杂度。
o(1)<o(logn)<n<nlogn<n^2<n3<2^n

---

java 一个引用用8个字节来表示。

public class A{ //对象头部占用16个字节，
pubilc int a=1; //// a占用4个字节。 会保存成8的倍数 24个字节。
}

---

冒泡排序 o(n^2)
for(i,n,i++),,,,,,for(int j,j<n-i-1;j++)

选择排序--选择最大值交换，o(n^2)

插入排序---比较，然后需要移动。（n^2）

希尔排序--设置增量排序。增量设置【5，2，1】。 性能较好。但不清楚复杂度的级别。

image.png

归并排序：分治 nlogn 控件复杂度有提升。

image.png

快速排序：时间最坏 n^2 nlogn 空间 o(n) 比较大
堆排序： 用数组实现 父节点左节点 n -----2n 大顶堆对应升序。

线性表：存储分为顺序存储，链式。

顺序表-----ArrayList（ 底层是数组实现，扩容---采用array.copyof() 复制数组。iterator ---提供遍历方法）
链表-----Linklist<T>(实现iterator方法来实现遍历)

单向链表是否有环问题，（快慢指针） 入口，，设定一个新指针与慢指针相遇即为入口。

约瑟夫问题，循环链表问题。

栈：逻辑思想，两种结构（数组和链表）。逆波兰表达式ab+， 中缀表达式a+b。
队列：先进先出。

树结构：二叉树 二叉排序树。

优先队列：不同优先级 堆实现

平衡树：是树的高度达到一个平衡。2-3树--》红黑树（红的节点组成3节点）。
红黑树的插入，平衡，左旋右旋。颜色反转。跟节点的颜色总是黑色。

B-Tree(节点包含的不确定)M阶（M-1个key,M 个子节点，跟节点至少有两个自己子节点）

文件系统使用B树结构，
磁盘，盘面，磁道。磁头，扇区。 移动臂。
缓存---》减少磁盘寻找磁道的时间。
页， 1kb*N 读到内存，用完之后，系统发出缺页异常，，再去读取下一页。
B树保存页节点。--减少IO读取次数，

B+Tree（非叶子结点起到索引的作用）

并查集--简单的树型结构。还要表示就行 ，是不是在一个组（根节点是不是一个），和合并（根节点指向另个根节点）。