数据结构
- 什么是队列、栈、链表
数组、链表、堆栈和队列是最基本的数据结构，队列就是一种先进先出的逻辑结构，栈是一种先进后出的逻辑结构。 - 什么是树（平衡树,排序树,B树,B+树,R树,红黑树）、堆（大根堆、小根堆）、图（有向图、无向图、拓扑）
- 栈通常采用的两种存储结构
链接存储：链栈带有头指针或头结点的单循环链表。
顺序存储：数组实现。 - 两个栈实现队列，和两个队列实现栈
链接答案
排序算法
冒泡排序
冒泡排序是一种简单的排序方法，它的基本思想是：通过相邻两个元素之间比较和交换，使较大的元素逐渐从前面移向后面（升序），就像水底下的气泡一样逐渐向上冒泡，所以被称为“冒泡”排序。冒泡排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* 排序算法
* @param list
*/
public static void bubbleSort(int[] list){
int temp;
// 做多少轮排序（最多length-1轮）
for (int i=0;i <list.length-1;i++){
// 每一轮比较多少个
for (int j=0;j<list.length-1-i;j++){
if (list[j]>list[j+1]){
//交换
temp = list[j];
list[j] = list[j+1];
list [j+1]=temp;
}
}
}
}
快速排序
快速排序的基本思想是：通过一轮排序将待排序元素分割成独立的两部分， 其中一部分的所有元素均比另一部分的所有元素小，然后分别对这两部分的元素继续进行快速排序，以此达到整个序列变成有序序列。快速排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(n*log2n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
* 快速排序算法
*/
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int point = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, point - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, point + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public static int partition(int[] list, int left, int right) {
// 用数组的第一个元素作为基准数
int first = list[left];
while (left < right) {
while (left < right && list[right] >= first) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= first) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
直接选择排序
直接选择排序(Straight Select Sort) 是一种简单的排序方法，它的基本思想是：通过length-1 趟元素之间的比较，从length-i+1个元素中选出最小的元素，并和第i个元素交换位置。直接选择排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)
1 | /** |
堆排序
堆排序(Heap Sort) 利用堆（一般为大根堆）进行排序的方法。它的基本思想是：将待排序的元素构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将它与数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的length-1 个元素重新构造成一个大根堆，这样就会得到length个元素中的次大值。如此反复执行，便能得到一个有序的序列。
堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大根堆；每个节点的值都小于或等于其左右孩子节点的值，称为小根堆。
堆排序的最坏时间复杂度为O(nlog2n)，平均时间复杂度为O(nlog2n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
* 堆排序算法
*/
public static void heapSort(int[] list) {
// 将无序堆构造成一个大根堆，大根堆有length/2个父节点
for (int i = list.length / 2 - 1; i >= 0; i--) {
headAdjust(list, i, list.length);
}
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整其为大根堆
for (int i = list.length - 1; i > 0; i--) {
// 将堆顶节点和当前未经排序的子序列的最后一个元素交换位置
swap(list, 0, i);
headAdjust(list, 0, i);
}
}
/**
* 构造大根堆
*/
public static void headAdjust(int[] list, int parent, int length) {
// 保存当前父节点
int temp = list[parent];
// 得到左孩子节点
int leftChild = 2 * parent + 1;
while (leftChild < length) {
// 如果parent有右孩子，则要判断左孩子是否小于右孩子
if (leftChild + 1 < length && list[leftChild] < list[leftChild + 1]) {
leftChild++;
}
// 父亲节点大于子节点，就不用做交换
if (temp >= list[leftChild]) {
break;
}
// 将较大子节点的值赋给父亲节点
list[parent] = list[leftChild];
// 然后将子节点做为父亲节点
parent = leftChild;
// 找到该父亲节点较小的左孩子节点
leftChild = 2 * parent + 1;
}
// 最后将temp值赋给较大的子节点，以形成两值交换
list[parent] = temp;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int top, int last) {
int temp = list[top];
list[top] = list[last];
list[last] = temp;
}
直接插入排序
直接插入排序的基本思想是：每次从无序序列中取出第一个元素插入到已经排好序的有序序列中，从而得到一个新的，数量加1的有序序列。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/**
* 直接插入排序算法
*/
public static void insertSort(int[] list) {
// 从无序序列中取出第一个元素 (注意无序序列是从第二个元素开始的)
for (int i = 1; i < list.length; i++) {
int temp = list[i];
int j;
// 遍历有序序列
// 如果有序序列中的元素比临时元素大，则将有序序列中比临时元素大的元素依次后移
for (j = i - 1; j >= 0 && list[j] > temp; j--) {
list[j + 1] = list[j];
}
// 将临时元素插入到腾出的位置中
list[j + 1] = temp;
}
}
