一、数据结构与算法基础
1.说一下几种常见的排序算法和分别的复杂度。
冒泡排序
核心思想：遍历数组N次，每次将最大的数字交换到最后。
时间复杂度：O(N2)
空间复杂度：O(1)快速排序
核心思想：选择一个基准数，比它小的数放左边，比它大的数放右边，依次递归。
时间复杂度：最坏情况 O(N2)，平均 O(N*lgN)
空间复杂度：主要来源于递归栈，因此最多O(N) 最少 O(lgN)插入排序
核心思想：打扑克牌时摸牌阶段的排序。
时间复杂度：O(N2)
空间复杂度：O(1)选择排序
核心思想：从没有排序的数列中找到最小的放在最前面，不停重复。（和冒泡类似）
时间复杂度：O(N2)
空间复杂度：O(1)堆排序
核心思想：利用“最大堆”（最小堆类似）每次找出最大的值，从而形成有序数组。
时间复杂度：O(N*lgN)
空间复杂度：O(1)归并排序
核心思想：将两个有序数组合并成一个数组，利用递归，从两个单个元素开始一直到一整个数组。
时间复杂度：O(N*lgN)
空间复杂度：O(N)，在合并数组时需要借助新的空间。
2.用Java写一个冒泡排序算法
public static void bubble(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
3.描述一下链式存储结构。
常见的链式存储结构有单向链表和双向链表。链表的结构特点就是有一个值字段，同时有指向下一个结点或者上一个结点的字段。java中定义如下：
//单向链表
public class ListNode {
int val;
ListNode next;
}
//双向链表
public class ListNode {
int val;
ListNode pre;
ListNode next;
}
4.如何遍历一棵二叉树？
二叉树的遍历有前序遍历，中序遍历和后续遍历。可以使用递归来完成，亦可使用循环的方式完成。
5.倒排一个LinkedList。
- 方法1：如果利用一个栈来存放，那么依次入栈，再依次出栈即可立即完成倒排。
- 方法2：从左往右依次倒排，进行到
i的位置时，i前面的是倒排的，i后面还是顺排的。
6.用Java写一个递归遍历目录下面的所有文件。
//遍历一个目录下所有的文件
public static void ScanFiles(File file) {
if (file == null || !file.exists()) {
return;
}
if (!file.isDirectory()) {
System.out.println(file.getName());
} else {
File[] files = file.listFiles();
if (files != null) {
for (File f : files) {
ScanFiles(f);
}
}
}
}
目录列表
一、数据结构与算法基础
二、Java基础
三、JVM
四、多线程/并发
五、Linux使用与问题分析排查
六、框架使用
七、数据库相关
八、网络协议和网络编程
九、Redis等缓存系统/中间件/NoSQL/一致性Hash等
十、设计模式与重构
本文是针对知乎文章《成为Java顶尖程序员，先过了下面问题》的解答
