数据结构的定义
1、 Data_Structure，它是储存数据的一种结构体，在此结构中储存一些数据，而这些数据之间有一定的关系。
2、 而各数据元素之间的相互关系，又包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
3、 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。
数据结构在Java的语言体系中按逻辑结构可以分为两大类：线性数据结构和非线性数据结构。
线性数据结构
一维数组、线性表、栈、队列、串；
1. 数组
插入效率比较低,更新，删除效率也比较低，而按索引查询效率非常高,查询效率时间复杂度是1。
2. 线性表(链表)
线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的，链表的每一个节点都知道上一个节点、或者下一个节点是谁，通常用Node表示。常见的有顺序链表(LinkedList、Linked***)，单项链表（里面只有Node类），双向链表(两个Node类)，循环链表(多个Node类)等。
操作方法：插入效率比较高，插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了，如果实现的不好，需要整个链路找下去才能找到应该找的元素。所以常见的方法有：add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。
常见的Uitil有：LinkedList，LinkedMap等，而这两个JDK底层也做了N多优化，可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。
1、链表Linked List）
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
2、单向链表（Single-Linked List）
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历：
- 查询一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。
- 插入一个节点，对于单向链表，我们需要将插入位置的前节点的指针指向自己，而自己的指针指向下一个节点。
- 删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点即可。
单向链表的具体实现
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| public class SingleLinkedList {
private int size;
private Node head;
public SingleLinkedList(){
size = 0;
head = null;
}
private class Node{
private Object data;
private Node next;
public Node(Object data){
this.data = data;
}
}
public Object addHead(Object obj){
Node newHead = new Node(obj);
if(size == 0){
head = newHead;
}else{
newHead.next = head;
head = newHead;
}
size++;
return obj;
}
public Object deleteHead(){
Object obj = head.data;
head = head.next;
size--;
return obj;
}
public Node find(Object obj){
Node current = head;
int tempSize = size;
while(tempSize > 0){
if(obj.equals(current.data)){
return current;
}else{
current = current.next;
}
tempSize--;
}
return null;
}
public boolean delete(Object value){
if(size == 0){
return false;
}
Node current = head;
Node previous = head;
while(current.data != value){
if(current.next == null){
return false;
}else{
previous = current;
current = current.next;
}
}
if(current == head){
head = current.next;
size--;
}else{
previous.next = current.next;
size--;
}
return true;
}
public boolean isEmpty(){
return (size == 0);
}
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{
System.out.println("[]");
}
}
}
|
2、 用单向链表实现栈
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
| public class StackSingleLink{
private SingleLinkedList link;
public StackSingleLink(){
link = new SingleLinkedList();
}
public void push(Object obj){
link.addHead(obj);
}
public Object pop(){
Object obj = link.deleteHead();
return obj;
}
public boolean isEmpty(){
return link.isEmpty();
}
public void display(){
link.display();
}
}
|
3、双端链表
对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。
双端链表的具体实现
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| public class DoublePointLinkedList {
private Node head;
private Node tail;
private int size;
private class Node{
private Object data;
private Node next;
public Node(Object data){
this.data = data;
}
}
public DoublePointLinkedList(){
size = 0;
head = null;
tail = null;
}
public void addHead(Object data){
Node node = new Node(data);
if(size == 0){
head = node;
tail = node;
size++;
}else{
node.next = head;
head = node;
size++;
}
}
public void addTail(Object data){
Node node = new Node(data);
if(size == 0){
head = node;
tail = node;
size++;
}else{
tail.next = node;
tail = node;
size++;
}
}
public boolean deleteHead(){
if(size == 0){
return false;
}
if(head.next == null){
head = null;
tail = null;
}else{
head = head.next;
}
size--;
return true;
}
public boolean isEmpty(){
return (size ==0);
}
public int getSize(){
return size;
}
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{
System.out.println("[]");
}
}
}
|
用双端链表实现队列
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
| public class QueueLinkedList {
private DoublePointLinkedList dp;
public QueueLinkedList(){
dp = new DoublePointLinkedList();
}
public void insert(Object data){
dp.addTail(data);
}
public void delete(){
dp.deleteHead();
}
public boolean isEmpty(){
return dp.isEmpty();
}
public int getSize(){
return dp.getSize();
}
public void display(){
dp.display();
}
}
|
有序链表
前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。
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 class OrderLinkedList {
private Node head;
private class Node{
private int data;
private Node next;
public Node(int data){
this.data = data;
}
}
public OrderLinkedList(){
head = null;
}
public void insert(int value){
Node node = new Node(value);
Node pre = null;
Node current = head;
while(current != null && value > current.data){
pre = current;
current = current.next;
}
if(pre == null){
head = node;
head.next = current;
}else{
pre.next = node;
node.next = current;
}
}
public void deleteHead(){
head = head.next;
}
public void display(){
Node current = head;
while(current != null){
System.out.print(current.data+" ");
current = current.next;
}
System.out.println("");
}
}
|
双向链表
我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| public class TwoWayLinkedList {
private Node head;
private Node tail;
private int size;
private class Node{
private Object data;
private Node next;
private Node prev;
public Node(Object data){
this.data = data;
}
}
public TwoWayLinkedList(){
size = 0;
head = null;
tail = null;
}
public void addHead(Object value){
Node newNode = new Node(value);
if(size == 0){
head = newNode;
tail = newNode;
size++;
}else{
head.prev = newNode;
newNode.next = head;
head = newNode;
size++;
}
}
public void addTail(Object value){
Node newNode = new Node(value);
if(size == 0){
head = newNode;
tail = newNode;
size++;
}else{
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
size++;
}
}
public Node deleteHead(){
Node temp = head;
if(size != 0){
head = head.next;
head.prev = null;
size--;
}
return temp;
}
public Node deleteTail(){
Node temp = tail;
if(size != 0){
tail = tail.prev;
tail.next = null;
size--;
}
return temp;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return (size == 0);
}
public void display(){
if(size >0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else{
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else{
System.out.println("[]");
}
}
}
|
总结
上面我们讲了各种链表，每个链表都包括一个LinikedList对象和许多Node对象，LinkedList对象通常包含头和尾节点的引用，分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部分data，以及对上一个节点的引用prev和下一个节点的引用next，只有下一个节点的引用称为单向链表，两个都有的称为双向链表。next值为null则说明是链表的结尾，如果想找到某个节点，我们必须从第一个节点开始遍历，不断通过next找到下一个节点，直到找到所需要的。栈和队列可以用数组来实现，也可以用链表实现。
3. 栈 （stack）
先进后出，后进先出！，实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈，pop()出栈。
java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构，就是线程栈，来保证当前线程的执行顺序。
4. 队列
队列是一种特殊的线性数据结构，队列只能允许在队头，队尾进行添加和查询等相关操作。队列又有单项有序队列，双向队列，阻塞队列等。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out） 线性表。
Queue这种数据结构注定了基本操作方法有：add(E e)加入队列，remove(),poll()等方法。
队列在Java语言环境中是使用频率相当高的数据结构，所有其实现的类也很多来满足不同场景。
线程池，连接池、消息队列等应用广泛。
队列的实现
一、基于数组的Queue实现
一般情况下，对于Queue而言，最核心的操作是：插入队列(enqueue)、移出队列(dequeue)。因为在队列中，插入操作是插入到队列的最后，而移出操作是移出队列的头部元素。因此我们通常会使用两个变量front（队头指针） 和**rear（队尾指针）** 记录当前元素的位置。
假设我们有一个容量有限队列，用于存放字母，如下图所示：
当我们要插入一个元素时，因为总是插入到队列的最尾部，所以插入的位置是rear+1的位置。
当我们要移出一个元素时，是从队头指针front的位置开始移除(因为Queue头部的元素是最先加入进来的，根据FIFO原则，应该最先移除)。当移除一个元素之后，front应该加1，因为移出一个元素之后，下一个元素就变成了第一个元素。例如现在我们移出了5个元素：
当移出5个元素之后，队头指针就移动到了字母F的位置，前五个位置空下来了。队尾指针rear不变。
现在问题来了：队列头部移出的几个元素，位置空下来了。当我们添加元素的时候，从队尾开始加，当添加到最后一个位置时，怎么办？不让添加时不合理的，毕竟前几个位置已经空下来了。我们的期望是，当一个位置上的元素被移出之后，这个位置是可以被重复使用的。而我们这里讨论的是有限容量的数据，如果我们还继续添加元素，那么就要往队列头部来添加。
这实际上就涉及到了循环队列的概念。也就是当队尾指针到了数组的最后一个下标时，下一个位置应该就是数组的首部。
因此，当队尾指针指向数组顶端的时候，我们要将队尾指针(rear)重置为-1，此时再加1，就是0，也就是数组顶端例。如我们又添加了5个字母，那么结果应该如下图：
java 基于数组实现Queue
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| public class MyQueue {
private Object[] queArray;
private int maxSize;
private int front;
private int rear;
private int nItems;
public MyQueue(int s){
maxSize = s;
queArray = new Object[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
public void insert(int value){
if(isFull()){
System.out.println("队列已满！！！");
}else{
if(rear == maxSize -1){
rear = -1;
}
queArray[++rear] = value;
nItems++;
}
}
public Object remove(){
Object removeValue = null ;
if(!isEmpty()){
removeValue = queArray[front];
queArray[front] = null;
front++;
if(front == maxSize){
front = 0;
}
nItems--;
return removeValue;
}
return removeValue;
}
public Object peekFront(){
return queArray[front];
}
public boolean isFull(){
return (nItems == maxSize);
}
public boolean isEmpty(){
return (nItems ==0);
}
public int getSize(){
return nItems;
}
}
|
java中的队列Queue
ConcurrentLinkedQueue：
- ConcurrentLinkedQueue是由链表结构组成的线程安全的先进先出无界队列。
- 当多线程要共享访问集合时，ConcurrentLinkedQueue是一个比较好的选择。
- 不允许插入null元素
- 支持非阻塞地访问并发安全的队列，不会抛出ConcurrentModifiationException异常。
阻塞队列(BlockingQueue)
阻塞队列特点:
阻塞队列的特点就在于阻塞，它可以阻塞线程，让生产者消费者得以平衡，阻塞队列中有两个关键方法 Put 和 Take 方法
Take : 方法的功能是获取并移除队列的头结点，通常在队列里有数据的时候是可以正常移除的。可是一旦执行 take 方法的时候，队列里无数据，则阻塞，直到队列里有数据。一旦队列里有数据了，就会立刻解除阻塞状态，并且取到数据。
**Put:**方法插入元素时，如果队列没有满，那就和普通的插入一样是正常的插入，但是如果队列已满，那么就无法继续插入，则阻塞，直到队列里有了空闲空间。如果后续队列有了空闲空间，比如消费者消费了一个元素，那么此时队列就会解除阻塞状态，并把需要添加的数据添加到队列中。
常见的阻塞队列成员:
1、ArrayBlockingQueue: 数组结构的有界阻塞队列，此队列按照先进先出(FIFO)原则对元素进行排序，同时支持公平锁和非公平锁。它的线程安全性由 ReentrantLock 来实现的。
1
2
| public ArrayBlockingQueue(int capacity) {...}
public ArrayBlockingQueue(int capacity, boolean fair) {...}
|
- 如上所示，ArrayBlockingQueue 提供的构造函数中，我们需要指定队列的长度，同时我们也可以设置队列是都是公平的，当我们设置了容量后就不能再修改了，符合数组的特性，此队列按照先进先出（FIFO）的原则对元素进行排序。
- 和 ReentrantLock 一样，如果 ArrayBlockingQueue 被设置为非公平的，那么就存在插队的可能；如果设置为公平的，那么等待了最长时间的线程会被优先处理，其他线程不允许插队，不过这样的公平策略同时会带来一定的性能损耗，因为非公平的吞吐量通常会高于公平的情况。
2、LinkedBlockingQueue: 链表结构的有界阻塞队列，队列的默认大小为 Integer.MAX_VALUE，这个值是非常大的，几乎无法达到，对此我们可以认为这个队列基本属于一个无界队列（也又认为是有界 队列）也是按照先进先出原则对元素进行排序的。它的线程安全性由 ReentrantLock 来实现的。
3、PriorityBlockingQueue: 支持线程优先级排序的无界阻塞队列。默认自然序进行排序，也可以自定义实现compareTo()方法来指定元素排序规则，不能保证同优先级元素的顺序。
4、DelayQueue: 实现PriorityBlockingQueue优先级排序的延迟阻塞队列，在创建元素时，可以指定多久才能从队列中获取当前元素。只有延时期满后才能从队列中获取元素。
5、SynchronousQueue: 不存储元素的阻塞队列，每一个put操作必须等待take操作，否则不能添加元素。支持公平锁和非公平锁。
6、LinkedBlockingDeque： 一个由链表结构组成的双向阻塞队列。队列头部和尾部都可以添加和移除元素，多线程并发时，可以将锁的竞争最多降到一半。
这些阻塞队列的实现类是都是实现了BlockingQueue接口
5. 串
串：也称字符串，是由N个字符组成的优先序列。在Java里面就是指String, 而String里面是由chat[]来进行储存。
KMP算法： 这个算法一定要牢记，Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是：在字符串比对的时候，主串的比较位置不需要回退的问题。
非线性结构
1、多维数组
一维数组前面咱也提到了，多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类，而java里面tree和图底层的native方法用了多维数组来储存。
2、集合
由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。
3、树
前面介绍数组的数据结构，我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空间，平均来讲要移动N/2次，这是很费时的。同理，删除数据也是。（数组插入、删除慢），
也介绍了另外一种数据结构——链表，链表的插入和删除很快，我们只需要改变一些引用值就行了，但是查找数据却很慢了，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均需要比较N/2次。
那么我们就希望一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是 树 诞生了。
特点：
- 在一个树结构中，有且仅有一个结点没有直接父节点，它就是根节点。
- 除了根节点，其他结点有且只有一个直接父节点
- 每个结点可以有任意多个直接子节点。
根据树的特点又将树分为以下几种：
1) 自由树/普通树：对子节点没有任何约束。
2) 二叉树：每个节点最多含有两个子节点的树称为二叉树。
2.1) 一般二叉树：每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。
2.2) 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
1、 满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树；
2、 在完全二叉树中，若某个节点没有左子树，则一定没有右子树；
2.3) 满二叉树：所有的节点都是二叉的二叉树成为满二叉树。
3) 二叉搜索树/BST：binary search tree,又称二叉排序树、二叉查找树。是有序的。要点：如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值。
二叉搜索树作为一种数据结构，那么它是如何工作的呢？ 它查找一个节点，插入一个新节点，以及删除一个节点，遍历树等工作效率如何，下面我们来一一介绍。
二叉树节点类：
1
2
3
4
5
6
7
8
9
| public class Node {
private Object data;
private Node leftChild;
private Node rightChild;
public void display(){
System.out.println(data);
}
}
|
二叉树的具体方法：
1
2
3
4
5
6
7
8
9
| public interface Tree {
public Node find(Object key);
public boolean insert(Object key);
public boolean delete(Object key);
}
|
查找节点
查找某个节点，我们必须从根节点开始遍历。
1、 查找值比当前节点值大，则搜索右子树；
2、 查找值等于当前节点值，停止搜索（终止条件）；
3、 查找值小于当前节点值，则搜索左子树；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public Node find(int key) {
Node current = root;
while(current != null){
if(current.data > key){
current = current.leftChild;
}else if(current.data < key){
current = current.rightChild;
}else{
return current;
}
}
return null;
}
|
插入节点
要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性，待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。
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
|
public boolean insert(int data) {
Node newNode = new Node(data);
if(root == null){
root = newNode;
return true;
}else{
Node current = root;
Node parentNode = null;
while(current != null){
parentNode = current;
if(current.data > data){
current = current.leftChild;
if(current == null){
parentNode.leftChild = newNode;
return true;
}
}else{
current = current.rightChild;
if(current == null){
parentNode.rightChild = newNode;
return true;
}
}
}
}
return false;
}
|
查找最大值和最小值
这没什么好说的，要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public Node findMax(){
Node current = root;
Node maxNode = current;
while(current != null){
maxNode = current;
current = current.rightChild;
}
return maxNode;
}
public Node findMin(){
Node current = root;
Node minNode = current;
while(current != null){
minNode = current;
current = current.leftChild;
}
return minNode;
}
|
删除节点
删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。
1、该节点是叶节点（没有子节点）
2、该节点有一个子节点
3、该节点有两个子节点
下面我们分别对这三种情况进行讲解。
1、 删除没有子节点的节点
要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。要删除的节点依然存在，但是它已经不是树的一部分了，由于Java语言的垃圾回收机制，我们不需要非得把节点本身删掉，一旦Java意识到程序不在与该节点有关联，就会自动把它清理出存储器。
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
| @Override
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = false;
while(current.data != key){
parent = current;
if(current.data > key){
isLeftChild = true;
current = current.leftChild;
}else{
isLeftChild = false;
current = current.rightChild;
}
if(current == null){
return false;
}
}
if(current.leftChild == null && current.rightChild == null){
if(current == root){
root = null;
}else if(isLeftChild){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
return true;
}
return false;
}
|
删除节点，我们要先找到该节点，并记录该节点的父节点。在检查该节点是否有子节点。如果没有子节点，接着检查其是否是根节点，如果是根节点，只需要将其设置为null即可。如果不是根节点，是叶节点，那么断开父节点和其的关系即可。
2、 删除有一个子节点的节点
删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
if(current.leftChild == null && current.rightChild != null){
if(current == root){
root = current.rightChild;
}else if(isLeftChild){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
return true;
}else{
if(current == root){
root = current.leftChild;
}else if(isLeftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
return true;
}
|
3、 删除有两个子节点的节点
当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？
我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。用后继节点来代替删除的节点，显然该二叉搜索树还是有序的。（这里用后继节点代替，如果该后继节点自己也有子节点，我们后面讨论。）
那么如何找到删除节点的中序后继节点呢？其实我们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。
后继节点也就是：比删除节点大的最小节点。
算法：程序找到删除节点的右节点，(注意这里前提是删除节点存在左右两个子节点，如果不存在则是删除情况的前面两种)，然后转到该右节点的左子节点，依次顺着左子节点找下去，最后一个左子节点即是后继节点；如果该右节点没有左子节点，那么该右节点便是后继节点。
需要确定后继节点没有子节点，如果后继节点存在子节点，那么又要分情况讨论了。
*1、* 后继节点是删除节点的右子节点
这种情况简单，只需要将后继节点表示的子树移到被删除节点的位置即可！
*2、* 后继节点是删除节点的右子节点的左子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
if(successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
|
4、 删除有必要吗？
通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，当该字段为true时，表示该节点已经删除，反正没有删除。那么我们在做比如find()等操作的时候，要先判断isDelete字段是否为true。这样删除的节点并不会改变树的结构。
1
2
3
4
5
6
| public class Node {
int data;
Node leftChild;
Node rightChild;
boolean isDelete;
}
|
二叉树的效率
从前面的大部分对树的操作来看，都需要从根节点到下一层一层的查找。
一颗满树，每层节点数大概为2n-1，那么最底层的节点个数比树的其它节点数多1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。
总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。
在有1000000 个数据项的无序数组和链表中，查找数据项平均会比较500000 次，但是在有1000000个节点的二叉树中，只需要20次或更少的比较即可。
有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要20次或更少比较，在加上很短的时间来连接数据项。
同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他，然后在花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。
所以，树对所有常用数据结构的操作都有很高的效率。
遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。
完整的BinaryTree代码
Node.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Node {
int data;
Node leftChild;
Node rightChild;
boolean isDelete;
public Node(int data){
this.data = data;
}
public void display(){
System.out.println(data);
}
}
|
Tree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public interface Tree {
public Node find(int key);
public boolean insert(int data);
public void infixOrder(Node current);
public void preOrder(Node current);
public void postOrder(Node current);
public Node findMax();
public Node findMin();
public boolean delete(int key);
}
|
BinaryTree.java
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
| public class BinaryTree implements Tree {
private Node root;
public Node find(int key) {
Node current = root;
while(current != null){
if(current.data > key){
current = current.leftChild;
}else if(current.data < key){
current = current.rightChild;
}else{
return current;
}
}
return null;
}
public boolean insert(int data) {
Node newNode = new Node(data);
if(root == null){
root = newNode;
return true;
}else{
Node current = root;
Node parentNode = null;
while(current != null){
parentNode = current;
if(current.data > data){
current = current.leftChild;
if(current == null){
parentNode.leftChild = newNode;
return true;
}
}else{
current = current.rightChild;
if(current == null){
parentNode.rightChild = newNode;
return true;
}
}
}
}
return false;
}
public void infixOrder(Node current){
if(current != null){
infixOrder(current.leftChild);
System.out.print(current.data+" ");
infixOrder(current.rightChild);
}
}
public void preOrder(Node current){
if(current != null){
System.out.print(current.data+" ");
infixOrder(current.leftChild);
infixOrder(current.rightChild);
}
}
public void postOrder(Node current){
if(current != null){
infixOrder(current.leftChild);
infixOrder(current.rightChild);
System.out.print(current.data+" ");
}
}
public Node findMax(){
Node current = root;
Node maxNode = current;
while(current != null){
maxNode = current;
current = current.rightChild;
}
return maxNode;
}
public Node findMin(){
Node current = root;
Node minNode = current;
while(current != null){
minNode = current;
current = current.leftChild;
}
return minNode;
}
@Override
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = false;
while(current.data != key){
parent = current;
if(current.data > key){
isLeftChild = true;
current = current.leftChild;
}else{
isLeftChild = false;
current = current.rightChild;
}
if(current == null){
return false;
}
}
if(current.leftChild == null && current.rightChild == null){
if(current == root){
root = null;
}else if(isLeftChild){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
return true;
}else if(current.leftChild == null && current.rightChild != null){
if(current == root){
root = current.rightChild;
}else if(isLeftChild){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
return true;
}else if(current.leftChild != null && current.rightChild == null){
if(current == root){
root = current.leftChild;
}else if(isLeftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
return true;
}else{
Node successor = getSuccessor(current);
if(current == root){
root= successor;
}else if(isLeftChild){
parent.leftChild = successor;
}else{
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return false;
}
public Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
if(successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.insert(50);
bt.insert(20);
bt.insert(80);
bt.insert(10);
bt.insert(30);
bt.insert(60);
bt.insert(90);
bt.insert(25);
bt.insert(85);
bt.insert(100);
bt.delete(10);
bt.delete(30);
bt.delete(80);
System.out.println(bt.findMax().data);
System.out.println(bt.findMin().data);
System.out.println(bt.find(100));
System.out.println(bt.find(200));
}
}
|
总结
树是由边和节点构成，根节点是树最顶端的节点，它没有父节点；二叉树中，最多有两个子节点；某个节点的左子树每个节点都比该节点的关键字值小，右子树的每个节点都比该节点的关键字值大，那么这种树称为二叉搜索树，其查找、插入、删除的时间复杂度都为logN；可以通过前序遍历、中序遍历、后序遍历来遍历树，前序是根节点-左子树-右子树，中序是左子树-根节点-右子树，后序是左子树-右子树-根节点；删除一个节点只需要断开指向它的引用即可。
3.1) 二叉平衡树：二叉搜索树，是有序的排序树，但左右两边包括子节点不一定平衡，而二叉平衡树是排序树的一种，并且加点条件，就是任意一个节点的两个叉的深度差不多（比如差值的绝对值小于某个常数，或者一个不能比另一个深出去一倍之类的）。这样的树可以保证二分搜索任意元素都是O(log n)的，一般还附带带有插入或者删除某个元素也是O(log n)的的性质。
为了实现，二叉平衡树又延伸出来了一些算法，业界常见的有AVL、和红黑算法，所以又有以下两种树：
3.1.1) AVL树：最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
3.1.2) 红黑树：通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。
二叉搜索树作为一种数据结构，其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。但是我们说这个时间复杂度是在平衡的二叉搜索树上体现的，也就是如果插入的数据是随机的，则效率很高，但是如果插入的数据是有序的，比如从小到大的顺序【10,20,30,40,50】插入到二叉搜索树中：
从大到小就是全部在左边，这和链表没有任何区别了，这种情况下查找的时间复杂度为O(N)，而不是O(logN)。当然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(N)和O(logN)之间，这取决于树的不平衡程度。
那么为了能够以较快的时间O(logN)来搜索一棵树，我们需要保证树总是平衡的（或者大部分是平衡的），也就是说每个节点的左子树节点个数和右子树节点个数尽量相等。红-黑树的就是这样的一棵平衡树，对一个要插入的数据项（删除也是），插入例程要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树的结构，从而保持树的平衡。
红黑树的5条性质：
**1、** 每个结点要么是红的，要么是黑的。
**2、** 根结点是黑的。
**3、** 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
**4、** 如果一个结点是红的，那么它的俩个儿子都是黑的。
**5、** 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
红黑树和平衡二叉树的区别
1、 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单；
2、 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知；
红-黑树的自我修正
红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。
1、 改变节点颜色
新插入的节点为15，一般新插入颜色都为红色，那么我们发现直接插入会违反规则3，改为黑色却发现违反规则4。这时候我们将其父节点颜色改为黑色，父节点的兄弟节点颜色也改为黑色。通常其祖父节点50颜色会由黑色变为红色，但是由于50是根节点，所以我们这里不能改变根节点颜色。
*2、* 右旋
首先要说明的是节点本身是不会旋转的，旋转改变的是节点之间的关系，选择一个节点作为旋转的顶端，如果做一次右旋，这个顶端节点会向下和向右移动到它右子节点的位置，它的左子节点会上移到它原来的位置。右旋的顶端节点必须要有左子节点。
*3、* 左旋
左旋的顶端节点必须要有右子节点。
注意：我们改变颜色也是为了帮助我们判断何时执行什么旋转，而旋转是为了保证树的平衡。光改变节点颜色是不能起到任何作用的，旋转才是关键的操作，在新增节点或者删除节点之后，可能会破坏二叉树的平衡，那么何时执行旋转以及执行什么旋转，这是我们需要重点关注的。
3、左旋和右旋代码
*1、* 节点类
节点类和二叉树的节点类差不多，只不过在其基础上增加了一个 boolean 类型的变量来表示节点的颜色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class RBNode<T extends Comparable<T>> {
boolean color;
T key;
RBNode<T> left;
RBNode<T> right;
RBNode<T> parent;
public RBNode(boolean color,T key,RBNode<T> parent,RBNode<T> left,RBNode<T> right){
this.color = color;
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey(){
return key;
}
public String toString(){
return ""+key+(this.color == RED ? "R":"B");
}
}
|
*2、* 左旋的具体实现
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
|
private void leftRotate(RBNode<T> x){
RBNode<T> y = x.right;
x.right = y.left;
if(y.left != null){
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == null){
this.root = y;
}else{
if(x == x.parent.left){
x.parent.left = y;
}else{
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
|
*3、* 右旋的具体实现
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
|
private void rightRotate(RBNode<T> y){
RBNode<T> x = y.left;
y.left = x.right;
if(x.right != null){
x.right.parent = y;
}
x.parent = y.parent;
if(y.parent == null){
this.root = x;
}else{
if(y == y.parent.left){
y.parent.left = x;
}else{
y.parent.right = x;
}
}
x.right = y;
y.parent = x;
}
|
4、插入操作
和二叉树的插入操作一样，都是得先找到插入的位置，然后再将节点插入。先看看插入的前段代码：
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
|
public void insert(T key){
RBNode<T> node = new RBNode<T>(RED, key, null, null, null);
if(node != null){
insert(node);
}
}
public void insert(RBNode<T> node){
RBNode<T> current = null;
RBNode<T> x = this.root;
while(x != null){
current = x;
int cmp = node.key.compareTo(x.key);
if(cmp < 0){
x = x.left;
}else{
x = x.right;
}
}
node.parent = current;
if(current != null){
int cmp = node.key.compareTo(current.key);
if(cmp < 0){
current.left = node;
}else{
current.right = node;
}
}else{
this.root = node;
}
insertFixUp(node);
}
|
这与二叉搜索树中实现的思路一样，这里不再赘述，主要看看方法里面最后一步 insertFixUp(node) 操作。因为插入后可能会导致树的不平衡，insertFixUp(node) 方法里主要是分情况讨论，分析何时变色，何时左旋，何时右旋。我们先从理论上分析具体的情况，然后再看insertFixUp(node) 的具体实现。
如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可；如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；但是遇到如下三种情况，我们就要开始变色和旋转了：
1、 插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。
2、 插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。
3、 插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的左子节点。
下面我们挨个分析这三种情况都需要如何操作，然后给出实现代码。
在下面的讨论中，使用N,P,G,U表示关联的节点。N(now)表示当前节点，P(parent)表示N的父节点，U(uncle)表示N的叔叔节点，G(grandfather)表示N的祖父节点，也就是P和U的父节点。
对于情况1：插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。此时，肯定存在祖父节点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况，另一种情况自然也与之对应。这里考虑父节点是其祖父节点的左子节点的情况，如下左图所示：
对于这种情况，我们要做的操作有：将当前节点(4) 的父节点(5) 和叔叔节点(8) 涂黑，将祖父节点(7)涂红,变成了上有图所示的情况。再将当前节点指向其祖父节点，再次从新的当前节点开始算法（具体看下面的步骤）。这样上右图就变成情况2了。
对于情况2：插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。我们要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。完成后如左下图所示，这样左下图就变成情况3了。
对于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。最后把根节点涂黑，整个红-黑树重新恢复了平衡，如右上图所示。至此，插入操作完成！
我们可以看出，如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，当然咯，实际中可能不一定会从情况1发生，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。
至此，我们完成了全部的插入操作。下面我们看看insertFixUp方法中的具体实现（可以结合上面的分析图，更加利与理解）：
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
56
57
58
59
60
| private void insertFixUp(RBNode<T> node){
RBNode<T> parent,gparent;
while(((parent = parentOf(node)) != null) && isRed(parent)){
gparent = parentOf(parent);
if(parent == gparent.left){
RBNode<T> uncle = gparent.right;
if(uncle != null && isRed(uncle)){
setBlack(parent);
setBlack(gparent);
setRed(gparent);
node = gparent;
continue;
}
if(node == parent.right){
leftRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
}else{
RBNode<T> uncle = gparent.left;
if(uncle != null && isRed(uncle)){
setBlack(parent);
setBlack(uncle);
setRed(gparent);
node = gparent;
continue;
}
if(node == parent.left){
rightRotate(parent);
RBNode<T> tmp = parent;
parent = node;
node = tmp;
}
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
setBlack(root);
}
|
5、删除操作
上面探讨完了红-黑树的插入操作，接下来讨论删除，红-黑树的删除和二叉查找树的删除是一样的，只不过删除后多了个平衡的修复而已。我们先来回忆一下二叉搜索树的删除：
1、 如果待删除的节点没有子节点，那么直接删除即可。
2、 如果待删除的节点只有一个子节点，那么直接删掉，并用其子节点去顶替它。
3、 如果待删除的节点有两个子节点，这种情况比较复杂：首先找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。每一步中也会有不同的情况。
实际上，删除过程太复杂了，很多情况下会采用在节点类中添加一个删除标记，并不是真正的删除节点。详细的删除我们这里不做讨论。
6、红黑树的效率
红黑树的查找、插入和删除时间复杂度都为O(log2N)，额外的开销是每个节点的存储空间都稍微增加了一点，因为一个存储红黑树节点的颜色变量。插入和删除的时间要增加一个常数因子，因为要进行旋转，平均一次插入大约需要一次旋转，因此插入的时间复杂度还是O(log2N),(时间复杂度的计算要省略常数)，但实际上比普通的二叉树是要慢的。
大多数应用中，查找的次数比插入和删除的次数多，所以应用红黑树取代普通的二叉搜索树总体上不会有太多的时间开销。而且红黑树的优点是对于有序数据的操作不会慢到O(N)的时间复杂度。
4) B-tree：又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子（m>=2）。它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。
5) B+tree：又称B+。是B-树的变体，也是一种多路搜索树。
树总结：
树在Java里面应用的也比较多。非排序树，主要用来做数据储存和展示。而排序树，主要用来做算法和运算，HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。
树的遍历
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。
*1、* 中序遍历:左子树——》根节点——》右子树
*2、* 前序遍历:根节点——》左子树——》右子树
3、 后序遍历:左子树——》右子树——》根节点**
4、Hash
Hash概念：
1、 Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。
2、 所谓的Hash算法都是散列算法，把任意长度的输入，变换成固定长度的输出，该输出就是散列值.（如：MD5,SHA1,加解密算法等）
3、 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash表：
1、 Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表。而Hash表就是综合了这两种数据结构。
2、 如：HashTable,HashMap。这个时候就得提一下HashMap的原理了，默认16个数组储存，通过Hash值取模放到不同的桶里面去。（注意：JDK1.8此处算法又做了改进，数组里面的值会演变成树形结构
3、 哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”。
一致性Hash：
1、 我们查看一下HashMap的原理，其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的，所有在分布式环境下，应运而生了一致性Hash算法。
2、 用意和hashCode的用意一样，只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。
3、 而一致性Hash需要注意的就是默认分配的桶比较多些，而当其中一台机器挂了，影响的面比较小一些。
4、 需要注意的是，相同的内容算出来的hash一定是一样的。既：幂等性。
1) 常见的hash函数
直接定址法
- 取关键字或关键字的某个线性函数值为散列地址。
- 即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
除留余数法
- 取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
- 即 H(key) = key % p, p < m。
数字分析法
- 当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
- 仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
平方取中法
- 先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
- 随机分布的关键字，得到的散列地址也是随机分布的。
折叠法（叠加法）
- 将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
- 用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。
随机数法
- 选择一个随机函数，把关键字的随机函数值作为它的哈希值。
- 通常当关键字的长度不等时用这种方法。
构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。
通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。
如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。
2) 哈希冲突的解决
选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。
常用的主要有两种方法解决冲突：
1.链接法（拉链法）
拉链法解决冲突的做法是：
将所有关键字为同义词的结点链接在同一个单链表中。
若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。
凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。
T中各分量的初值均应为空指针。
在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。
2.开放定址法
用开放定址法解决冲突的做法是：
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
简单的说：当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
a.线性探查法
hi=(h(key)+i) ％ m ，0 ≤ i ≤ m-1
基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。
b.二次探查法
hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1
基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。
缺点是无法探查到整个散列空间。
c.双重散列法
hi=(h(key)+i*h1(key)) ％ m，0 ≤ i ≤ m-1
基本思想是：
探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。
该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。
定义h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。
该方法是开放定址法中最好的方法之一。
5.各个数据结构的比较
排序算法的评价标准
时间复杂度
时间复杂度是一个函数，定性描述算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度通常用大写 O 符号来表示，不包括这个函数的低阶项和首项系数。
一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，使用 T(n) 表示，如果有某个辅助函数 f(n)，使当 n 趋于无穷大时，T(n)/f(n) 的极限值为不等于 0 的常数，则称 f(n) 是 T(n) 的同量级函数。记作 T(n) = O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度
时间频度
一个算法花费的时间与算法中语句的执行次数成正比，执行次数多花费时间就多。一个算法中语句执行次数称为语句频度或者时间频度 T(n)
计算时间复杂度的方法：
- 使用常数 1 代替运行时间中的所有加法常数
- 修改后的运行次数函数中，只保留最高阶项
- 去除最高阶项的系数
常见的时间复杂度
1、 常数阶O(1)；
对于一个算法，T(n) 的上界与输入大小无关，则称其具有常数时间，记作 O(1) 时间。
2、 对数阶O(㏒2n)；
㏒a n 和 ㏒b n 只有一个常数因子不同，这个因子在在大 O 记法中被丢弃，因此记作 O(㏒n)，不论对数的底是多少，是对数时间算法的标准记法。
常见的对数时间的算法有二叉树的相关操作和二分搜索
3、 线性阶O(n)；
对于足够大的输入，运行时间增加的大小与输入成线性关系。
4、 线性对数阶O(n㏒2n)；
线性对数比线性时间要快，但是对于任何含有 n，并且 n 的幂指数大于 1 的多项式时间来说，线性对数时间却增长很慢
5、 平方阶O(n^2)；
6、 立方阶O(n^3)；
7、 k次方阶O(n^k)；
8、 指数阶O(2^n)；
常见时间复杂度由小到大依次为：O(1) < O( ㏒2 n) < O(n) < O(n㏒2 n) < O(n^2) < O(n^3) < O(n^k) < O(2^n)，随着问题规模 n 的不断增大，时间复杂度不断增大，算法的执行效率越低。
平均时间复杂度和最坏时间复杂度
1、 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间；
2、 最坏情况下的时间复杂度称为最坏时间复杂度一般说时间复杂度是最坏情况下的时间复杂度；
3、 平均时间复杂度和最坏时间复杂度是否一致和算法有关；
空间复杂度
基本介绍
- 算法的空间复杂度（Space Complexity）定义为该算法所耗费的存储空间
- 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记作 S(n) = O(f(n))
- 分析算法主要讨论时间复杂度，一些缓存产品（Redis，Memcache）和算法（基数排序）使用空间换时间
量度
一个算法的空间复杂度 S(n) 定义为该算法所耗费的存储空间，也是问题规模 n 的函数，渐进空间复杂度也简称为空间复杂度。空间复杂度（SpaceComplexity）是对一个算法在运行过程中临时占用存储空间大小的量度。
一个算法在计算机存储器上占用的存储空间，包括存储算法本身占用的存储空间，算法的输入输出数据锁占用的存储空间和算法在运行过程中临时占用的存储空间三个方面。
分析
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
如果一个算法是递归算法，空间复杂度为递归所使用的堆栈空间的大小，它大于等于一次调用所分配的临时存储空间的大小乘以被调用的次数（递归调用次数加 1，这个 1 表示开始进行的一次非递归调用）
稳定性
稳定的算法在排序过程中不会改变元素彼此位置的相对次序，反之不稳定的排序算法经常会改变这个次序。稳定性算法中非常重要的影响选择的因素
排序算法
部分文档参考自：10大经典排序
1、冒泡排序
基本思想：
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个名词的由来很好理解，一般河水中的冒泡，水底刚冒出来的时候是比较小的，随着慢慢向水面浮起会逐渐增大，这物理规律我不作过多解释，大家只需要了解即可。
冒泡算法的运作规律如下：
1、 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
3、 针对所有的元素重复以上的步骤，除了最后一个。
4、 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1、冒泡排序普通版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static void sort(Integer [] arr, int len){
if(len <= 1){
return;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - i - 1; j++) {
if(arr[j] > arr[j + 1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
|
冒泡排序改良版：
如果说在一次冒泡中，没有发生相邻元素的交换，那说明待排序序列已经有序了，不管后面还剩下多少次冒泡，我们都不需要再进行冒泡下去了。这样是不是就减少冒泡的次数了呢
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
|
public static void sort(Integer [] arr, int len){
if(len <= 1){
return;
}
boolean flag = false;
for (int i = 0; i < len; i++) {
flag = false;
for (int j = 0; j < len - i - 1; j++) {
if(arr[j] > arr[j + 1]){
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = true;
}
}
System.out.println("第【" + (i + 1) + "】次冒泡");
if(!flag){
break;
}
}
}
|
冒泡排序解释：
冒泡排序是由两个for循环构成，第一个for循环的变量 i 表示总共需要多少轮比较，第二个for循环的变量 j 表示每轮参与比较的元素下标【0,1，……，length-i】，因为每轮比较都会出现一个最大值放在最右边，所以每轮比较后的元素个数都会少一个，这也是为什么 j 的范围是逐渐减小的。相信大家理解之后快速写出一个冒泡排序并不难。
冒泡排序性能分析：
假设参与比较的数组元素个数为 N，则第一轮排序有 N-1 次比较，第二轮有 N-2 次，如此类推，这种序列的求和公式为：
（N-1）+（N-2）+…+1 = N*（N-1）/2
当N 的值很大时，算法比较次数约为 N2/2次比较，忽略减1。
假设数据是随机的，那么每次比较可能要交换位置，可能不会交换，假设概率为50%，那么交换次数为 N2/4。不过如果是最坏的情况，初始数据是逆序的，那么每次比较都要交换位置。
交换和比较次数都和N2 成正比。由于常数不算大 O 表示法中，忽略 2 和 4，那么冒泡排序运行都需要 O(N2) 时间级别。
其实无论何时，只要看见一个循环嵌套在另一个循环中，我们都可以怀疑这个算法的运行时间为 O(N2)级，外层循环执行 N 次，内层循环对每一次外层循环都执行N次（或者几分之N次）。这就意味着大约需要执行N2次某个基本操作。
时间复杂度：最好O(n)；最坏O(n2)；平均O(n2)
空间复杂度：O(1)
稳定性：稳定
2、选择排序
选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
分为三步：
1、 从待排序序列中，找到关键字最小的元素
2、 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
3、 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static int[] choiceSort (int[] array){
for(int i = 0 ; i < array.length-1 ; i++){
int min = i;
for(int j = i+1 ; j < array.length ; j++){
if(array[j]<array[min]){
min = j;
}
}
if(i != min){
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
System.out.print("第"+(i+1)+"轮排序后的结果为:");
}
return array;
}
|
选择排序性能分析：
选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。
当N 值很大时，比较次数是主要的，所以和冒泡排序一样，用大O表示是O(N2) 时间级别。但是由于选择排序交换的次数少，所以选择排序无疑是比冒泡排序快的。当 N 值较小时，如果交换时间比选择时间大的多，那么选择排序是相当快的。
时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：不稳定
3、插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
插入排序还分为直接插入排序、二分插入排序、链表插入排序、希尔排序等等，这里我们只是以直接插入排序讲解，后面讲高级排序的时候会将其他的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static int[] insertSort (int[] array){
int j;
for(int i = 1 ; i < array.length ; i++){
int tmp = array[i];
j = i;
while(j > 0 && tmp < array[j-1]){
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
return array;
}
|
插入排序性能分析：
在第一轮排序中，它最多比较一次，第二轮最多比较两次，一次类推，第N轮，最多比较N-1次。因此有 1+2+3+…+N-1 = N*（N-1）/2。
假设在每一轮排序发现插入点时，平均只有全体数据项的一半真的进行了比较，我们除以2得到：N*（N-1）/4。用大O表示法大致需要需要 O(N2) 时间级别。
复制的次数大致等于比较的次数，但是一次复制与一次交换的时间耗时不同，所以相对于随机数据，插入排序比冒泡快一倍，比选择排序略快。
这里需要注意的是，如果要进行逆序排列，那么每次比较和移动都会进行，这时候并不会比冒泡排序快。
最好情况O(n)；最坏情况O(n2)；平均时间复杂度为：O(n2)
空间复杂度：O(1)
稳定性：稳定
总结：
上面讲的三种排序，冒泡、选择、插入用大 O 表示法都需要 O(N2) 时间级别。一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。
下面我们会讲解高级排序，大O表示法的时间级别将比O(N2)小。
4、希尔排序(shell Sort)
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。即先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序“时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。
算法步骤
1、 选择一个增量序列t1，t2，……，tk，其中ti>tj,tk=1；
2、 按增量序列个数k，对序列进行k趟排序；
3、 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度；
举例：[16，25，12，30，47，11，23，36，9，18，31]，共11个元素
第一趟：增量d=5, 我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：
1
2
3
| 16，25，12，30，47
11，23，36， 9，18
31
|
然后每列排序：
1
2
3
| 11，23，12，9， 18
16，25，36，30，47
31
|
所以得到的序列为 [11，23，12，9， 18，16，25，36，30，47，31]
第二趟：增量d=2，同理
1
2
3
4
5
6
| 11，23，
12， 9，
18，16，
25，36，
30，47，
31
|
按列排序并连接起来得：[11, 9, 12, 16, 18, 23, 25, 36, 30, 47, 31]
第三趟：增量d=1，即以1步长进行排序(即是简单的插入排序)
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public static void shellSort(int[] arr){
if(arr == null | arr.length ==0) return;
int temp;
for(int delta = arr.length/2; delta>=1; delta/=2){
for(int i=delta; i<arr.length; i++){
for(int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
swap(arr, j-delta, j);
}
}
}
}
|
时空复杂度
希尔排序在效率上比直接插入排序有很大的改进，但对希尔排序进行时间性能分析很难，原因是何种步长序列最优难以判定，通常认为其时间复杂度为O(n1.5)。
希尔排序的增量序列可以有多种取法，较优的增量序列的共同特征如下。
- 最后一个增量必须为。
- 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
时间效率： 当增量序列为d(k)=2t-k+1-1时，时间复杂度为O(n1.5）。
空间效率： O（1）
算法的稳定性： 不稳定
5、归并排序（MergeSort)
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
典型的是二路合并排序，将原始数据集分成两部分(不一定能够均分)，分别对它们进行排序，然后将排序后的子数据集进行合并，这是典型的分治法策略。
算法步骤
1、 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2、 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4、 重复步骤3直到某一指针达到序列尾；
5、 将另一序列剩下的所有元素直接复制到合并序列尾；
实现
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
| public class SortTest {
public static void mergeSort(int[] arr){
if(arr == null || arr.length < 2) return;
mSort(arr, 0, arr.length-1);
}
private static void mSort(int[] arr, int left, int right){
if(left<right){
int middle = (left+right)/2;
mSort(arr, left, middle);
mSort(arr, middle+1, right);
merge(arr, left, middle, right);
}
}
private static void merge(int[] arr, int left, int middle, int right){
int[] t = new int[right - left + 1];
int k = 0;
int i = left;
int j = middle+1;
while(i<=middle && j<=right){
if(arr[i] <= arr[j]){
t[k++] = arr[i++];
}else{
t[k++] = arr[j++];
}
}
while(i<=middle){
t[k++] = arr[i++];
}
while(j<=right){
t[k++] = arr[j++];
}
for(i=0;i<k;i++){
arr[left+i] = t[i];
}
}
public static void main(String[] args) {
int[] arr = {1,8,6,5,9,4,7,3,2,0};
mergeSort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
|
时间复杂度
在归并排序中，进行一趟归并需要的关键字比较次数和数据元素移动次数最多为n，需要归并的趟数log2n，故归并排序的时间复杂度为O(nlog2n)。归并排序需要长度等于序列长度为n的辅助存储单元，故归并排序的空间复杂度为O(n)。归并排序是稳定的排序算法。
时间复杂度：O(nlog2n)
空间复杂度：O(n)
稳定性：稳定
6、快速排序（quickSort）
快速排序是图灵奖得主C.R.A Hoare于1960年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法（Divide-and-Conquer Method）
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题组合为原问题的解。
算法步骤
利用分治法可将快速排序分为三步：
1、 从数列中挑出一个元素作为“基准”（pivot）；
2、 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边这个操作称为“分区操作”，分区操作结束后，基准元素所处的位置就是最终排序后它的位置；
3、 再对“基准”左右两边的子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
代码实现
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
| public class SortTest {
public static void quickSort(int[] arr){
if(arr == null || arr.length<2){
return;
}
quickSort(arr, 0, arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
if(l < r){
int p = partition(arr, l, r);
quickSort(arr, l, p-1);
quickSort(arr, p+1, r);
}
}
private static int partition(int[] arr, int l, int r) {
int pivot = arr[l];
while (l<r){
while(l<r && arr[r]>=pivot) r--;
arr[l] = arr[r];
while(l<r && arr[l]<=pivot) l++;
arr[r] = arr[l];
}
arr[l] = pivot;
return l;
}
public static void main(String[] args) {
int[] arr = {1,8,6,5,9,4,7,3,2,0};
quickSort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
|
有一种优化方式：分区时可能中间边界存在大量相同元素，可取其边界再划分；同时选基准时，随机选取，减小偶然性。
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 class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = {1,8,6,5,9,4,7,3,2,0};
quickSort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
|
时空复杂度
时间复杂度：最好O(nlog2n)；平均O(nlog2n)，最坏：O(n2)
空间复杂度：O(log2n)
稳定性：不稳定
7、堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
1、 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2、 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。
如下图，是一个堆和数组的相互关系：
对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标(源点从1开始)：
- Parent(i) = floor(i/2)，i 的父节点下标
- Left(i) = 2i，i 的左子节点下标
- Right(i) = 2i + 1，i 的右子节点下标
算法步骤
堆排序中经常用到的两种基本动作为：建堆和筛选
1、 创建一个堆H[0……n-1]；
2、 把堆首（最大值）和堆尾互换；
3、 把堆的尺寸缩小1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4、 重复步骤2，直到堆的尺寸为1；
代码实现
大顶堆排序
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
| public class SortTest {
public static void heapSort(int[] arr){
if(arr==null || arr.length<2) return;
for(int i=arr.length/2; i>=0; i--){
heapAdjust(arr, i, arr.length);
}
for(int i=arr.length-1; i>0; i--){
swap(arr, 0, i);
heapAdjust(arr, 0, i);
}
}
private static void heapAdjust(int[] arr, int i, int n){
int left = 2*i+1;
while(left<n){
int largest = left + 1 < n && arr[left+1]>arr[left] ? left+1 : left;
largest = arr[largest] > arr[i] ? largest : i;
if(largest == i) break;
swap(arr, largest, i);
i = largest;
left = 2*i + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = {1,8,6,5,59,18};
heapSort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
|
时空复杂度
堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。
时间复杂度：O(nlog2n)
假设节点数为n,所以需要进行n - 1次调换，也就是需要n-1次堆调整，每次堆调整的时间复杂度为O(logn) ，那么总的时间复杂度就是(n - 1)O(logn) = O(nlogn)
8、计数排序
计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为 O(n+k)。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序只适合元素是整数，小规模的排序。
算法步骤
1、 花O(n)的时间扫描一下整个待排序列，获取最小值min和最大值max；
2、 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3、 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4、 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1；
代码实现
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
| package demo;
public class SortTest {
public static void countingSort(int[] arr){
if(arr==null || arr.length<2) return;
int maxValue = getMaxValue(arr);
countingSort(arr, maxValue);
}
private static int[] countingSort(int[] arr, int maxValue){
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for(int value: arr)
bucket[value]++;
int sortedIndex = 0;
for(int j=0; j<bucketLen; j++){
while(bucket[j]>0){
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
private static int getMaxValue(int[] arr){
int maxValue = arr[0];
for(int value : arr){
if(maxValue < value)
maxValue = value;
}
return maxValue;
}
public static void main(String[] args) {
int[] arr = {1,8,6,5,59,18,15,3,7,10,2};
countingSort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
}
|
优化后的实现：
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
| public static int[] countSort1(int[] arr){
if (arr == null || arr.length == 0) {
return null;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int help[] = new int[max];
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
}
int index = 0;
for(int i = 0; i < help.length; i++){
while(help[i]-- > 0){
arr[index++] = i+min;
}
}
return arr;
}
|
View Code
时空复杂度
n个0 到 k 之间的整数时，它的运行时间是 O(n + k)
9、桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
1、 在额外空间充足的情况下，尽量增大桶的数量；
2、 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中；
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
算法步骤
1、 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶；
2、 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序；
3、 将各个桶中的数据有序的合并起来；
动画参考 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
代码实现
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
56
57
58
59
60
61
62
63
64
| public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
|
时空复杂度
O(n+k)
(1)什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
(2)什么时候最慢
当输入的数据被分配到了同一个桶中。
10、基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序按照优先从高位或低位来排序有两种实现方案：
- MSD（Most significant digital） 从最左侧高位开始进行排序。
- LSD （Least significant digital）从最右侧低位开始进行排序。
基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值；
算法步骤
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
步骤：
①.取得数组中的最大数，并取得位数；
②.arr为原始数组，从最低位开始取每个位组成radix数组；
③.对radix进行计数排序（利用计数排序适用于小范围数的特点）；
通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：
[ ]nbsp_nbsp 15
在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。
1、 按照个位数进行排序；
2、 按照十位数进行排序；
3、 按照百位数进行排序；
排序后，数列就变成了一个有序序列。
代码实现
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
public class RadixSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
private int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
private int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
|
时空复杂度
d为位数，r 为基数，n 为原数组个数。 在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。
查找算法
1、符号表
2、二叉查找树
3、平衡查找树
4、散列表
查找部分，参考文章
二分查找算法（代码实现）
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好，占用系统内存较少；其缺点是要求待查表为有序表，且插入删除困难。这个是基础，最简单的查找算法了。
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
| public static void main(String[] args) {
int srcArray[] = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
System.out.println(binSearch(srcArray, 95));
}
public static int binSearch(int srcArray[], int key) {
if (srcArray.length <= 0) {
return -1;
}
int first = srcArray[0];
int end = srcArray[srcArray.length - 1];
if (key < first || key > end) {
return -1;
}
int mid = srcArray.length / 2;
if (key == srcArray[mid]) {
return mid;
}
int startIndex = 0;
int endIndex = srcArray.length - 1;
while (startIndex <= endIndex) {
mid = (endIndex - startIndex) / 2 + startIndex;
if (key < srcArray[mid]) {
endIndex = mid - 1;
} else if (key > srcArray[mid]) {
startIndex = mid + 1;
} else {
return mid;
}
}
return -1;
}
|
二分查找算法如果没有用到递归方法的话，只会影响CPU。对内存模型来说影响不大。时间复杂度log2n，2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛，平衡树里面大量采用。
2.递归实现二分查找
递归简单理解就是方法自身调用自身。
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
| public static void main(String[] args) {
int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
System.out.println(binSearch(srcArray, 0,15,28));
}
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (srcArray[mid] == key) {
return mid;
}
if (start >= end) {
return -1;
} else if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
return -1;
}
|
递归几乎会经常用到，需要注意的一点是：递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。
图（Graph）
1、无向图
2、有向图
3、最小生成树
4、最短路径算法
字符串
1、字符串排序
2、 单词查找
3、 KMP查找算法
布隆过滤器
见 详细专题贴
]nbsp_nbsp 15
