数据结构总结
image.png
一、排序
注：以下关于时间复杂度的描述时出现log2n代表的是以2为底的n的对数，空间复杂度也一样
把一组杂乱的数据按一定规律顺次排列起来（实质是按关键字排序），目的是为了方便查找。
内部排序：待排序记录在内存中。
外部排序：待排序记录一部分在外存中，一部分在内存中，外部排序比较复杂。
排序算法好坏的衡量：
- 时间效率——排序速度（比较次数和移动次数）
- 空间效率——占内存辅助空间的大小
- 稳定性——假定A和B的关键字相等，若排序之后A和B的先后顺序不变，则称这种排序就是稳定的。
分为4大类（插入排序，交换排序，选择排序，归并排序）
-
1、插入排序（即边插入边排序，保证子序列中随时都是排好序的）
- 直接插入排序（基于顺序查找）
- 折半插入排序（基于折半查找）
- 希尔排序（基于逐趟缩小增量）
图片.png
void InsertSort(SqList ＆L){
int i,j;
for(i=2;i<=L.length;++i){
//如果出现后一位比前一位小，则开始排序
if( L.r[i].key<L.r[i-1].key){ //将L.r[i]插入有序子表
L.r[0]=L.r[i]; //下标为0的数组复制为哨兵
L.r[i]=L.r[i-1];
for(j=i-2; L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j]; //如果后一位总比前一位大，则数据都后移
L.r[j+1]=L.r[0]; //等上面移动好再插入到正确位置
}
}
}
直接插入排序算法分析
若对象为n个，则执行n-1趟，比较次数与移动次数和初始数据排列有关。
最好情况：每趟比较一次，不移动，总比较次数n-1。
最坏情况：第i个对象的插入都必须与前面第i-1个对象比较，并且每比较一次都得做一次数据移动。
直接插入排序是一种稳定排序，时间复杂度：o(n的平方)，空间复杂度：o(1)。
图片.png
//代码解读：通过low左指针，high右指针，m中间折半指针，通过移动这3指针来对数据进行排序
void BInsertSort ( SqList &L){
for ( i = 2; i <= L.length ; ++i ){
L.r[0] = L.r[i];
low = 1;
high = i-1 ;
//直到右指针小于左指针，才停止移动
while (low <= high){
m = ( low + high ) / 2 ; //m指针位置是前后指针位置相加折半而得
if (L.r[0].key < L.r[m].key)
high = m-1 ;
else
low = m+1;
}
//
for ( j=i-1; j>=high+1; --j)
L.r[j+1] = L.r[j];
L.r[high+1] = L.r[0];
}
}
折半插入排序算法分析
减少了比较次数，但没有减少移动次数。
平均性能和速度就优于直接插入排序，但是在直接插入排序最好情况下就还是直接插入排序速度更胜一筹。
也是一种稳定排序，时间复杂度：o(n的平方)；空间复杂度：o(1)。
图片.png
void ShellSort(SqList &L，int dlta[ ]，int t){
//按增量序列dlta[0…t-1]对顺序表L作Shell排序
for(k=0；k<t；++k)
ShellInsert(L，dlta[k])； //增量为dlta[k]的一趟插入排序
}
void ShellInsert(SqList &L，int dk) {
//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子
for(i=dk+1；i<=L.length； ++ i) //开始将r[i] 插入有序增量子表
if(r[i].key < r[i-dk].key) {
r[0]=r[i]； //暂存在r[0]
for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk)
r[j+dk]=r[j]； //关键字较大的记录在子表中后移
r[j+dk]=r[0]； //在本趟结束时将r[i]插入到正确位置
}
}
希尔排序算法分析
是一种不稳定的排序算法，时间复杂度：o(n的1.3次方)，空间复杂度：o(1)。
最后一组增量值必须是1，不过如何选定最佳d序列是主要难题，还有不宜采用链式存储结构。
-
2、交换排序（两两比较，发生逆序则交换，直到所有记录都排好序）
- 冒泡排序（核心代码思路：用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数）
- 快速排序
图片.png
void bubble_sort(SqList &L){
int m,i,j,flag=1; //flag作为一个标记
RedType x;
m=n-1;
while((m>0)&&(flag==1)){
flag=0;
for(j=1;j<=m;j++){
if(L.r[j].key>L.r[j+1].key){ //前小后大，把大的数往后冒
flag=1;
//以下三步在两两交换
x=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=x;
}
}
m--;
}
}
冒泡排序算法分析
最好的情况：只进行一趟排序，n-1次比较，不移动数据。
最坏的情况：需要n-1趟排序，第i趟比较n-1次，移动3(n-1)次。
是一种稳定的排序算法，时间复杂度：o(n的平方)，空间复杂度：o(1)。
图片.png
//移动指针
int Partition ( SqList &L，int low, int high ) {
L.r[0] = L.r[low];
pivotkey = L.r[low].key; //指定第一个中心枢轴为low左指针
//当右指针位置移动到左指针的左边
while ( low < high ) {
while ( low < high && L.r[high].key >= pivotkey ) //右边值比中心枢轴小，移动右指针
--high;
L.r[low] = L.r[high]; //把右指针指向的值赋值给左指针指向的值
while ( low < high && L.r[low].key <= pivotkey )
++low;
L.r[high] = L.r[low];
}
L.r[low]=L.r[0]; //把中心枢轴的值指向最后左指针指向的值
return low;
}
void QSort ( SqList &L，int low, int high ) {
if ( low < high ) {
pivotloc = Partition(L, low, high ) ;
//递归调用
Qsort (L, low, pivotloc-1) ;
Qsort (L, pivotloc+1, high )
}
}
void main ( ){
QSort ( L, 1, L.length );
}
快速排序算法分析
平均排序时间是：o(nlog2 n)，空间复杂度是：o(n)，递归要用到栈空间。
目前就内部排序里，快速排序是最好的一个了。
快速排序是不稳定排序，最好情况是o(log2 n)，最坏情况是o(n)。
-
3、选择排序（每一趟在n-i+1的数据中选出最小的值，作为有序序列的第i个记录）
- 简单选择排序
- 堆排序（参考这篇文章：https://www.cnblogs.com/chengxiao/p/6129630.html）
图片.png
简单选择排序算法分析
是一种稳定的排序，时间复杂度：o(n的平方)，空间复杂度：o(1)。
图片.png
堆排序算法分析
由于是完全二叉树，所以采用顺序存储结构，对于大量记录的序列进行堆排序是很有效的。
是一种不稳定的排序，时间复杂度：o(nlog2 n)，空间复杂度：o(1)。
-
4、归并排序
图片.png
归并排序算法分析
是一种稳定的排序算法，时间复杂度：o(nlog2n)，空间复杂度：o(n)。
-
5、排序总结
图片.png
图片.png
图片.png
图片.png
图片.png
二、数组与链表的区别？
从三个角度出发考虑：
①逻辑结构角度，数组实现是固定长度的，这样有个缺点就是当插入数据多时会造成溢出不够存，当数据少时会造成浪费内存，而链表则是动态分配存储空间的，利于插入和删除。
②内存存储角度，数组使用的是从栈来分配空间，不过若使用new创建对象的话就是从堆来分配空间，而链表则是从堆来分配空间。从栈来分配空间自由度小，不灵活；从堆来分配空间自由度大，相对灵活。
③访问方式角度，数组在内存中是连续存储的，采用下标来进行查找，而链表是链式存储结构，查找时只能线性地从前往后进行访问，所以查找效率比数组低。
三、简述一下快速排序？
思路：就是不断把规模划分为更小的规模
步骤：
①先确定一个中心枢纽，一般为无序序列的第一个元素，
②对无序序列设置low左指针和high右指针，移动指针使指针对应的关键字值与中心枢纽的值比较，若比枢纽值大则放在枢纽右边，若比枢纽值小则放在枢纽左边。如此一趟比较下来，就把序列划分为2部分。
③迭代继续进行这样的比较，直到划分后左右2部分只剩下一个元素，整个序列变得有序。
四、解决哈希冲突的方法？
哈希表，也称为散列表，是根据关键码值直接进行访问的数据结构。
什么是哈希冲突？即是为产生冲突的地址寻找下一个地址。
1、开放地址法（常有线性探测法、二次探测法），附带如下习题解释
数据结构总结
2、拉链法（链地址法），附带如下习题解释
数据结构总结
- 3、平方探测法
- 4、伪随机序列法
五、B+树和B树的区别？
以一个m阶的B树和B+树来解释，树的阶数指的是一个结点最多有m个子节点，也就是每个节点上最多的键值个数。
图片.png
图片.png
①关键字的数目不同，B+树的分支节点有m个关键字，其叶子节点也有m个，其关键字只起到一个索引的作用，而B树虽也有m个子节点，但它只有m-1个关键字。
②存储的位置不同，B树的每个节点都存储key和data，所有节点组成这棵树，叶子节点指针为null，而B+树则仅仅叶子节点存储data，所有叶子节点可以组成这棵树，叶子节点不存储指针。
六、为什么B+树比B树更适合作为数据库的索引？
①因为B+树的读写代价更低，即磁盘IO操作次数更少，而这又是为什么呢？因为B+树内部节点没有指向具体关键字的指针所以内部节点比B树少些。
②因为B+树的查询更加稳定，而这又是为什么呢？因为B+树非终端节点不存储data，只相当于叶子节点的关键字索引，所以所有的关键字查询都会走一条从根到叶子节点的路径，所有路径的查找长度是一样的，查询效率稳定。
七、mysql中的两种存储引擎MyISAM和InnoDB，采用的索引实现方式是不同的。
①MyISAM中，data存的是数据地址，数据是数据，索引是索引，分开起来存放在不同的文件里，称为非聚集索引。
②InnoDB中，data存的是数据本身，索引也是数据，数据和索引都放在同一个文件里，称为聚集索引。
八、二叉查找树（BST）
二叉查找树：左子树上所有节点的值一定小于等于根节点的值，右子树上所有节点的值一定大于等于根节点的值，左右子树又分别为二叉排序树。
二叉查找树查找元素例子：图片.png 步骤：10>9进入右子树，10<13进左子树，10<11进左子树，最后就查找到10了，应用了二分查找的思想，查找所需的最大次数就是二叉查找树的高度。
缺陷：就是当根节点的值足够大时，插入新的值都比根节点值小，就会导致左右子树不平衡，变成“瘸子”，这样查找就变成了线性的了，查找效率就大大降低，而红黑树就是为了解决这种情况的。
AVL树（自平衡的二叉查找树）：任意节点的两个子树的高度最大只相差1，增加或删除都需要通过一次或多次旋转来平衡这个树。
附：关于面试的红黑树、AVL树、BST树原理分析
九、红黑树？
要想了解红黑树，首先需要理解上图提到二叉查找树（BST），因为红黑树说到底就是自平衡的二叉排序树。
红黑树：①节点是红色或黑色，②根节点是黑色，③每个红色节点的子节点都是黑色，④每个叶子节点都是黑色的空节点，⑤从任意节点到其每个叶子的所有路径都包含数目相同的黑色节点。
红黑树的操作时间跟二叉查找树的时间复杂度是一样的，执行查找、插入、删除等操作的时间复杂度为O（logn）图片.png 因为红黑树这些规则约束，才保证了红黑树的自平衡，红黑树到叶子节点的最大路径不会超过最短路径的2倍。
红黑树涉及的平衡调整有3种方式：①变色，②左旋转，③右旋转
红黑树的应用：JDK的TreeMap，TreeSet集合的底层实现就是红黑树，Java8的HashMap底层实现也是红黑树。
附：java面试搞懂红黑树
