《2021最新Java面试题全集-2021年第二版》不断更新完善！
第七章 数据结构和算法
1：队列、栈和链表是什么？
栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶 (top)。
它是后进先出(LIFO)的。对栈的基本操作只有 push(进栈)和 pop(出栈)两种， 前者相当于插入，后者相当于删除最后的元素。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
链表是一种数据结构，和数组同级。比如，Java 中我们使用的 ArrayList，其实现原理是数组。
而LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
2：用Java写一个冒泡排序
冒泡排序几乎是个程序员都写得出来，基本方式为：
（1)比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
(2)这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第 N-1 个位置。
(3)N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。
先来个简单的：
public static
void bubbleSort(int[] a, int n) {
int i, j;
for (i = 0;
i < n;
i++) {// 表示 n 次排序过程。
for (j = 1;
j < n
- i; j++)
{
if (a[j - 1] > a[j]) {// 前面的数字大于后面的数字就交换
// 交换 a[j-1]和 a[j]
int temp;
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
但是面试的时候如何写一个逼格高的冒泡排序却不是每个人都能做到，下面提供一个参考代码：
import
java.util.Comparator;
/**
* 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
*/
public interface
Sorter {
/**
* 排序
* @param list 待排序的数组
*/
public <T extends
Comparable<T>> void sort(T[] list);
/**
* 排序
* @param list 待排序的数组
* @param comp 比较两个对象的比较器
*/
public <T> void
sort(T[] list, Comparator<T> comp);
}
import java.util.Comparator;
/**
* 冒泡排序
*/
public class BubbleSorter implements Sorter {
public <T
extends Comparable<T>> void sort(T[] list) {
boolean swapped = true;
for (int i = 1, len = list.length; i < len && swapped; ++i) {
swapped = false;
for (int j = 0; j < len - i; ++j) {
if (list[j].compareTo(list[j
+ 1]) > 0) {
T temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
}
}
public <T> void
sort(T[] list, Comparator<T> comp) {
boolean swapped = true;
for (int i =
1, len = list.length; i < len && swapped; ++i) {
swapped = false;
for (int j = 0; j < len - i; ++j) {
if (comp.compare(list[j], list[j + 1]) > 0) {
T temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
}
}
}
3：用Java写一个折半查找
折半查找，也称二分查找、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。
搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组已经为空，则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半，其时间复杂度是O(logN)。
import
java.util.Comparator;
public class MyUtil {
public static <T extends
Comparable<T>> int binarySearch(T[] x, T key) {
return
binarySearch(x, 0, x.length- 1, key);
}
// 使用循环实现的二分查找
public static <T> int
binarySearch(T[] x, T key, Comparator<T> comp) {
int low = 0;
int high =
x.length - 1;
while (low <=
high) {
int mid = (low + high) >>> 1;
int cmp = comp.compare(x[mid], key);
if (cmp < 0) {
low= mid + 1;
}
else if (cmp > 0) {
high= mid - 1;
}
else {
return mid;
}
}
return -1;
}
// 使用递归实现的二分查找
private static<T extends
Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
if(low <=
high) {
int
mid = low + ((high -low) >> 1);
if(key.compareTo(x[mid])== 0) {
return mid;
}
else
if(key.compareTo(x[mid])< 0) {
return binarySearch(x,low, mid - 1, key);
}
else
{
return binarySearch(x,mid + 1, high, key);
}
}
return -1;
}
}
4：用Java写一个插入排序算法
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。
public static void sort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
//
插入的数
int
insertVal = arr[i];
//
被插入的位置(准备和前一个数比较)
int index =
i - 1;
//
如果插入的数比被插入的数小
while (index
>= 0 && insertVal < arr[index]) {
// 将把 arr[index] 向后移动
arr[index + 1]
= arr[index];
// 让 index 向前移动
index--;
}
// 把插入的数放入合适位置
arr[index + 1] = insertVal;
}
}
5：用Java写一个快速排序算法
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的)，比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素为基准值。
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。
找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。
直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
public static void sort2(int[] a, int startIndex, int endIndex) {
int start = startIndex;
int end = endIndex;
int key = a[startIndex];
while (end
> start) {
// 从后往前比较
while (end
> start && a[end] >= key)
// 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
end--;
if (a[end] <= key)
{
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
// 从前往后比较
while (end
> start && a[start] <= key)
// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
start++;
if (a[start] >= key)
{
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
// 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的 值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
}
// 递归
if (start > startIndex)
sort2(a, startIndex, start - 1);// 左边序列。第一个索引位置到关键值索引-1
if (end < endIndex)
sort2(a, end + 1, endIndex);// 右边序列。从关键值索引+1 到最后一个 }
}
在笔试面试过程中，需要手撕的常见的也就是：冒泡、折半查找、插入排序几个，快排相对就少见了，其它的复习一下思想就好了，就不去配代码了，大概率是不会让你手写代码的。
6：希尔排序算法
基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
1：操作方法:
选择一个增量序列
t1，t2，...，tk，其中 ti>tj，tk=1;
2：按增量序列个数 k，对序列进行 k 趟排序;
3：每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为
1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
7：归并排序算法
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列，分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
8：桶排序算法
基本思想是:
把数组 arr 划分为 n 个大小相同子区间(桶)，每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1：找出待排序数组中的最大值 max、最小值 min
2：我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max- min)/arr.length+1
3：遍历数组 arr，计算每个元素 arr[i] 放的桶
4：每个桶各自排序
9：排序二叉树
如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。
1：插入操作
首先要从根节点开始往下找到自己要插入的位置(即新节点的父节点)，具体流程是：
新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入;如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可;如果 大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。
2：删除操作
删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。
（1）对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
（2）对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
（3）对于要删除的节点有两个子节点，则首先找该节点的替换节点(即右子树中最小的节点)，接着替换要删除的节点为替换节点，然后删除替换节点。
3：查询操作
查找操作的主要流程为：
先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。
因此在排序二叉树中可以很容易获取最大(最右最深子节点)和最小(最左最深子节点)值。