1、LRU算法分析
最近最少使用页面置换算法，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。
image.png
上述图片比较好理解，但会有大量的内存拷贝操作，实现上还有一种方法性能更好：双向链表
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。
image.png
2、排序算法有哪些？
冒泡、快排、堆排序
3、最快的排序算法是哪个？
4、手写一个冒泡排序
5、手写快速排序代码
6、快速排序的过程、时间复杂度、空间复杂度
7、手写堆排序
private int[] data; // 利用数组和完全二叉树的性质，存储数据
private int size; // 当前大小
private int maxSize; // 最大容量
public HeapSort() {
// 默认大小
this(16);
}
public HeapSort(int maxSize) {
// 下标为0的位置，不存储实际值，只存储哨兵
data = new int[maxSize + 1];
data[0] = Integer.MIN_VALUE; // 哨兵，最小值
this.size = 0;
this.maxSize = maxSize;
}
// 向最小堆插入一个值
public boolean insert(int value) {
int index = ++size; // 当前要插入的下标
// 判断是否满了
if (size == maxSize) {
System.out.println("堆已满，无法插入 " + value);
return false;
}
// 沿着祖先路径，查找待插入值的合适位置
// 当父节点大于自己时
while (value < data[index / 2]) {
// 将父节点放在自己当前的位置
data[index] = data[index / 2];
// 然后再继续和上一级比较
index = index / 2;
}
// 循环结束之后，index就是待插入值value的最终位置了，因为data[index] < (data[0] = Integer.MIN_VALUE) 是不可能成立的
// 这也是哨兵的作用，不用每次都判断index > 0
data[index] = value;
return true;
}
8、堆排序过程、时间复杂度及空间复杂度
时间:nlogN -------------空间: log(1)
9、写出你所知道的排序算法及时空复杂度，稳定性
冒泡排序 稳定 时间复杂度：O(n2) 空间复杂度O(1)
快速排序：不稳定 时间复杂度：O(log2N) 空间复杂度O(log2n)-O(logN)
快速排序：不稳定 时间复杂度：O(log2N) 空间复杂度O(1)
