Java面试八股--08-数据结构和算法篇
1、怎么理解时间复杂度和空间复杂度
时间复杂度和空间复杂度一般是针对算法而言，是衡量一个算法是否高效的重要标准。先纠正一个误区，时间复杂度并不是算法执行的时间，在纠正一个误区，算法不单单指冒泡排序之类的，一个循环升值一个判断都可以称之为算法。其实理解起来并不冲突。八大排序甚至更多的算法本质上也是通过各种循环判断来实现的。
时间复杂度：指算法语句的执行次数。O(1),O(logn),O(n^2)
空间复杂度：就是一个算法在运行过程中临时占用的存储空间大小，换句话说就是被创建次数最多的变量。它被创建了多少次，那么这个算法的空间复杂度就是多少。有个规律，如果算法语句中就有创建对象。那么这个算法的时间复杂度和空间复杂度一般一致，很好理解，算法语句被执行了多少次就创建了多少对象。
2、数组和链表结构简单对比
数组：相同的数据类型的元素按一定的顺序排列的组合，就是把有限个类型相同的变量用同一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。
数组的特性：
1.数组必须先定义固定长度，不能适应数据动态增减
2.当数据增加时，可能超出原先定义的元素个数，当数据减少时，造成内存浪费
3.数组查询比较方便，根据下标就可以直接找到元素，时间复杂度O(1)；增加和删除比较复杂，需要移动操作数所在位置后的所有数据，时间复杂度为O(N)
链表：是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的特性：
1.链表动态进行存储分配，可适应数据动态增减
2.插入、删除数据比较方便,时间复杂度O(1)；查询必须从头开始找起，十分麻烦，时间复杂度O(N)
常见的链表:
1.单链表：通常链表每一个元素都要保存一个指向下一个元素的指针
2.双链表：每个元素既要保存到下一个元素的指针，还要保存一个上一个元素的指针
3.循环链表：在最后一个元素中下一个元素指针指向首元素
链表和数组都是在堆里分配内存
应用：
如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了
3、怎么遍历一个树
四种遍历概念
先序遍历：先访问根节点，再访问左子树，最后访问右子树。
后序遍历：先左子树，再右子树，最后根节点。
中序遍历：先左子树，再根节点，最后右子树。
层序遍历：每一层从左到右访问每一个节点。
每一个子树遍历时依然按照此时的遍历顺序。可以采用递归实现遍历。
4、冒泡排序（Bubble Sort）
算法描述：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
如果两个元素相等，不会再交换位置，所以冒泡排序是一种稳定排序算法。
5、快速排序（Quick Sort）
算法描述：
使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6、二分查找（Binary Search）
算法描述：
- 二分查找也称折半查找，它是一种效率较高的查找方法，要求列表中的元素首先要进行有序排列。
- 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
- 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
- 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
后续会继续补充，到这里已经有点累了。。。