数据结构与算法

数据结构（data structure）是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。

它包含三方面的内容，逻辑关系、存储关系及操作，不同种类的数据结构适合于不同种类的应用。

线性结构和非线性结构

  • 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
  • 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。
    • 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
    • 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
  • 线性结构常见的有：
    • 栈（Stack）：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。
    • 队列（Queue）：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
    • 数组（Array）：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
    • 链表（Linked List）：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。
  • 非线性结构常见的有：
    • 树（Tree）：树是典型的非线性结构，它是包括，2 个结点的有穷集合 K。
    • 堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
    • 图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
    • 散列表（Hash table）：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

数据结构与算法的关系

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据，存储到计算机的存储器里。

算法研究的目的：是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。

  • 算法一般有以下几种常用运算：
    • 检索：在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
    • 插入：往数据结构中增加新的节点。
    • 删除：把指定的结点从数据结构中去掉。
    • 更新：改变指定节点的一个或多个字段的值。
    • 排序：把节点按某种指定的顺序重新排列。例如递增或递减。

算法的时间复杂度

度量一个程序/算法的执行时间有两种方法：

  • 事后统计法：
    • 要想对设计的算法的运行性能进行评测，需要实际运行该程序
    • 所得时间的统计量依赖于计算机的硬件、软件等环境因素
    • 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快
  • 事前统计法：通过分析某个算法的时间复杂度来判断哪个算法更优

时间频度：

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度：

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n) 表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) = O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

时间复杂度计算中可以忽略常数项、低次项、系数。如：5n^2+7n 可以计算为 n^2。

T(n)不同，但时间复杂度可能相同。如：T(n)=n^2+7n+6 与 T(n)=3n^2+7n+6 它们的 T(n) 不同，但时间复杂度相同，都为 O(n^2)。

时间复杂度的计算方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
如：T(n) = 3n^2 + 7n + 6

用常数1代替运行时间中的所有加法常数
T(n) = 3n^2 + 7n + 6 => T(n) = 3n^2 + 7n + 1

忽略常数项 
T(n) = 3n^2 + 7n + 1 => T(n) = 3n^2 + 7n

忽略低次项
T(n) = 3n^2 + 7n => T(n) = 3n^2

忽略系数
T(n) = 3n^2 => T(n) = n^2 

结果
T(n) = n^2 => O(n^2)

常见的时间复杂度(由小到大排序)

  1. 常数阶：O(1)
  2. 对数阶：O(log_k n)
  3. 线性阶：O(n)
  4. 线性对数阶：O(n log_k n)
  5. 平方阶：O(n^2)
  6. 立方阶：O(n^3)
  7. 指数阶：O(2^n)²
  8. 阶乘阶：O(n!)
  9. n的n次方阶：O(nⁿ)

平均时间复杂度和最坏时间复杂度

  1. 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
  2. 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因匙最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
  3. 平均时间复杂度和最坏时间复杂度是否一致，和算法有关
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
排序法  排序方式  平均时间 最差情形  稳定度  额外空间    备注
插入    In-Place  O(n²)   O(n²)    稳定     O(1)   大部分已排序时较好
希尔    In-Place  O(n㏒n) O(n的s次方 1 < s < 2) 不稳定 O(1) s是所选分组
选择    In-Place  O(n²)   O(n²)    不稳定   O(1)   n小时较好
堆      In-Place  O(n㏒n) O(n㏒n)  不稳定   O(1)   n大时较好
冒泡    In-Place  O(n²)   O(n²)    稳定     O(1)   n小时较好
快速    In-Place  O(n㏒n) O(n²)    不稳定  O(n㏒n) n大时较好
归并    Out-Place O(n㏒n) O(n㏒n)   稳定    O(1)   n大时较好
基数    Out-Place O(㏒RB) O(㏒RB)   稳定    O(n)   B是真数（0-9），R是基数（个十百）

1.稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
2.不稳定：如果a原本在b前面，而a=b，排序之后a可能会在b的后面
3.内排序：所有排序操作都在内存中完成
4.外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
5.n: 数据的规模
6.In-Place：不占用额外内存
7.Out-Place：占用额外内存

算法的空间复杂度

  1. 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
  2. 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。
  3. 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis,memcache)和算法(基数排序)本质就是用空间换时间。

数据结构：数组

稀疏数组

当一个数组中大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

  • 记录数组一共有几行几列，有多少个不同的值。
  • 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

二维数组转稀疏数组

  • 遍历原始的二维数组，得到有效数据的个数 sum。
  • 根据sum就可以创建稀疏数组（Sparse Array）

    sa = int[sum + 1][3]

  • 将二维数组的有效数据数据存入到稀疏数组。

稀疏数组转二维数组

  • 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组

    arr2 = int[sa[0][0]][sa[0][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
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
/**
 * 以五子棋存储的二维数组为例
 * 转化为稀疏数组
 */
public class SparseArray {

    /**
     * 初始化二维数组
     */
    public static int[][] initArray() {
        //创建一个原始的二维数组 11 * 11
        //0：表示没有棋子，1：表示黑子，2：表示白子
        int[][] arr2 = new int[11][11];
        arr2[1][2] = 1;
        arr2[2][3] = 2;
        return arr2;
    }

    /**
     * 将二维数组转化为稀疏数组
     */
    public static int[][] transformSparseArray(int[][] arr2) {
        //获取二维数组中的有效数据个数
        int num = 0;
        for(int[] row : arr2) {
            for(int data : row) {
                if (data != 0) {
                    num = num + 1;
                }
            }
        }

        //初始化稀疏数组
        int[][] sa = new int[num + 1][3];
        sa[0][0] = arr2.length;
        sa[0][1] = arr2[0].length;
        sa[0][2] = num;

        //给稀疏数组赋值
        int count = 0;
        for (int j = 0; j < arr2.length; j++) {
            for (int k = 0; k < arr2[j].length; k++) {
                if (arr2[j][k] != 0) {
                    count = count + 1;
                    sa[count][0] = j;
                    sa[count][1] = k;
                    sa[count][2] = arr2[j][k];
                }
            }
        }
        return sa;
    }

    /**
     * 将稀疏数组转化为二维数组
     */
    public static int[][] transformTwoArray(int[][] sa) {
        //初始化二维数组
        int[][] arr2 = new int[sa[0][0]][sa[0][1]];

        //给二维数组赋值
        for (int i = 1; i < sa.length; i++) {
            arr2[sa[i][0]][sa[i][1]] = sa[i][2];
        }
        return arr2;
    }

    public static void main(String[] args) {
        //初始化二维数组
        int[][] arr2 = initArray();
        for(int[] row : arr2) {
            for(int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        System.out.println("--------------------");
        //将二维数组转化为稀疏数组
        int[][] sa = transformSparseArray(arr2);
        for (int[] ints : sa) {
            System.out.printf("%d\t%d\t%d\t\n", ints[0], ints[1], ints[2]);
        }
        System.out.println("--------------------");
        //将稀疏数组转化为二维数组
        int[][] arr = transformTwoArray(sa);
        for(int[] row : arr) {
            for(int data : row) {
                System.out.printf("%d\t", data);
            }
            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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/**
 * 使用数组模拟队列
 */
public class ArrayQueue {

    private int maxSize;//队列最大容量
    private int front;//队列头下标
    private int rear;//队列尾下标

    private int[] arr;//用于存放数据，模拟队列

    private int conut;//用于记录储存的个数

    //创建队列的构造器
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.front = -1;//队列头下标初始化为-1
        this.rear = -1;//队列尾下标初始化为-1
        conut = 0;//记录储存的个数初始化为0
    }

    //判断队列是否已经储存满
    public boolean isFull() {
        return conut == maxSize;
    }

    //判断队列是否为空
    public boolean isNull() {
        return conut == 0;
    }

    //给队列添加值
    public void add(int value) {
        if (isFull()) {
            System.out.println("队列已满，请稍后...");
            return;
        }
        conut = conut + 1;
        rear = (rear + 1) % maxSize;
        arr[rear] = value;
    }

    //获取队列的值
    public int get() {
        if (isNull()) {
            throw new RuntimeException("队列为空，不能取数据");
        }
        conut = conut - 1;
        front = (front + 1) % maxSize;
        return arr[front];
    }

    //显示队列的所有数据
    public void show() {
        if (isNull()) {
            System.out.println("队列为空");
            return;
        }

        for (int i = 0; i < conut; i++) {
            System.out.println("第" + (1+i) + "位：" + arr[(front + 1 + i) % maxSize]);
        }
    }

    //显示队列目前的第一个数据
    public int headValue() {
        if(isNull()) {
            throw new RuntimeException("对列为空");
        }
        return arr[(front + 1) % maxSize];
    }
}

public class Client {
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' ';
        //接收用户输入
        Scanner scanner = new Scanner(System.in);
        //输出一个菜单
        boolean bool = true;
        while(bool){
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key) {
                case 's':
                    queue.show();
                    break;
                case 'e':
                    bool = false;
                    scanner.close();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int nextInt = scanner.nextInt();
                    queue.add(nextInt);
                    break;
                case 'g':
                    try {
                        int i = queue.get();
                        System.out.println("取出的数据是：" + i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int i = queue.headValue();
                        System.out.println("目前排在第一位的数据是：" + i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        };
        System.out.println("退出程序...");
    }
}

数据结构：链表

链表是一个有序列表，链表是以节点的方式链式存储的，各个节点不一定是连续储存的，每个节点包含 data 域、next 域，next 域指向下一个节点。

链表分为带头节点的链表和不带头节点的链表，双向链表比单向链表多一个 prev 域指向前一个节点。

单向链表只能查找一个方向，而双向链表可以向前向后查找。

单向链表不能自我删除，需要依靠辅助节点，而双向链表可以自我删除。

单向链表

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
/**
 * 使用单向链表模拟：ArrayList类
 */
public class SinglyLinkedList<E> implements Iterable<E> {

    private Node headNode; //链表头部节点

    public SinglyLinkedList() {
        this.headNode = new Node();
    }

    private class Node {
        private E data;
        private Node next;

        public Node() {}

        public Node(E data) {
            this.data = data;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" + "data=" + data + '}';
        }
    }

    /**
     * 根据下标获取节点
     */
    private Node getNode(int index) {
        Node nodeNext = this.headNode.getNext();
        int tempIndex = 0;
        while (nodeNext != null) {
            if (tempIndex == index) {
                return nodeNext;
            }
            nodeNext = nodeNext.getNext();
            tempIndex = tempIndex + 1;
        }
        throw new RuntimeException("根据下标未找到数据~~~");
    }

    /**
     * 添加数据
     */
    public void add(E data) {
        Node node = new Node(data);
        Node nextNode = this.headNode.getNext();
        if (nextNode == null) {
            this.headNode.setNext(node);
            return;
        }

        Node prevNode = nextNode;
        while (true) {
           if(nextNode == null) {
               prevNode.setNext(node);
               break;
           }
           prevNode = nextNode;
           nextNode = nextNode.getNext();
        }
    }

    /**
     * 删除数据
     */
    public void delete(int index) {
        Node node = getNode(index);
        if (node.getNext() == null) {
            if (index == 0) {
                this.headNode.setNext(null);
            } else {
                getNode(index - 1).setNext(null);
            }
        } else {
            Node nextNode = node.getNext();
            if (index == 0) {
                this.headNode.setNext(nextNode);
            } else {
                Node prevNode = getNode(index - 1);
                prevNode.setNext(nextNode);
            }
        }
    }

    /**
     * 修改数据
     */
    public void update(int index, E data) {
        getNode(index).setData(data);
    }

    /**
     * 获取数据
     */
    public E get(int index) {
        return getNode(index).getData();
    }

    /**
     * 遍历数据
     */
    public String toString() {
        Node nodeNext = this.headNode.getNext();
        StringBuilder result = new StringBuilder("[");
        while (true) {
            if (nodeNext != null) {
                result.append(nodeNext.getData().toString());
                if (nodeNext.getNext() != null) {
                    result.append(", ");
                    nodeNext = nodeNext.getNext();
                } else {
                    break;
                }
            }
        }
        result.append("]");
        return result.toString();
    }

    /**
     * 获取数据长度
     */
    public int length() {
        int length = 0;
        Node next = this.headNode.getNext();
        while (next != null) {
            next = next.getNext();
            length = length + 1;
        }
        return length;
    }

    private Node iteratorTemp;

    @Override
    public Iterator<E> iterator() {
        iteratorTemp = this.headNode;
        return new Iterator<E>() {
            @Override
            public boolean hasNext() {
                return iteratorTemp.getNext() != null;
            }

            @Override
            public E next() {
                Node next = iteratorTemp.getNext();
                iteratorTemp = next;
                return next.getData();
            }
        };
    }

    /**
     * 单链表的反转
     */
    public void reverse() {
        //新建一个临时的头节点
        Node headNodeTemp = new Node();
        //获取第一个节点
        Node next = this.headNode.getNext();
        //没有第一个节点返回
        if (next == null) return;
        //获取第一个节点的下一个节点给临时子节点
        Node nodeTemp = next.getNext();
        //把第一个节点的下一个节点改为空
        next.setNext(null);
        //把第一个节点放入临时头节点中
        headNodeTemp.setNext(next);

        while (nodeTemp != null) {
            //获取下一个节点
            Node node = nodeTemp.getNext();
            //修改当前节点的下一个节点（下一个节点是临时头节点的第一个节点）
            nodeTemp.setNext(headNodeTemp.getNext());
            //把当前节点放在临时头节点的第一个节点
            headNodeTemp.setNext(nodeTemp);
            //把下一个节点赋值给临时节点
            nodeTemp = node;
        }

        //把临时头节点的第一个节点赋予给头节点
        this.headNode.setNext(headNodeTemp.getNext());
    }
}

public class Client {
    public static void main(String[] args) {
        SinglyLinkedList<String> singlyLinkedList = new SinglyLinkedList<>();
        singlyLinkedList.add("唐僧");
        singlyLinkedList.add("白龙马");
        singlyLinkedList.add("孙悟空");
        singlyLinkedList.add("猪悟能");
        singlyLinkedList.add("沙悟净");

        System.out.println(singlyLinkedList.toString());

        System.out.println("链表总长度：" + singlyLinkedList.length());

        System.out.println("--- 把白龙马修改为三太子 ---");
        singlyLinkedList.update(1, "三太子");
        System.out.println(singlyLinkedList.toString());

        System.out.println("--- 删除白龙马 ---");
        singlyLinkedList.delete(1);
        System.out.println(singlyLinkedList.toString());

        System.out.println("--- 获取下标为1的值 ---");
        System.out.println(singlyLinkedList.get(1));

        System.out.println("--- 迭代器 ---");
        Iterator<String> iterator = singlyLinkedList.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            System.out.println(next);
        }

        System.out.println("--- 链表反转后的值 ---");
        singlyLinkedList.reverse();
        System.out.println(singlyLinkedList.toString());
    }
}

单向环形列表

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
/**
 * 单向环形链表
 */
public class SinglyCircleLinkedList<E> {

    private Node firstNode;//指向第一个节点

    public SinglyCircleLinkedList() {
    }

    class Node {
        private E data;
        private Node nextNode;

        public Node() {
        }

        public Node(E data) {
            this.data = data;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node getNextNode() {
            return nextNode;
        }

        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }
    }

    public void add(E data) {
        //添加一个节点
        Node node = new Node(data);
        //第一个节点为null，表示还没有数据
        if (firstNode == null) {
            //添加的节点自己指向自己（环形）
            node.setNextNode(node);
            //第一个节点指向新添加的节点
            firstNode = node;
        } else {
            Node nextNode = firstNode;
            //当下一个节点指向的是第一个节点，表示循环到了最后一个
            while (nextNode.getNextNode() != firstNode) {
                nextNode = nextNode.getNextNode();
            }
            //把添加的节点指向第一个节点
            node.setNextNode(firstNode);
            //把最后一个节点的下一个节点指向添加的节点
            nextNode.setNextNode(node);
        }
    }

    public void show() {
        Node nextNode = firstNode;
        while (true) {
            System.out.println(nextNode.getData().toString());
            if (nextNode.getNextNode() == firstNode) {
                break;
            }
            nextNode = nextNode.getNextNode();
        }
    }

    public int length() {
        int length = 0;
        if (this.firstNode != null) {
            Node temp = this.firstNode;
            while (true) {
                length = length + 1;
                if (this.firstNode == temp.getNextNode()) {
                    break;
                }
                temp = temp.getNextNode();
            }
        }
        return length;
    }

    /**
     * 约瑟夫环（Josephus）问题：
     *      设编号为1，2，... n 的 n 个人围坐一圈。
     *      随机指定一个编号为 k：(1 <= k <= n)的人，从 1 开始报数，数到 m 的那个人出列。
     *      出列的下一人又从 1 开始报数，数到 m 的那个人又出列，依次类推。
     *      直到所有人出列为止，由此产生一个出队编号的序列。
     * @param k k：(1 <= k <= n)，n 有效数据总数
     * @param m m：(m >= 1)，指定报数的数字
     */
    public void josephusRun(int k, int m) {
        if (k < 1 || k > length() || m < 1)
            return;

        //根据 K 找到第一个数 1 的人
        int count = 0;
        Node prevNode;//当前报数的节点的上一个节点
        Node temp = this.firstNode;
        while (true) {
            if (this.firstNode == temp.getNextNode()) {
                prevNode = temp;
                break;
            }
            temp = temp.getNextNode();
        }
        Node numNode = this.firstNode;//当前报数的节点

        while (true) {
            //循环计数，当与 K 值相等时 numNode为第一个报数的人
            count = count + 1;
            if (count == k) {
                break;
            }
            prevNode = numNode;
            numNode = numNode.getNextNode();
        }

        //循环出列
        while (this.firstNode != null) {
            //当上一个节点和报数的节点为同一节点时，说明节点中只剩下一个节点
            if (prevNode == numNode) {
                //打印报最后一个节点
                System.out.println(numNode.getData().toString());
                //移除此节点
                this.firstNode = null;
                break;
            }

            //从 numNode 节点开始为 1，到 M 为止，M节点出列。
            count = 0;
            while (true) {
                count = count + 1;
                if (count == m) {
                    //打印报到 m 的节点
                    System.out.println(numNode.getData().toString());
                    //移除此节点
                    prevNode.setNextNode(numNode.getNextNode());
                    //下一次报数的节点
                    numNode = numNode.getNextNode();
                    break;//结束此次循环，进行下一阶段报数
                }
                //否则当前报数的节点为上一个节点
                prevNode = numNode;
                //把下一个节点看为要报数的节点
                numNode = numNode.getNextNode();
            }
        }
    }
}

public class Client {
    public static void main(String[] args) {
        SinglyCircleLinkedList<String> singlyCircleLinkedList = new SinglyCircleLinkedList<>();
        singlyCircleLinkedList.add("刘一");
        singlyCircleLinkedList.add("陈二");
        singlyCircleLinkedList.add("张三");
        singlyCircleLinkedList.add("李四");
        singlyCircleLinkedList.add("王五");
        singlyCircleLinkedList.add("赵六");
        singlyCircleLinkedList.add("孙七");
        singlyCircleLinkedList.add("周八");
        singlyCircleLinkedList.add("吴九");
        singlyCircleLinkedList.add("郑十");

        singlyCircleLinkedList.show();

        System.out.println(singlyCircleLinkedList.length());

        singlyCircleLinkedList.josephusRun(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
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
/**
 * 使用双向链表模拟：ArrayList类
 */
public class DoubleLinkedList<E> {

    private Node headNode; //链表头部节点

    public DoubleLinkedList() {
        this.headNode = new Node();
    }

    private class Node {
        private E data;
        private Node prevNode;
        private Node nextNode;

        public Node() {}

        public Node(E data) {
            this.data = data;
        }

        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }

        public Node getPrevNode() {
            return prevNode;
        }

        public void setPrevNode(Node prevNode) {
            this.prevNode = prevNode;
        }

        public Node getNextNode() {
            return nextNode;
        }

        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }

        @Override
        public String toString() {
            return "Node{" + "data=" + data + '}';
        }
    }

    /**
     * 根据下标获取节点
     */
    private Node getNode(int index) {
        Node nodeNext = this.headNode.getNextNode();
        int tempIndex = 0;
        while (nodeNext != null) {
            if (tempIndex == index) {
                return nodeNext;
            }
            nodeNext = nodeNext.getNextNode();
            tempIndex = tempIndex + 1;
        }
        throw new RuntimeException("根据下标未找到数据~~~");
    }

    /**
     * 添加数据
     */
    public void add(E data) {
        Node node = new Node(data);
        Node nextNode = this.headNode.getNextNode();
        if (nextNode == null) {
            this.headNode.setNextNode(node);
            return;
        }

        Node temp = this.headNode;
        while (true) {
            if(temp.getNextNode() == null) {
                node.setPrevNode(temp);
                temp.setNextNode(node);
                break;
            }
            temp = temp.getNextNode();
        }
    }

    /**
     * 删除数据
     */
    public void delete(int index) {
        Node node = getNode(index);
        Node prevNode = node.getPrevNode();
        Node nextNode = node.getNextNode();

        //上一个节点是NULL，那就表示要删除的节点是第一个节点
        if (prevNode == null) {
            //下一个节点为空，表示只有一个节点，则把头节点变为空
            if (nextNode == null) {
                this.headNode.setNextNode(null);
            } else { //否则头节点指向下一个节点，下一个节点的prevNode变为空
                nextNode.setPrevNode(null);
                this.headNode.setNextNode(nextNode);
            }
        } else {
            //下一个节点不为空，把下一个节点的上一个节点指向要删除节点的上一个节点
            if (nextNode != null) {
                nextNode.setPrevNode(prevNode);
            }
            //上一个节点不为空则把上一个节点中的nextNode指向要删除节点的nextNode
            prevNode.setNextNode(nextNode);
        }
    }

    /**
     * 修改数据
     */
    public void update(int index, E data) {
        getNode(index).setData(data);
    }

    /**
     * 获取数据
     */
    public E get(int index) {
        return getNode(index).getData();
    }

    public String toString() {
        Node nodeNext = this.headNode.getNextNode();
        StringBuilder result = new StringBuilder("[");
        while (true) {
            if (nodeNext != null) {
                result.append(nodeNext.getData().toString());
                if (nodeNext.getNextNode() != null) {
                    result.append(", ");
                    nodeNext = nodeNext.getNextNode();
                } else {
                    break;
                }
            }
        }
        result.append("]");
        return result.toString();
    }

    /**
     * 获取数据长度
     */
    public int length() {
        int length = 0;
        Node next = this.headNode.getNextNode();
        while (next != null) {
            next = next.getNextNode();
            length = length + 1;
        }
        return length;
    }
}

public class Client {
    public static void main(String[] args) {
        DoubleLinkedList<String> singlyLinkedList = new DoubleLinkedList<>();
        singlyLinkedList.add("唐僧");
        singlyLinkedList.add("白龙马");
        singlyLinkedList.add("孙悟空");
        singlyLinkedList.add("猪悟能");
        singlyLinkedList.add("沙悟净");

        System.out.println(singlyLinkedList.toString());

        System.out.println("链表总长度：" + singlyLinkedList.length());

        System.out.println("--- 把白龙马修改为三太子 ---");
        singlyLinkedList.update(1, "三太子");
        System.out.println(singlyLinkedList.toString());

        System.out.println("--- 删除白龙马 ---");
        singlyLinkedList.delete(1);
        System.out.println(singlyLinkedList.toString());

        System.out.println("--- 获取下标为1的值 ---");
        System.out.println(singlyLinkedList.get(1));
    }
}

数据结构：栈

栈（stack）是一个先入后出（FILO-First In Last Out）的有序列表，元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。

允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。最先放入栈中元素在栈底，最后放入的元素在栈顶。删除元素时，最后放入的元素最先删除，最先放入的元素最后删除。

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
/**
 * 使用数组模拟栈
 */
public class Stack {

    private int maxSize; // 栈的大小
    private int[] stack; // 数组模拟栈，数据就放在该数组
    private int top = -1;// top表示栈顶下标，初始化为-1

    //构造器
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //栈满
    public boolean isFull() {
        return this.top == this.maxSize - 1;
    }

    //栈空
    public boolean isEmpty() {
        return this.top == -1;
    }

    //入栈
    public void push(int value) {
        //先判断栈是否满
        if(isFull()) {
            System.out.println("栈满");
            return;
        }
        //栈顶下标加1
        top = top + 1;
        //数据放入数组
        stack[top] = value;
    }

    //出栈
    public int pop() {
        //先判断栈是否空
        if(isEmpty()) {
            throw new RuntimeException("栈空，没有数据~");
        }
        //根据栈顶下标获取栈
        int value = stack[top];
        //栈顶下标减1
        top = top - 1;
        return value;
    }

    //显示
    public void show() {
        if (isEmpty()) {
            System.out.println("null");
            return;
        }
        //需要从栈顶开始显示数据
        for(int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
}

class ClientStack {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);

        System.out.println("--- 显示栈的数据 ---");
        stack.show();

        System.out.println("--- 循环出站 ---");
        while (!stack.isEmpty()) {
            try {
                int pop = stack.pop();
                System.out.println(pop);
            } catch (Exception ignored) {}
        }

        System.out.println("--- 显示栈的数据 ---");
        stack.show();
    }
}

数据结构：哈希表

哈希表(Hash table，也叫散列表)，是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。

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
/**
 * 表示一个雇员
 */
public class Emp {
    public int id;
    public String name;
    public Emp next; //next 默认为 nuLL

    public Emp(int id,String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

/**
 * 创建EmpLinkedList,表示链表
 */
public class EmpLinkedList {

    //头指针，执行第一个Emp，因此我们这个链表的head，是直接指向第一个Emp
    private Emp head;//默认null

    //添加雇员到链表
    //说明
    //1。假定，当添加雇员时，id 是自增长，即id的分配总是从小到大
    // 因此我们将该雇员直接加入到本链表的最后即可
    public void add(Emp emp) {
        //如果是添加第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {//说明到链表最后
                break;
            }
            curEmp = curEmp.next;//后移
        }
        //退出时直接将emp 加入链表
        curEmp.next = emp;
    }

    //遍历链表的雇员信息
    public void list(int no) {
        if (head == null) { //说明链表为空
            System.out.println("第"+(no+1)+"条链表为空");
            return;
        }
        System.out.print("第"+(no+1)+"条链表的信息为");
        Emp curEmp = head;//辅助指针
        while (true) {
            System.out.printf("=> id=%d name=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {//说明curEmp已经是最后结点
                break;
            }
            curEmp = curEmp.next;//后移，遍历
        }
        System.out.println();
    }

    //根据id查找雇员
    //如果查找到，就返回Emp，如果没有找到，就返回null
    public Emp findEmpById(int id) {
        //辅助指针Emp
        Emp curEmp = head;
        while(true) {
            // 退出
            if(curEmp == null){
                break;//说明遍历当前链表没有找到该雇员
            }
            //匹配
            if(curEmp.id == id) {
                break;//这时curEmp就指向要查找的雇员
            }
            //下一个
            curEmp = curEmp.next;
        }
        return curEmp;
    }
}

/**
 * 创建HashTab 管理多条链表
 */
public class HashTab {

    private EmpLinkedList[] empLinkedListArray;
    private int size;//表示有多少条链表

    //构造器
    public HashTab(int size){
        //初始化
        this.size = size;
        empLinkedListArray = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //添加雇员
    public void add (Emp emp) {
        //根据员工的id，得到该员工应当添加到哪条链表
        int empLinkedListNo = hashFun(emp.id);
        //将emp添加到对应的链表中
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    //遍历所有的链表，遍历hashtab
    public void list() {
        for(int i = 0; i < size; i++){
            empLinkedListArray[i].list(i);
        }
    }

    //根据输入的id,查找雇员
    public void findEmpById(int id) {
        //使用散列函数确定到哪条链表查找
        int empLinkedListNo = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
        if(emp != null){
            System.out.printf("在第%d条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id);
        } else {
            System.out.println("在哈希表中，没有找到该雇员~");
        }
    }
    //编写散列函数，使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }

}

public class Run {

    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        //写一个简单的菜单
        String key ="";
        Scanner scanner = new Scanner(System.in);
        while(true) {
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("find:查找雇员");
            System.out.println("exit:退出系统");

            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建 雇员
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("输入id");
                    hashTab.findEmpById(scanner.nextInt());
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

数据结构：树

  1. 二叉树(BinaryTree)
    • 每个节点最多只能有两个子节点称为二叉树，二叉树的子节点分为左节点和右节点。
    • 如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2ⁿ-1，n为层数，则我们称为满二叉树。
    • 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
  2. 多叉树(MultiwayTree)
    • 每个节点可以有更多的数据项和更多的子节点，就是多叉树。
    • 节点的度：在一个节点中，子节点数量为2，节点的度就是2，一个节点的子节点数量为999，节点的度就是999。
    • 树的度：在一棵树所有节点中，最大节点的度就是树的度。
    • 2-3树、2-3-4树
      • 2-3树是由二节点和三节点构成的树。
      • 2-3-4树是由二节点、三节点和四节点构成的树。
      • 2-3树、2-3-4树的所有叶子节点都在同一层。
      • 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
      • 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
      • 有四个子节点的节点叫四节点，四节点要么没有子节点，要么有四个子节点。
  3. B树(B-Tree)
    • B即Balanced，平衡的意思。
    • B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。
    • B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4。
    • B树的搜索，从根结点开始，对结点内的关键字(有序)序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点，重复，直到所对应的儿子指针为空，或已经是叶子结点。
    • 关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据，搜索有可能在非叶子结点结束，其搜索性能等价于在关键字全集内做一次二分查找。
  4. B+树
    • B+树是B树的变体，也是一种多路搜索树。
    • B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），不可能在非叶子结点命中，其性能也等价于在关键字全集做一次二分查找。
    • 所有关键字都出现在叶子结点的链表中，即数据只能在叶子节点（也叫稠密索引），且链表中的关键字（数据）恰好是有序的。
    • 非叶子结点相当于是叶子结点的索引（稀疏索引）叶子结点相当于是存储关键字（数据）的数据层，更适合文件索引系统。
    • B树和B+树各有自己的应用场景，没有性能好坏之分。
  5. B*树
    • B*树是B+树的变体，在B+树的非根节点和非叶子结点再增加指向兄弟的指针。
    • B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
    • B*树分配新结点的概率比B+树要低，空间使用率更高。

简单二叉树

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
/**
 * 二叉树节点
 */
public class HeroNode {

    private int no;
    private String name;
    private HeroNode left; //左节点
    private HeroNode right;//右节点

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历: 先输出父节点，再遍历左子树，再遍历右子树
    public void preOrder() {
        // 输出父结点
        System.out.println(this);
        // 递归向左子树遍历
        if(this.left != null) {
            this.left.preOrder();
        }
        // 递归向右子树遍历
        if(this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
    public void infixOrder() {
        // 递归向左子树遍历
        if(this.left != null) {
            this.left.infixOrder();
        }
        // 输出父结点
        System.out.println(this);
        // 递归向右子树遍历
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

    //后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
    public void postOrder() {
        // 递归向左子树遍历
        if(this.left != null) {
            this.left.postOrder();
        }
        // 递归向右子树遍历
        if(this.right != null) {
            this.right.postOrder();
        }
        // 输出父结点
        System.out.println(this);
    }

    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        System.out.println("进入前序遍历查找");

        //比较当前节点是不是
        if(this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
        //2.如果左递归前序查找，找到节点，则返回
        if(this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        //说明我们左子树找到
        if(resNode != null) {
            return resNode;
        }
        //1.左递归前序查找，找到节点，则返回，否则继续判断，
        //2.当前的节点的右子节点是否为空，如果不空，则继续向右递归前序查找
        if(this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        //判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if(resNode != null) {
            return resNode;
        }
        //如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点
        System.out.println("进入中序遍历查找");
        if(this.no == no) {
            return this;
        }
        //否则继续进行右递归的中序查找
        if(this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        //判断当前节点的左子节点是否为空，如果不为空，则递归后序查找
        HeroNode resNode = null;
        if(this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if(resNode != null){//说明在左子树找到
            return resNode;
        }
        //如果左子树没有找到，则向右子树递归进行后序遍历查找
        if(this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if(resNode != null){//说明在右子树找到
            return resNode;
        }
        //如果左右子树都没有找到，就比较当前节点是不是
        System.out.println("进入后序遍历查找");
        if(this.no == no){
            return this;
        }
        return null;
    }

    //递归删除结点
    //1.如果删除的节点是叶子节点，则删除该节点
    //2.如果删除的节点是非叶子节点，则删除该子树
    //因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要则除结点。
    public void delNode(int no) {
        /*

            3.如果第1和第2步没有删除结点，那么我们就需要向左子树进行递归删除
            4.如果第3步也没有删除结点，则应当向右子树进行递归删除。
         */
        //1.如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left = null,结束递归删除;
        if (this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        //2.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right= null,结束递归删除;
        if (this.right != null && this.right.no == no){
            this.right = null;
            return;
        }
        //3.如果第1和第2步没有删除结点，那么我们就需要向左子树进行递归删除
        if (this.left != null) {
            this.left.delNode(no);
        }
        //4.如果第3步也没有删除结点，则应当向右子树进行递归删除。
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
}

/**
 * 二叉树
 */
public class BinaryTree {

    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历: 先输出父节点，再遍历左子树，再遍历右子树
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        }
    }

    //中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        }
    }

    //后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        }
    }

    //前序遍历查找
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return this.root.postOrderSearch(no);
        } else {
            return null;
        }
    }

    //删除结点
    public void delNode(int no) {
        if (root != null) {
            //如果只有一个root结点，这里立即判断root是不是就是要删除结点
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);//递归删除
            }
        } else {
            System.out.println("空树，不能删除~");
        }
    }
}

public class Run {
    public static void main(String[] args) {
        //先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();//创建需要的结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        
        //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);
        binaryTree.setRoot(root);

        //遍历
        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();

        //查找
        System.out.println("前序遍历查找");
        HeroNode resNode = binaryTree.preOrderSearch(5);
        if(resNode != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
        System.out.println("中序遍历查找");
        resNode = binaryTree.infixOrderSearch(5);
        if(resNode != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
        System.out.println("后序遍历查找");
        resNode = binaryTree.postOrderSearch(5);
        if(resNode != null) {
            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
        } else {
            System.out.printf("没有找到 no = %d 的英雄", 5);
        }
        System.out.println();

        //删除
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();
        binaryTree.delNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();
    }
}

数组二叉树

数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

  1. 数组二叉树通常只考虑完全二叉树
  2. 第n个元素的左子节点为：2*n + 1
  3. 第n个元素的右子节点为：2*n + 2
  4. 第n个元素的父节点为：(n-1) / 2
  5. n：表示二叉树中的第几个元素，从0开始
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 ArrBinaryTree {

    private int[] arr;//储存数据节点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    /**
     * 重载
     */
    public void preOrder() {
        this.preOrder(0);
    }

    /**
     * @description: 前序遍历
     * @param: index 数组下标
     */
    private void preOrder(int index) {
        //如果数组为空，或者 arr.length =0
        if(arr == null || arr.length == 0) {
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        //输出
        System.out.println(arr[index]);
        //向左递归遍历
        int indexLeft = 2 * index + 1;
        if (indexLeft < arr.length) {
            preOrder(indexLeft);
        }
        //向右递归遍历
        int indexRight = 2 * index + 2;
        if (indexRight < arr.length) {
            preOrder(indexRight);
        }
    }
}

public class Run {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree tree = new ArrBinaryTree(arr);
        tree.preOrder();
    }
}

线索二叉树

  1. n个结点的二叉链表中含有n+1 [推导公式：2n-(n-1) = n + 1]个空指针域。
  2. 一个结点的前一个结点，称为前驱结点；一个结点的后一个结点，称为后继结点。
  3. 利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针，这种附加的指针称为”线索”。
  4. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。
  5. 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树、后序线索二叉树。

注意：当线索化二叉树后，Node节点的属性 left 和 right，有如下情况

  1. left 可能指向左子树，也有可能指向前驱节点。
  2. right 可能指向右子树，也有可能指向后继节点。
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
/**
 * 二叉树节点
 */
public class HeroNode {

    private int no;
    private String name;
    private HeroNode left; //左节点
    private HeroNode right;//右节点

    //1.如果leftType == 0表示指向的是左子树，如果1表示指向前驱结点
    private int leftType;
    //2.如果rightType == 0表示指向的是右子树，如果1表示指向后继结点
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

/**
 * 线索二叉树
 */
public class ThreadedBinaryTree {

    private HeroNode root;

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre总是保留前一个结点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //重载
    public void threadedInfix() {
        threadedInfix(root);
    }

    //对二叉树进行中序线索化
    private void threadedInfix(HeroNode node) {
        if (node == null) {
            return;
        }

        //先线索化左子树
        threadedInfix(node.getLeft());

        //再线索化当前节点
        //处理当前结点的前驱结点
        if(node.getLeft() == null){
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型
            node.setLeftType(1);
        }
        //处理后继结点
        if(pre != null && pre.getRight() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱结点的右指针的类型
            pre.setRightType(1);
        }
        //!!!每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;

        //再线索化右子树
        threadedInfix(node.getRight());
    }

    /**
     * 二叉树遍历
     * 因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用。
     * 这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。
     * 遍历的次序和什么方式线索化（前序线索二叉树、中序线索二叉树、后序线索二叉树）保持一致
     */
    //遍历线索化二叉树
    public void threadedList() {
        //定义一个变量，存储当前追历的结点，从root开始
        HeroNode node = root;
        while (node != null) {
            //循环的找到leftType == 1的结点，后面随着遍历而变化
            //因为当1eftType == 1时，说明该结点是按照线索化处理后的有效结点
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前这个结点
            System.out.println(node);

            //如果当前结点的右指针指向的是后继结点，一直输出
            while(node.getRightType() == 1) {
                //获职到当前结点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的结点
            node = node.getRight();
        }
    }
}

public class Run {
    public static void main(String[] args) {
        //测试中序线索二叉树的功能
        HeroNode root = new HeroNode(1,"tom" );
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6,"smith");
        HeroNode node4 = new HeroNode(8,"mary");
        HeroNode node5 = new HeroNode(10,"king" );
        HeroNode node6 = new HeroNode(14,"dim");
        //二叉树，后面我们要递归创建，现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.threadedInfix();//中序线索化二叉树

        //测试:以10号节点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是:" + leftNode);
        System.out.println("10号结点的后继结点是:" + rightNode);

        //遍历
        tree.threadedList();
    }
}

二叉排序树

二叉排序树也翻译为：BST:(Binary Sort(Search) Tree)，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。

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
203
/**
 * 节点
 */
public class Node {
    int value;//结点权值
    Node left;//指向左子结点
    Node right;//指向右子结点

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //添加结点的方法//注意需要满足二叉排序树的要求
    public void add(Node node) {
        if(node == null) {
            return;
        }
        //判断传入的结点的值，和当前子树的根结点的值关系
        if(node.value < this.value) {
            //如果当前结点左子结点为null
            if(this.left == null) {
                this.left = node;
            } else {
                //递归的向左子树添加
                this.left.add(node);
            }
        } else{
            //添加的结点的值大于当前结点的值
            if(this.right == null) {
                this.right = node;
            } else {
                //递归的向右子树添加
                this.right.add(node);
            }
        }
    }

    //中序遍历
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

    //查找节点
    public Node search(int value) {
        if(value == this.value){ //找到就是该结点
            return this;
        } else if( value < this.value) {//如果查找的值小于当前结点，向左子树递归查找
            // 如果左子结点为空
            if(this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else{ //如果查找的值不小于当前结点，向右子树递归查找
            if(this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找节点的父节点
    public Node searchParent(Node node) {
        int value = node.value;
        //如果当前结点就是要删除的结点的父结点，就返回
        if((this.left != null && this.left.value == value)
                || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的值小于当前结点的值，并且当前结点的左子结点不为空
            if(value < this.value && this.left != null) {
                return this.left.searchParent(node);//向左子树递归查找
            } else if(value >= this.value && this.right != null) {
                return this.right.searchParent(node);//向右子树递归查找
            }
            return null;// 没有找到父结点
        }
    }

}

/**
 * 二叉排序树
 */
public class BinarySortTree {

    private Node root;

    //添加结点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //根据值查找结点
    public Node search(int value) {
        if (root != null) {
            return root.search(value);
        } else {
            return null;
        }
    }
    //根据结点查找其父结点
    public Node searchParent(Node node) {
        if (node != null) {
            return root.searchParent(node);
        } else {
            return null;
        }
    }

    //删除节点
    public void delNode(int value) {
        if (root == null)
            return;

        //查找节点
        Node node = search(value);

        //没有找到节点
        if (node == null)
            return;

        //处理后继节点
        Node nextNode = null;
        //要删除的节点是有两颗子树的节点
        if(node.left != null && node.right != null) {
            //找出要删除的节点里，右子节点下最小的值
            //要删除的节点->右子节点->左子节点（在左子节点里一直找，最后一个就是最小的）
            nextNode = node.right;
            while(nextNode.left != null) {
                nextNode = nextNode.left;
            }
            //删除这个最小的节点
            delNode(nextNode.value);

            //把要删除节点的左子节点和右子节点负值给找到的最小的节点
            nextNode.left = node.left;
            if (nextNode != node.right) {
                nextNode.right = node.right;
            }
        } else {//要删除的节点是有一颗子树的节点//没有子节点后继节点为null
            if(node.left != null) {
                nextNode = node.left;
            }
            if (node.right != null) {
                nextNode = node.right;
            }
        }

        //查找要删除节点的父节点
        Node parentNode = searchParent(node);
        if (parentNode != null) {
            //判断要删除的节点是父节点的左子节点还是右子节点
            if(parentNode.left != null && parentNode.left.value == value) {
                parentNode.left = nextNode;//后继节点替换掉要删除的左子节点
            } else if(parentNode.right != null && parentNode.right.value == value) {
                parentNode.right = nextNode;//后继节点替换掉要删除的右子节点
            }
        } else {
            //要删除节点没有父节点，说明要删除节点是root节点
            root = nextNode;
        }
    }


    //中序遍历
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        }
    }

}

public class Run {
    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9,2};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环的添加结点到二叉排序树
        for(int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        binarySortTree.infixOrder();
        binarySortTree.delNode(3);
        binarySortTree.infixOrder();
    }
}

平衡二叉树

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树，可以保证查询效率较高。

平衡二叉树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

平衡二叉树是在二叉排序树的基础上就行了优化，通过左右旋转的方法，保证左右两个子树的高度差的绝对值不超过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
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
/**
 * 节点
 */
public class Node {
    int value;//结点权值
    Node left;//指向左子结点
    Node right;//指向右子结点

    public Node(int value) {
        this.value = value;
    }

    //添加结点的方法//注意需要满足二叉排序树的要求
    public void add(Node node) {
        if(node == null) {
            return;
        }
        //判断传入的结点的值，和当前子树的根结点的值关系
        if(node.value < this.value) {
            //如果当前结点左子结点为null
            if(this.left == null) {
                this.left = node;
            } else {
                //递归的向左子树添加
                this.left.add(node);
            }
        } else{
            //添加的结点的值大于当前结点的值
            if(this.right == null) {
                this.right = node;
            } else {
                //递归的向右子树添加
                this.right.add(node);
            }
        }
        //当添加完一个结点后，如果:(右子树的高度-左子树的高度)>1，左旋转
        if(rightHeight() - leftHeight() > 1) {
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if(right != null && right.leftHeight() > right.rightHeight()) {
                //先对当前结点的右结点(右子树)->右旋转
                right.rightRotate();
            }
            //左旋转
            leftRotate();
        }
        //当添加完一个结点后，如果:(左子树的高度-右子树的高度)>1，右旋转
        else if(leftHeight() - rightHeight() > 1) {
            //如果它的左子树的右子树高度大于它的左子树的高度
            if(left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前结点的左结点(左子树)->左旋转
                left.leftRotate();
            }
            //右旋转
            rightRotate();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //中序遍历
    public void infixOrder() {
        if(this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right != null) {
            this.right.infixOrder();
        }
    }

    //返回当前结点的高度，以该结点为根结点的树的高度
    public int height() {
        int leftHeight = left == null ? 1 : left.height() + 1;
        int rightHeight = right == null ? 1 : right.height() + 1;
        return Math.max(leftHeight, rightHeight);
    }

    //返回左子树的高度
    public int leftHeight() {
        if(left == null) {
            return 0;
        }
        return left.height();
    }

    //返回右子树的高度
    public int rightHeight() {
        if(right == null) {
            return 0;
        }
        return right.height();

    }

    //左旋转
    private void leftRotate() {
        //创建新的结点，以当前根结点的值
        Node newNode =new Node(value);
        //把新的结点的左子树设置成当前结点的左子树
        newNode.left = left;
        //把新的结点的右子树设置成带你过去结点的右子树的左子树
        newNode.right =right.left;
        //把当前结点的值替换成右子结点的值
        value = right.value;
        //把当前结点的右子树设置成当前结点右子树的右子树
        right = right.right;
        //把当前结点的左子树(左子结点)设置成新的结点
        left = newNode;
    }

    //右旋转
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }
}

/**
 * 平衡二叉树
 */
public class AVLTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    //添加结点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //中序遍历
    public void infixOrder() {
        if(root != null) {
            root.infixOrder();
        }
    }

}

public class Run {
    public static void main(String[] args) {
        //int[] arr = {4,3,6,5,7,8};//右子树高//左旋转
        //int[] arr = {10,12,8,9,7,6};//左子树高//右旋转
        int[] arr = {10,11,7,6,8,9};//双旋转
        //创建一个 AVLTree对象
        AVLTree avlTree = new AVLTree();
        //添加结点
        for(int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }
        avlTree.infixOrder();
        System.out.println(avlTree.getRoot().height());
        System.out.println(avlTree.getRoot().leftHeight());
        System.out.println(avlTree.getRoot().rightHeight());
    }
}

赫夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)，还有的书翻译为霍夫曼树。

  1. 路径：在一棵树中，从一个结点往下可以达到的孩子结点或孙子结点之间的通路，称为路径。
  2. 路径长度：通路中，分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第n层结点的路径长度：为n-1。
  3. 结点的权：若将树中的结点，赋一个有着某种含义的数值，则这个数值称为该结点的权。
  4. 带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
  5. 树的带权路径长度：所有叶子结点的带权路径长度之和，记为WPL(weighted path length)。
  6. WPL最小的就是赫夫曼树，赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
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
/**
 * 节点
 */
public class Node implements Comparable<Node> {
    int value; //结点权值
    Node left; //指向左子结点
    Node right;//指向右子结点

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node node) {
        return this.value - node.value;
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if(this.left != null) {
            this.left.preOrder();
        }
        if(this.right != null) {
            this.right.preOrder();
        }
    }
}

/**
 * 赫夫曼树
 */
public class HuffmanTree {

    //将一个数组转化为赫夫曼树
    public static Node createHuffmanTree(int[] arr) {
        //将数组转化为一个个节点
        List<Node> nodes = new ArrayList<Node>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        //当集合中只有一个节点时处理完成
        while(nodes.size() > 1) {
            //从小到大排序
            Collections.sort(nodes);

            //取出值最小的两颗二叉树，创建一个新的二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node node = new Node(leftNode.getValue() + rightNode.getValue());
            node.setLeft(leftNode);
            node.setRight(rightNode);
            nodes.add(node);

            //删除刚才处理过的两个二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
        }
        //返回root节点
        return nodes.get(0);
    }
}

public class Run {

    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = HuffmanTree.createHuffmanTree(arr);
        node.preOrder();
    }

}

数据结构：图

  1. 图是一种数据结构，其中结点（顶点）可以具有零个或多个相邻元素。
    • 边：两个顶点之间的连接称为边。
    • 有权图：边带权值的图是有权图，也叫网。
    • 有向图：顶点之间单向连接是有向图。
    • 无向图：顶点之间双向连接是无向图。
  2. 图的表示方式有两种：二维数组表示（邻接矩阵）、链表表示（邻接表）。
    • 邻接矩阵
      • 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。
      • 对于n个顶点的图而言，矩阵是的row和col表示的是1….n个点。
    • 邻接表
      • 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失。
      • 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组和链表组成。
  3. 图的搜索：即是对结点的访问。一个图有很多个结点，遍历这些结点，需要特定策略，一般有两种访问策略，深度优先搜索和广度优先搜索。
    • 深度优先搜索(Depth First Search)
      1. 需要使用一个数组保存节点是否已经访问，已经访问过的节点不再访问。
      2. 从初始访问结点出发，这个结点可能有多个邻接结点，首先访问第一个邻接结点，结点加入数组。
      3. 然后再以这个被访问的邻接结点作为初始结点，继续访问第一个未被访问的邻接结点。
      4. 直到最后未找到结点的邻接结点，返回最后未找到结点的上一个节点，访问第二个未被访问邻接结点。
      5. 以第二个邻接结点作为初始结点，继续访问第二个邻接结点的第一个邻接结点。
      6. 直到最后未找到结点的邻接结点，返回该结点的上一个节点，访问第三个未被访问邻接结点。
      7. 一直递归访问，直到这个结点也没有邻接结点，在回到上一个节点，访问第二个结点，回到第四步。
    • 广度优先搜索(Broad First Search)
      1. 还需要使用一个队列保存访问过的结点顺序，按这个顺序来访问这些结点的邻接结点。
      2. 访问初始结点，并标记结点为已访问，结点加入队列。
      3. 当队列非空时，继续执行，否则算法结束。
      4. 出队列，取得队头结点，查找头结点的第一个邻接结点。
      5. 若头结点的邻接结点不存在，则转到步骤3，否则循环执行以下步骤
      6. 若结点尚未被访间，则访问结点并标记为已访问，结点加入队列。
      7. 查找头结点的邻接结点后的下一个邻接结点，转到步骤6。
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
/**
 * 图：邻接矩阵
 */
public class Graph {

    private ArrayList<String> vertexList;//存储顶点集合
    private int[][] edges;//存储图对应的邻结矩阵
    private int numOfEdges;//表示边的数目
    //定义给数组boolean[]，记录结点是否被访问
    private boolean[] isVisited;

    public Graph(int n) {
        vertexList = new ArrayList<String>(n);
        edges = new int[n][n];
        numOfEdges = 0;
        isVisited = new boolean[n];
    }

    //添加顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * v1       顶点对应的vertexList中的下标
     * v2       顶点对应的vertexList中的下标
     * weight   0：v1、v2顶点之间没有连接，1：有连接
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2]= weight;
        edges[v2][v1]= weight;
        numOfEdges++;
    }

    //返回结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //得到边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //返回结点对应的数据
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //返回v1和v2的权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    //显示图对应的矩阵
    public void showGraph() {
        for(int[] link : edges) {
            System.out.println(Arrays.toString(link));
        }
    }

    //得到传入结点的第一个邻接结点下标
    public int getFirstNeighbor(int index) {
        for(int j = 0;j < vertexList.size(); j++) {
            if(edges[index][j] > 0) {
                return j;

            }
        }
        return -1;
    }

    //根据前一个邻接结点的下标来获取下一个邻接结点的下标
    public int getNextNeighbor(int v1, int v2) {
        for(int j = v2 + 1; j < vertexList.size(); j++) {
            if(edges[v1][j] > 0){
                return j;

            }
        }
        return -1;
    }

    //深度优先遍历
    public void dfs(boolean[] isVisited, int i) {
        //首先我们访问该结点，输出
        System.out.print(getValueByIndex(i) + "=>");
        //将结点设置为已经访问
        isVisited[i] = true;
        //查找结点i的第一个邻接结点
        int w = getFirstNeighbor(i);
        while(w != -1){
            if(isVisited[w]) {//已经被访问
                w = getNextNeighbor(i, w);
            } else {//未访问
                dfs(isVisited, w);
            }
        }
    }

    //深度优先遍历所有的结点
    public void dfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
        isVisited = new boolean[getNumOfVertex()];
    }

    //广度优先遍历
    public void bfs(boolean[] isVisited, int i) {
        int u; //表示队列的头结点对应下标
        int w; //邻接结点w
        //队列，记录结点访问的顺序
        LinkedList<Integer> queue = new LinkedList<Integer>();
        //访问结点，输出结点信息
        System.out.print(getValueByIndex(i) + "=>");
        //标记为已访问
        isVisited[i]= true;
        //将结点加入队列尾部
        queue.addLast(i);
        //队列不为空循环处理
        while(!queue.isEmpty()) {
            //职出队列的头结点下标
            u = queue.removeFirst();
            //得到第一个邻接结点的下标
            w = getFirstNeighbor(u);
            //找到下一次邻接结点
            while(w != -1){
                //是否访问过
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    //标记已经访问
                    isVisited[w] = true;
                    //将结点加入队列尾部
                    queue.addLast(w);
                }
                //以u为前驱点，找w后面的下一个邻结点
                w = getNextNeighbor(u, w);//体现出广度优先
            }
        }
    }

    //广度优先遍历所有的结点
    public void bfs() {
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
        isVisited = new boolean[getNumOfVertex()];
    }
}

public class Run {
    public static void main(String[] args) {
        //顶点的值
        String[] vertexes = {"1","2","3","4","5","6","7","8"};
        //创建图对象
        Graph graph = new Graph(vertexes.length);
        //循环的添加顶点
        for(String vertex : vertexes) {
            graph.insertVertex(vertex);
        }
        //添加边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        System.out.println("查看图");
        graph.showGraph();
        System.out.println("深度优先遍历");
        graph.dfs();
        System.out.println();
        System.out.println("广度优先遍历");
        graph.bfs();
        System.out.println();
    }
}

算法：递归

阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Factorial {

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            int f = factorial(n - 1);
            int num = f * n;
            System.out.println(f + "x" + n + "=" + num);
            return num;
        }
    }

    public static void main(String[] args) {
        factorial(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
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
public class Maze {
    /**
     * 初始化迷宫地图
     * 1：是围墙，0：是可走的路
     */
    public static int[][] initMaze() {
        //迷宫为 8 x 8 格子
        int[][] map = new int[8][8];

        //左右两边加上围墙
        for (int row = 0; row < map.length; row++) {
            map[row][0] = 1;
            map[row][map[row].length - 1] = 1;
        }

        //上下两边加上围墙
        for (int col = 0; col < map.length; col++) {
            map[0][col] = 1;
            map[map.length - 1][col] = 1;
        }

        //中间加上围墙
        map[1][2] = 1;
        map[3][1] = 1;
        map[3][2] = 1;
        map[3][6] = 1;

        //查看地图
        mazeShow(map);
        return map;
    }

    /**
     * 地图展示
     */
    public static void mazeShow(int[][] map) {
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    /**
     * @param map N x N 的地图
     * @param x 起点x轴下标
     * @param y 起点y轴下标
     * @return 是否走通
     */
    public static boolean setWay(int[][] map, int x, int y) {
        //地图从[1, 1]开始走
        //走到[map.length - 2, map.length - 2] 逃出迷宫
        if (map[map.length - 2][map.length - 2] == 2) {
            return true;
        } else {
            //当为 0 时说明该店还没有走过
            if (map[y][x] == 0) {
                //走过的点标记为2
                map[y][x] = 2;
                //根据 右 -> 下 -> 左 -> 上 的行走策略
                if (setWay(map, x + 1, y)) {
                    return true;
                } else if (setWay(map, x, y + 1)) {
                    return true;
                } else if (setWay(map, x - 1, y)) {
                    return true;
                } else if (setWay(map, x, y - 1)) {
                    return true;
                } else {
                    //走不通的情况标记为3
                    map[y][x] = 3;
                    return false;
                }
            } else {
                //其他情况 1：该点是墙，2：该点已走过，3：该点走不通
                return false;
            }
        }
    }

    public static void main(String[] args) {
        int[][] ints = initMaze();
        boolean bool = setWay(ints, 1, 1);
        if (bool) {
            System.out.println("破解完成");
        } else {
            System.out.println("迷宫无解");
        }
        mazeShow(ints);
    }
}

八皇后

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，一共有多少种摆法？

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
/**
 * 八皇后问题
 */
public class Queen {
    //解法计数
    int count = 0;
    //八皇后棋盘8x8
    int[][] queenBoard;
    //摆放位置
    //[8]：代表八个皇后
    //[2]: [0] 为棋盘 X 轴坐标，[1] 为棋盘 Y 轴坐标
    int[][] position;

    public Queen() {
        queenBoard = new int[8][8];
        position = new int[8][2];

        System.out.println("棋盘下标：");
        System.out.println(" ↑");
        for (int i = 7; i >= 0; i--) {
            System.out.print(i+"|");
            for (int j = 0; j < 8; j++) {
                System.out.print(i + ","+ j + " ");
            }
            System.out.println();
        }
        System.out.println("Y|X-0--1---2---3---4---5---6---7-→");
    }

    //结果打印
    public void show() {
        System.out.println("第" + count + "种解法：");

        System.out.println(Arrays.deepToString(position));

        for (int[] ints : position) {
            queenBoard[7-ints[1]][ints[0]] = 1;
        }

        System.out.println(" ↑");
        for (int i = 0; i < queenBoard.length; i++) {
            System.out.print((7-i) + "|");
            for (int anInt : queenBoard[i]) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        System.out.println("Y|0-1-2-3-4-5-6-7-X→");

        queenBoard = new int[8][8];
    }

    private void check(int num) {
        //num 等于 9，说明已经有解，则展示解法
        if (num == 9) {
            count = count + 1;
            show();
        } else {
            //Y轴坐标为：摆放次数减1
            //X轴坐标为：0-8
            for (int i = 0; i < 8; i++) {
                //判断位置是否冲突
                if (judge(i, num - 1, num)) {
                    position[num - 1][0] = i;
                    position[num - 1][1] = num - 1;
                    check(num + 1);
                }
            }
        }
    }

    /**
     * 查看当前放置的皇后是否与之前放置的皇后有冲突
     * @param x x轴坐标
     * @param y y轴坐标
     * @param num 第几次放置
     * @return 是否冲突
     */
    public boolean judge(int x, int y, int num) {
        for (int i = 0; i < (num - 1); i++) {
            //当要放置的皇后 X 轴与之前放置的皇后 X 轴相等说明在同一列
            if (position[i][0] == x) {
                return false;
            }

            //当要放置的皇后 Y 轴与之前放置的皇后 Y 轴相等说明在同一行
            if (position[i][1] == y) {
                return false;
            }

            //当要放置的皇后 X 轴 减 之前放置的皇后 X 轴的绝对值 与
            //当要放置的皇后 Y 轴 减 之前放置的皇后 Y 轴的绝对值 相等
            //说明在同一斜线上
            if (Math.abs(x - position[i][0]) == Math.abs(y - position[i][1])) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Queen queen = new Queen();
        queen.check(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
/**
 * 顺序查找：有序/无序的数组都可以
 */
public class SeqSearch {

    public static void main(String[] args) {
        int[] arr = {1, 9, 34, 11, -1, 34, 39};
        System.out.println(seqSearch(arr, 34));
        System.out.println(seqSearchAll(arr, 34));
    }

    /**
     * 在数组中查找传入的值，返回下标，该方法只找首次命中值的下标
     * 未找到返回-1
     */
    public static int seqSearch(int[] arr, int findVal) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == findVal) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 在数组中查找传入的值，返回所有命中值的下标
     */
    public static List<Integer> seqSearchAll(int[] arr, int findVal) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == findVal) {
                result.add(i);
            }
        }
        return result;
    }

}

二分查找

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
/**
 * 二分查找：只能是有序的数组
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 89, 89, 1000, 1234};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 101));
        System.out.println(binarySearchAll(arr, 0, arr.length - 1, 89));
    }

    /**
     * 只查询第一次命中值的下标
     * @param: arr     要查找的数组
     * @param: left    左边的索引
     * @param: right   右边的索引
     * @param: findVal 要查找的值
     * @return: 如果找到就返回下标，如果没有找到，就返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //当left > right时，说明已经查找完整个数组，未找到相对应的值，则返回-1
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;//中间值下标
        int midVal = arr[mid];//中间值

        if (findVal > midVal) {//要查找的值大于中间值，则向右侧继续查找
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//要查找的值小于中间值，则向左侧继续查找
            return binarySearch(arr, left, mid - 1, findVal);
        } else {//要查找的值等于中间值，则返回下标
            return mid;
        }
    }

    /**
     * 查询所有命中值的下标
     * @param: arr     要查找的数组
     * @param: left    左边的索引
     * @param: right   右边的索引
     * @param: findVal 要查找的值
     */
    public static List<Integer> binarySearchAll(int[] arr, int left, int right, int findVal) {
        //当left > right时，说明已经查找完整个数组，未找到相对应的值，则返回空集合
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;//中间值下标
        int midVal = arr[mid];//中间值

        if (findVal > midVal) {//要查找的值大于中间值，则向右侧继续查找
            return binarySearchAll(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//要查找的值小于中间值，则向左侧继续查找
            return binarySearchAll(arr, left, mid - 1, findVal);
        } else {//要查找的值等于中间值
            List<Integer> result = new ArrayList<Integer>();
            //将下标放入返回值
            result.add(mid);
            //继续向左查找
            int temp = mid - 1;
            while (true) {
                //因为数组是有序的，所以如果下一个值不等于要查找的值，则退出
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                //与查找的值相等，放入返回值，继续查找下一个
                result.add(temp);
                temp = temp - 1;
            }
            //继续向右查找
            temp = mid + 1;
            while (true) {
                //因为数组是有序的，所以如果下一个值不等于要查找的值，则退出
                if (temp > right || arr[temp] != findVal) {
                    break;
                }
                //与查找的值相等，放入返回值，继续查找下一个
                result.add(temp);
                temp = temp + 1;
            }
            return result;
        }
    }
    
}

插值查找

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
/**
 * 插值查找：只能是有序的数组
 */
public class InsertSearch {

    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        System.out.println(insertSearch(arr, 0, arr.length - 1, 1));
        System.out.println(insertSearchAll(arr, 0, arr.length - 1, 89));
    }

    /**
     * 只查询第一次命中值的下标
     * @param: arr     要查找的数组
     * @param: left    左边的索引
     * @param: right   右边的索引
     * @param: findVal 要查找的值
     * @return: 如果找到就返回下标，如果没有找到，就返回 -1
     */
    public static int insertSearch(int[] arr, int left, int right, int findVal) {
        /**
         * 当left > right时，说明已经查找完整个数组，未找到相对应的值
         * 要查找的值小于数组中的最小值，说明数组中不存在该值
         * 要查找的值大于数组中的最大值，说明数组中不存在该值
         * 则返回-1
         */
        if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal) {
            return -1;
        }

        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);//中间值下标
        int midVal = arr[mid];//中间值

        if (findVal > midVal) {//要查找的值大于中间值，则向右侧继续查找
            return insertSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//要查找的值小于中间值，则向左侧继续查找
            return insertSearch(arr, left, mid - 1, findVal);
        } else {//要查找的值等于中间值，则返回下标
            return mid;
        }
    }

    /**
     * 查询所有命中值的下标
     * @param: arr     要查找的数组
     * @param: left    左边的索引
     * @param: right   右边的索引
     * @param: findVal 要查找的值
     */
    public static List<Integer> insertSearchAll(int[] arr, int left, int right, int findVal) {
        /**
         * 当left > right时，说明已经查找完整个数组，未找到相对应的值
         * 要查找的值小于数组中的最小值，说明数组中不存在该值
         * 要查找的值大于数组中的最大值，说明数组中不存在该值
         * 则返回-1
         */
        if (left > right || arr[0] > findVal || arr[arr.length - 1] < findVal) {
            return new ArrayList<Integer>();
        }

        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);//中间值下标
        int midVal = arr[mid];//中间值

        if (findVal > midVal) {//要查找的值大于中间值，则向右侧继续查找
            return insertSearchAll(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//要查找的值小于中间值，则向左侧继续查找
            return insertSearchAll(arr, left, mid - 1, findVal);
        } else {//要查找的值等于中间值
            List<Integer> result = new ArrayList<Integer>();
            //将下标放入返回值
            result.add(mid);
            //继续向左查找
            int temp = mid - 1;
            while (true) {
                //因为数组是有序的，所以如果下一个值不等于要查找的值，则退出
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }
                //与查找的值相等，放入返回值，继续查找下一个
                result.add(temp);
                temp = temp - 1;
            }
            //继续向右查找
            temp = mid + 1;
            while (true) {
                //因为数组是有序的，所以如果下一个值不等于要查找的值，则退出
                if (temp > right || arr[temp] != findVal) {
                    break;
                }
                //与查找的值相等，放入返回值，继续查找下一个
                result.add(temp);
                temp = temp + 1;
            }
            return result;
        }
    }

}

斐波那契查找

  1. 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。其比值是一个无理数，用分数表示为(√5-1)/2，取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这个分割点就叫做黄金分割点（golden section ratio），通常用 Φ 表示。这是一个十分有趣的数字，以0.618来近似表示，通过简单的计算就可以发现：(1-0.618)/0.618≈0.618，即一条线段上有两个黄金分割点。
  2. 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}，前两个值相加等于第三个值，以此类推。发现斐波那契数列的两个相邻数的比例：34/55，无限接近黄金分割值 0.618。
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
/**
 * 斐波那契查找：有序数列
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr = {1, 8, 89, 1000, 1234};
        System.out.println(fibSearch(arr, 89));
    }

    /**
     * 创建斐波那契数列
     * @param: length 数列长度
     */
    public static int[] fib(int length) {
        int[] f = new int[length];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < length; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    public static int fibSearch(int[] arr, int findVal) {
        int right = arr.length - 1;//原始数组最大下标值
        int[] f = fib(20);//获取斐波那契数列
        int k = 0;//斐波那契数列下标

        /**
         * 循环斐波那契数列
         * 当循环斐波那契数列中的值
         * 大于或者等于
         * 要查询的原始数组最大下标值时
         * 返回斐波那契数列的下标
         */
        for (int i = 0; i < f.length; i++) {
            if (f[i] >= right) {
                k = i;
                break;
            }
        }

        /**
         * 以原始数组为基础创建一个临时数组，数组长度为f[k]
         */
        int[] temp = new int[f[k]];
        for (int i = 0; i < arr.length; i++) {
            temp[i] = arr[i];
        }

        /**
         * 因为f[k]的值是大于等于原始数组最大下标值的
         * 所以临时数组长度大于原始数组的长度
         * 那么大于的部分需要补充值
         * 补充的值为原始数组的最后一个值
         */
        for (int i = arr.length; i < temp.length; i++) {
            temp[i] = arr[arr.length - 1];
        }

        /**
         * 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233}
         * 综上所述：如果原始数组长度为100，则临时数组的长度为144
         * 那么临时数组的黄金分割点下标就是89
         * 对比二分查找算法
         * 二分查找算法是从中间开始截取的，也就是0.5
         * 斐波那契算法是从黄金分割点截取，也就是0.618
         */
        int mid = 0;//初始化数组的黄金分割点

        /**
         * 开始查找的最小下标
         */
        int left = 0;

        //开始循环查找
        while (left <= right) {
            mid = left + f[k-1] - 1;//取到黄金分割点后，因为数组下标是从0开始的，所以需要减1
            if (findVal > temp[mid]) {//要查找的值大于中间值，则向右侧继续查找
                left = mid + 1;
                k = k - 2;
            } else if (findVal < temp[mid]) {//要查找的值小于中间值，则向左侧继续查找
                right = mid - 1;
                k = k - 1;
            } else {//要查找的值等于中间值
                /**
                 * 因为临时数组长度大于等于原始数组的长度
                 * 判断相等值的下标是否小于等于原始数组的下标
                 * 如果是则直接返回下标
                 * 判断相等值的下标大于原始数组的下标
                 * 则说明是临时数组的补充值被找到，补充值是原始数组最大下标的值
                 * 所以返回原始数组最大下标
                 */
                if (mid <= right) {
                    return mid;
                } else {
                    return right;
                }
            }
        }

        //未找到返回-1
        return -1;
    }

}

算法：排序

插入排序

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

直接插入排序

插入排序 (Insertion Sort) 的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-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
/**
 * 直接插入排序
 * 平均时间复杂度：O(n²)
 * 最坏时间复杂度：O(n²)
 * 稳定度：稳定
 * 额外空间：O(1)
 * 备注：数据大部分已排序的时候较好
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {3, 9, 1, 10, 12};

        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];
            for (int n = i - 1; n >= 0; n--) {
                if (arr[n] > insertValue) {
                    arr[n + 1] = arr[n];
                    arr[n] = insertValue;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

}

希尔排序

希尔排序是希尔 (DonaldShell Sort) 于1959年提出的一种排序算法。希尔排序也是种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序.随着增量逐渐减少，每组包含的关键词越来越多，当增量减至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
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 希尔排序
 * 平均时间复杂度：O(n㏒n)
 * 最坏时间复杂度：O(n的s次方 1 < s < 2)
 * 稳定度：不稳定
 * 额外空间：O(1)
 * 备注：s是所选分组
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellMove(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序：插入法
     */
    private static void shellInsert(int[] arr) {
        int temp = 0;
        //开始分组 10长度 -> 5组 -> 2组 -> 1组
        for (int group = (arr.length / 2); group > 0; group /= 2) {
            for (int i = group; i < arr.length; i++) {
                for (int n = (i - group); n >= 0; n-=group) {
                    System.out.print(arr[n] +":"+ arr[n + group] + "\t");
                    if (arr[n] > arr[n + group]) {
                        temp = arr[n];
                        arr[n] = arr[n + group];
                        arr[n + group] = temp;
                    }
                }
                System.out.println();
            }
            System.out.println("-----");
        }
    }

    /**
     * 希尔排序：移位法
     */
    private static void shellMove(int[] arr) {
        //增量gap，并逐步的缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
}

选择排序

选择式排序属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

简单选择排序

选择排序 (Select Sort) 也是一种简单的排序方法。它的基本思想是：第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]-arr[n-1]中选取最小值，与arr[2]交换，···，第i次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]交换，···，第n-1次从arr[n-2]-arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-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
/**
 * 选择排序
 * 平均时间复杂度：O(n²)
 * 最坏时间复杂度：O(n²)
 * 稳定度：不稳定
 * 额外空间：O(1)
 * 备注：n小的时候比较好
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {3, 9, 1, 10, 12};//要排序的数组

        //可以少循环一次，因为其他数字位置都确定了，最后一个数字也就确定了
        for (int i = 0; i < arr.length - 1; i++) {
            //最小值下标
            int index = i;
            //最小的值
            int indexValue = arr[i];
            //循环取出再小的值跟对应的下标
            for (int n = 1 + i; n < arr.length; n++) {
                if (indexValue > arr[n]) {
                    index = n;
                    indexValue = arr[n];
                }
            }

            //判断最初下标是否改变
            if (index != i) {
                arr[index] = arr[i];
                arr[i] = indexValue;
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

堆排序

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它也是不稳定排序，堆也是完全二叉树。
  2. 每个结点的值都大于或等于其左右子结点的值称为大顶堆，左节点的值和右节点的值的没有大小关系区分。
  3. 大顶堆特点，数组储存:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]，i对应第几个节点，i从0开始。
  4. 每个结点的值都小于或等于其左右子结点的值，称为小顶堆。
  5. 小顶堆特点，数组储存:arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]，i对应第几个节点，i从0开始。
  6. 一般升序采用大顶堆，降序采用小顶堆。
  7. 堆排序使用的都是数组储存二叉树的结构：数组二叉树
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
/**
 * 堆排序
 * 平均时间复杂度：O(n㏒n)
 * 最坏时间复杂度：O(n㏒n)
 * 稳定度：不稳定
 * 额外空间：O(1)
 * 备注：n大时较好
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);

    }

    public static void heapSort(int arr[]) {
        //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆，升序采用大顶堆，降序采用小顶堆
        int nodeCount = arr.length /2 - 1;//一共有多少个非叶子节点
        for(int i = nodeCount; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        System.out.println("数组转化为大顶堆："+ Arrays.toString(arr));

        int temp = 0;
        for(int j = arr.length - 1; j > 0; j--) {
            //将堆顶元素与末尾元素交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            //重新调整结构：数组长度去除调整后的长度，剩下的数组使其满足堆定义
            adjustHeap(arr,0, j);
        }
        System.out.println("排序后数组："+ Arrays.toString(arr));
    }

    /**
     * 将一个数组(二叉树)，调整成一个大项堆
     * 将 以 i 对应的非叶子结点的树调整成大顶堆
     * @param: arr：待调整的数组
     *           i：表示非叶子结点在数组中索引
     *      length：表示对多少个元素继续调整，length 是在逐渐的减少
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//当前节点的值

        //2 * i + 1：当前节点的左子节点对应的数组中的下标
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            //左子节点的值小于右子节点的值
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k = k + 1;//将指向右子节点
            }
            //子节点的值大于父节点
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }

        //当for循环结束后，我们已经将以i为父结点的树的最大值，放在了顶部
        arr[i] = temp;//将temp值放到调整后的位置
    }
}

交换排序

冒泡排序

冒泡排序 (Bubble Sort) 的基本思想是：通过对待排序序列从前向后 (从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。因为排序的过程中，各元素不断接近自己的位置，如果一圈比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

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
/**
 * 冒泡排序
 * 平均时间复杂度：O(n²)
 * 最坏时间复杂度：O(n²)
 * 稳定度：稳定
 * 额外空间：O(1)
 * 备注：n小的时候比较好
 */
public class BubbleSort {
    //从小到大排序
    public static void main(String[] args) {
        int[] arr = {3, 9, 1, 10, 12};//要排序的数组
        int temp = 0;//临时变量
        boolean flag = false;//标识是否进行过交换

        //可以少循环一次，因为其他数字位置都确定了，最后一个数字也就确定了
        for (int i = 0; i < arr.length - 1; i++) {
            for (int n = 0; n < arr.length - 1 - i; n++) {
                if (arr[n] > arr[n + 1]) {
                    temp = arr[n];
                    arr[n] = arr[n + 1];
                    arr[n + 1] = temp;
                    flag = true;
                }
            }

            if (!flag) {//一次交换都没有产生则已经排序完成，退出循环
                break;
            } else {//重置标识，进行下一次对比
                flag = false;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

快速排序

快速排序 (Quick Sort) 是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

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
/**
 * 快速排序
 * 平均时间复杂度：O(n㏒n)
 * 最坏时间复杂度：O(n²)
 * 稳定度：不稳定
 * 额外空间：O(n㏒n)
 * 备注：n大时较好
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, -789, 23, -567, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param: arr 要排序的数组
     * @param: left 数组排序最左侧下标
     * @param: right 数组排序最右侧下标
     */
    public static void quickSort(int[] arr, int left, int right) {
        int l = left;//左下标
        int r = right;//右下标
        //中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量，用于交换时使用
        int temp;

        // 从小到大排序
        // 比 pivot 值小放到 pivot 左边
        // 比 pivot 值大放到 pivot 右边
        while (l < r){
            //在中轴左侧找到一个大于等于中轴值的数退出
            //最多循环到中轴的下标位置，跟中轴值相等，退出
            while (arr[l] < pivot) {
                l = l + 1;
            }

            //在中轴右侧找到一个小于等于中轴值的数退出
            //最多循环到中轴的下标位置，跟中轴值相等，退出
            while (arr[r] > pivot) {
                r = r - 1;
            }

            //左侧大于等于右侧时，处理完毕退出
            if (l >= r) {
                break;
            }

            //交换位置
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //在循环找值的过程中，如果一个值恰好跟中轴值相等，
            //但这个值之后还有其他的值要处理，那么后边的值就会处理不到
            //为了解决这种情况：
            //左侧的下标+1，跳过这个值，继续处理下一个值
            if (arr[r] == pivot) {//arr[r]这个值是刚从右侧交换到左侧的值
                l = l + 1;
            }
            //右侧的下标-1，跳过这个值，继续处理下一个值
            if (arr[l] == pivot) {//arr[l]这个值是刚从左侧交换到右侧的值
                r = r - 1;
            }
        }

        //如果 l == r，那么需要 l + 1，r - 1，否则就死循环了
        if(l == r) {
            l = l + 1;
            r = r - 1;
        }

        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }

        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

归并排序

归并排序 (Merge Sort) 是利用归并的思想实现的排序方法，该算法采用经典的分治 (divide-and-conquer) 策略。分治法将问题分 (divide) 成一些小的问题然后递归求解，而治 (conquer) 的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。

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
/**
 * 归并排序
 * 平均时间复杂度：O(n㏒n)
 * 最坏时间复杂度：O(n㏒n)
 * 稳定度：稳定
 * 额外空间：O(1)
 * 备注：n大时较好
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {8, 5, 4, 6, 1, 3, 7, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序是：先分解再合并的过程，在合并的时候进行排序
     * @param: arr 要排序的数组
     * @param: left 数组最左边的下标
     * @param: mid 数组中间的下标
     * @param: right 数组最右边的下标
     * @param: temp 临时数组
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            mergeSort(arr, left, mid, temp);//数组左侧到中间分解
            mergeSort(arr, mid + 1, right, temp);//从中间到数组右侧分解
            merge(arr, left, mid, right, temp);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左边数组的初始索引
        int j = mid + 1;//右边数组的初始索引
        int t = 0;//临时数组的当前索引

        //先把左右两边的数组按照规则填充到临时数组
        //直到左右两边有一边处理完毕为止
        while (i <= mid && j <= right) {//从小到大排序
            //左边数组的值跟右侧数组的值比较大小
            if (arr[i] <= arr[j]) {//如果左侧的小于右侧的，则把左侧的值放入临时数组
                temp[t] = arr[i];
                t = t + 1;
                i = i + 1;
            } else {//如果左侧的大于右侧的，则把右侧的值放入临时数组
                temp[t] = arr[j];
                t = t + 1;
                j = j + 1;
            }
        }

        //如果有一侧有剩余未处理的数据，则依次填充到temp
        while (i <= mid) {
            temp[t] = arr[i];
            t = t + 1;
            i = i + 1;
        }
        while (j <= right) {
            temp[t] = arr[j];
            t = t + 1;
            j = j + 1;
        }

        //将temp的数据放入到原始数组中
        int arrIndex = left;
        for (int n = 0; n < t; n++) {
            arr[arrIndex] = temp[n];
            arrIndex = arrIndex + 1;
        }
    };
}

基数排序

基数排序 (Radix Sort) 属于“分配式排序” (distribution sort)，又称“桶子法” (Bucket Sort) 或 (Bin Sort)，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

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
/**
 * 基数排序
 * 平均时间复杂度：O(㏒RB)
 * 最坏时间复杂度：O(㏒RB)
 * 稳定度：稳定
 * 额外空间：O(n)
 * 备注：B是真数（0-9），R是基数（个十百）
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //只适用于正整数的数组排序
    public static void radixSort(int[] arr) {
        //定义一个二维数组，用来存放数据
        //10是0-9对应的值，把对应位数的值放入相对应的桶中
        int[][] bucket = new int[10][arr.length];
        //记录每个桶存入的数值个数
        int[] bucketCount = new int[bucket.length];

        //得到数组中最大的数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        //计算最大的数一共有几位
        int maxLength = (max + "").length();

        //循环处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //i=0个位数，i=1十位数，i=2百位数，以此类推
            for (int j = 0; j < arr.length; j++) {
                int bucketNum = arr[j] / n % 10;//取出对应位数的值
                int bucketIndex = bucketCount[bucketNum];//相对应值的桶中已经存放数据的个数
                bucket[bucketNum][bucketIndex] = arr[j];//将数据存入相对应值的桶中
                bucketCount[bucketNum] = bucketCount[bucketNum] + 1;//相对应值的桶中已经存放数据的个数+1
            }

            //取出桶中的数据放入原始数组中
            int index = 0;
            for (int j = 0; j < bucket.length; j++) {
                //该桶中存放数据的数量
                int bucketIndex = bucketCount[j];
                //判断该桶中是否存放了数据
                if (bucketIndex > 0) {
                    //取出数据放入原始数组中
                    for (int k = 0; k < bucketIndex; k++) {
                        arr[index] = bucket[j][k];
                        index = index + 1;
                    }
                    //取完数据后将bucketCount初始化为0
                    bucketCount[j] = 0;
                }
            }
        }
    }
}

算法：压缩

赫夫曼编码

赫夫曼编码也翻译为：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，是可变字长编码(VLC)的一种，属于一种程序算法。

赫夫曼编码是赫夫曼树在电讯通信中的经典的应用之一。广泛地用于数据文件压缩，其压缩率通常在20%~90%之间。

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
/**
 * 二叉树节点
 */
public class Node implements Comparable<Node> {
    int weight;//结点权值
    Byte data;//存放数据
    Node left;//指向左子结点
    Node right;//指向右子结点

    public Node(int weight, Byte data) {
        this.weight = weight;
        this.data = data;
    }

    @Override
    public int compareTo(Node node) {
        return this.weight - node.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "weight=" + weight +
                ", data=" + data +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preorder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preorder();
        }
        if (this.right != null) {
            this.right.preorder();
        }
    }
}

/**
 * 算法：赫夫曼编码
 */
public class HuffmanCode {

    //赫夫曼编码
    private Map<Byte, String> huffmanCodes;

    //最后一个二进制字符，因为不确定是多少位，所以需要储存
    private String endBinaryString;

    public HuffmanCode() {
        this.huffmanCodes = new HashMap<>();
    }

    public Map<Byte, String> getHuffmanCodes() {
        return huffmanCodes;
    }

    public String getEndBinaryString() {
        return endBinaryString;
    }

    /**
     * 文件加密
     */
    public byte[] encrypt(byte[] bytes) {
        //将源数据转化为node节点
        List<Node> nodes = this.getNodes(bytes);
        //转化为赫夫曼树
        Node huffmanTree = this.createHuffmanTree(nodes);
        //创建赫夫曼编码
        this.createHuffmanCode(huffmanTree);
        //bytes 根据赫夫曼编码加密
        return this.encryptHuffmanCodeBytes(bytes, this.huffmanCodes);
    }

    /**
     * 根据赫夫曼编码将原byte[]加密，返回加密后的byte[]
     */
    private byte[] encryptHuffmanCodeBytes(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //利用赫夫曼编码将 bytes 转成对应的赫夫曼编码的路径，拼接为字符串
        StringBuffer buffer = new StringBuffer();
        for (byte b : bytes) {
            //获取 byte 所对应的赫夫曼树的编码（路径）
            String path = huffmanCodes.get(b);
            //拼接编码（路径）
            buffer.append(path);
        }

        //将编码字符串转化为byte[]
        int len;//计算byte[]的长度
        if(buffer.length() % 8 == 0) {
            len = buffer.length() / 8;
        } else {
            len =buffer.length() / 8 + 1;
        }//简单写：int len = (buffer.length() + 7 ) / 8;

        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;//记录是第几个byte
        for(int start = 0; start < buffer.length(); start += 8) {
            //每八位组成一个二进制编码
            int end = start + 8 > buffer.length() ? buffer.length() : start + 8;
            String binaryString = buffer.substring(start, end);
            //二进制编码转为 byte，放入到 huffmanCodeBytes
            if (end == buffer.length()) {
                this.endBinaryString = binaryString;
            }
            huffmanCodeBytes[index] = (byte) Integer.parseInt(binaryString,2);
            index = index + 1;
        }
        return huffmanCodeBytes;
    }

    /**
     * 文件解密
     */
    public byte[] decrypt(byte[] bytes, Map<Byte, String> huffmanCodes, String endBinaryString) {
        //将加密后的byte[]转化为赫夫曼编码字符串
        StringBuffer buffer = new StringBuffer();
        for (int index = 0; index < bytes.length; index++) {
            byte b = bytes[index];
            //将byte转为二进制字符串
            //b&0xFF:确保以无符号整数的方式来解释byte值，从而得到正确的二进制表示
            String binaryString = Integer.toBinaryString(b&0xFF);
            binaryString = String.format("%8s", binaryString).replace(' ', '0');
            if (index != bytes.length - 1) {
                buffer.append(binaryString);
            } else {
                buffer.append(endBinaryString);
            }
        }

        //获取反向的赫夫曼编码 Key->value、value->key
        Map<String, Byte> map = new HashMap<String, Byte>();
        for(Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        //创建集合，存放byte
        List<Byte> byteList = new ArrayList<>();
        //i 可以理解成就是索引,扫描 stringBuilder
        for(int i = 0; i < buffer.length();) {
            int count = 1;//小的计数器
            boolean flag = true;
            Byte b = null;
            while(flag){
                String key = buffer.substring(i, i+count);
                //i不动，让count移动，指定匹配到一个字符
                b = map.get(key);
                if(b == null){//说明没有匹配到
                    count = count + 1;
                } else {//匹配到
                    i = count + i;
                    flag = false;
                }
            }
            byteList.add(b);
        }

        //获取原始数据
        byte[] byteArray = new byte[byteList.size()];
        for (int i = 0; i < byteList.size(); i++) {
            byteArray[i] = byteList.get(i);
        }
        return byteArray;
    }

    /**
     * 创建赫夫曼编码
     */
    private void createHuffmanCode(Node huffmanTree) {
        //处理root的左子树
        getCodes(huffmanTree.left,"0", new StringBuffer());
        //处理root的右子树
        getCodes(huffmanTree.right,"1", new StringBuffer());
    }

    /**
     * 获取子叶结点的路径，以编码的形式表示出来，并放入到huffmanCodes集合
     * @param: node 赫夫曼树,
     *         code 编码(左子结点是0、右子结点是1)
     *         path 路径
     */
    private void getCodes(Node node, String code, StringBuffer path) {
        StringBuffer buffer = new StringBuffer(path);
        buffer.append(code);
        if(node != null) {//如果node == null不处理
            // 判断当前node 是叶子结点还是非叶子结点
            if (node.data == null) { //非叶子结点
                //向左递归
                getCodes(node.left, "0", buffer);
                //向右递归
                getCodes(node.right, "1", buffer);
            } else {//说明是一个叶子结点
                //就表示找到某个叶子结点的最后
                huffmanCodes.put(node.data, buffer.toString());
            }
        }
    }

    /**
     * 将数据转化为赫夫曼树
     */
    private Node createHuffmanTree(List<Node> nodes) {
        while(nodes.size() > 1) {//当集合中只有一个节点时处理完成
            //从小到大排序
            Collections.sort(nodes);

            //取出值最小的两颗二叉树，创建一个新的二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node node = new Node(leftNode.weight + rightNode.weight, null);
            node.left = leftNode;
            node.right = rightNode;
            nodes.add(node);

            //删除刚才处理过的两个二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
        }
        //返回root节点
        return nodes.get(0);
    }

    /**
     * 将数据转化为一个个节点
     */
    private List<Node> getNodes(byte[] bytes) {
        //用于统计每一个byte出现的次数
        Map<Byte, Integer> weights = new HashMap<>();
        for (byte b : bytes) {
            Integer weight = weights.get(b);
            if(weight == null){
                weights.put(b, 1);
            } else {
                weights.put(b, weight + 1);
            }
        }
        //将数组转化为一个个节点
        List<Node> nodes = new ArrayList<Node>();
        weights.forEach((b, weight) -> {
            Node node = new Node(weight, b);
            nodes.add(node);
        });
        return nodes;
    }

}

public class Run {

    public static void main(String[] args) {
        String srcFile = "C:\\Users\\Administrator\\Desktop\\1.jpg";//文件上传路径
        String dstFile = "C:\\Users\\Administrator\\Desktop\\1.zip";//文件下载路径
        encrypt(srcFile, dstFile);
        String dstFile1 = "C:\\Users\\Administrator\\Desktop\\11.jpg";//解密文件下载路径
        decrypt(dstFile, dstFile1);
    }

    private static void encrypt(String srcFile, String dstFile) {
        FileInputStream is = null;//文件输入流
        OutputStream os = null;//文件输出流
        ObjectOutputStream oos = null;//对象输出流
        try {
            //获取上传文件
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] contentBytes = new byte[is.available()];
            //读取文件
            is.read(contentBytes);

            //初始化
            HuffmanCode huffmanCode = new HuffmanCode();
            //加密文件
            byte[] byteCodes = huffmanCode.encrypt(contentBytes);
            //加密编码
            Map<Byte, String> huffmanCodes = huffmanCode.getHuffmanCodes();
            //最后一位编码
            String endBinaryString = huffmanCode.getEndBinaryString();

            //创建文件的输出流，存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(byteCodes);
            //放入加密编码是为了以后我们恢复源文件时使用
            oos.writeObject(huffmanCodes);
            //最后一个二进制字符，因为不确定是多少位，所以需要储存
            oos.writeObject(endBinaryString);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                if (is != null) {
                    is.close();
                }
                if (os != null) {
                    os.close();
                }
                if (oos != null) {
                    oos.close();
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    public static void decrypt(String srcFile, String dstFile) {
        //定义文件输入流
        InputStream is = null;//输入流
        ObjectInputStream ois = null;//对象输入流
        OutputStream os = null;//文件输出流
        try {
            //创建文件输入流
            is = new FileInputStream(srcFile);
            //创建一个和 is 关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            //最后一位字符
            String endBinaryString = (String) ois.readObject();

            //初始化
            HuffmanCode huffmanCode = new HuffmanCode();
            //解密
            byte[] decrypt = huffmanCode.decrypt(huffmanBytes, huffmanCodes, endBinaryString);
            //下载文件
            os = new FileOutputStream(dstFile);
            os.write(decrypt);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                if (is != null) {
                    is.close();
                }
                if (ois != null) {
                    ois.close();
                }
                if (os != null) {
                    os.close();
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

}

算法：常用

分治算法

分治法在每一层递归上都有三个步骤

  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
/**
 * 分治算法
 */
public class Dac {
    public static void main(String[] args) {
        hanoiTower(2,'A','B','C');
    }

    /**
     * 分治算法解决：汉诺塔问题
     * @param: num 盘子的数量
     *           a a塔
     *           b b塔
     *           c c塔
     * @return: void
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        //如果只有一个盘
        if(num == 1) {
            System.out.println("第1个盘从 " + a +"->"+ c);
        } else {
            //如果我们有num >= 2情况，我们总是可以看做是两个盘 1.最下边的一个盘 2.上面的所有盘
            // 1.先把最上面的所有盘 A -> B，移动过程会使用到C塔
            hanoiTower(num - 1, a, c, b);
            // 2.把最下边的盘 A -> C
            System.out.println("第"+ num + "个盘从 "+ a +"->" + c);
            // 3.把B塔的所有盘从 B -> C，移动过程使用到A塔
            hanoiTower(num - 1, b, a, c);
        }
    }
}

贪心算法

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。

贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似最优解的结果。

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
/**
 * 贪心算法
 */
public class Greedy {
    public static void main(String[] args) {
        List<String> greedy = greedy();
        System.out.println(greedy);
    }

    /**
     * 贪心算法解决集合覆盖问题
     * 假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。
     * 如何选择最少的广播台，让所有的地区都可以接收到信号。
     * 地区："北京","上海","天津","广州"，"深圳”"成都""杭州","大连"
     * 电台         覆盖地区
     * k1     "北京","上海","天津"
     * k2     "广州","北京","深圳"
     * k3     "成都","上海","杭州"
     * k4     "上海","天津"
     * k5     "杭州","大连"
     */
    public static List<String> greedy() {
        //初始化地区
        HashSet<String> allAreas = new HashSet<String>();
        allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津");
        allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都");
        allAreas.add("杭州");  allAreas.add("大连");
        //初始电台
        HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
        HashSet<String> hashSet1 = new HashSet<String>();
        hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津");
        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州"); hashSet2.add("北京"); hashSet2.add("深圳");
        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州");
        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海"); hashSet4.add("天津");
        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州"); hashSet5.add("大连");
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        //存放选择的电台集合
        ArrayList<String> selects = new ArrayList<String>();
        //定义一个临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有盖的地区的交集
        HashSet<String> tempSet =new HashSet<String>();
        //保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
        String maxKey;
        //如果allAreas不为0，则表示还没有覆盖到所有的地区
        while(allAreas.size() != 0) {
            //每进行一次while,需要
            maxKey = null;
            //遍历 broadcasts，取出对应key
            for(String key : broadcasts.keySet()) {
                tempSet.clear();
                //当前这个key能够覆盖的地区
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求出tempSet 和 allAreas 集合的交集，交集会赋给 tempSet
                tempSet.retainAll(allAreas);
                //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多//就需要重置maxKey
                if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }

            if(maxKey != null) {
                //将maxKey 加入selects
                selects.add(maxKey);
                //将maxKey指向的广播电台盖的地区，从allreas去掉
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        return selects;
    }
}

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

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
/**
 * 回溯算法
 */
public class Backtracking {
    public static void main(String[] args) {
        int row = 1;//马儿初始位置的行
        int column = 3;//马儿初始位置的列
        int[][] chessboard = new int[X][Y];//创建棋盘
        long start = System.currentTimeMillis();
        backtracking(chessboard, row, column, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时:"+(end-start)+"秒");
        //输出棋盘的最后情况
        for(int[] rows : chessboard) {
            for(int step : rows) {
                System.out.print(step +"\t");
            }
            System.out.println();
        }
    }

    private static int X = 6; //棋盘的列数
    private static int Y = 6; //棋盘的行数
    private static boolean[] visited = new boolean[X * Y];//标记棋盘的各个位置是否被访问过
    private static boolean  finished;//标记棋盘的所有位置是否都被访问

    /**
     * 回溯算法解决马踏棋盘问题
     * @param chessboard    棋盘
     * @param row           马儿当前的位置的行 从0开始
     * @param column        马儿当前的位置的列 从0开始
     * @param step          是第几步，初始位置就是第1步
     */
    public static void backtracking(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        visited[row * X + column] = true;//标记该位置已经访问
        //马儿的当前位置
        Point point = new Point(column, row);
        //获取马儿的下一个位置
        ArrayList<Point> ps = next(point);
        //减少回溯次数//从小到大排序
        sort(ps);
        while(!ps.isEmpty()) {
            //取出下一个可以走的位置
            Point p = ps.remove(0);
            //判断该点是否已经访问过
            if(!visited[p.y * X + p.x]){//说明还没有访问过
                backtracking(chessboard, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务，使用step和应该走的步数比较，
        //如果没有达到数量，则表示没有完成任务，将整个盘置0
        //1：棋盘到目前位置,仍然没有走完
        //2：棋盘处于一个回溯过程
        if(step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    //根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中
    public static ArrayList<Point> next(Point curPoint){
        //马儿可以走哪些位置
        ArrayList<Point> ps = new ArrayList<Point>();
        //下一个位置
        Point p1 = new Point();
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这个一步的所有的下一步的选择位置，进行非递减排序
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>(){
            @Override
            public int compare(Point o1, Point o2){
                //获取到o1的下一步的所有位置个数
                int count1 = next(o1).size();
                //获取到o2的下一步的所有位置个数
                int count2 = next(o2).size();
                if(count1< count2) {
                    return -1;
                } else if(count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}

KMP算法

KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。

KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回湖时，通过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
/**
 * KMP算法
 */
public class KMP {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int violenceMatch = violenceMatch(str1, str2);
        System.out.println("index=" + violenceMatch);
        int kmp = kmp(str1, str2);
        System.out.println("index=" + kmp);
    }

    /**
     * KMP算法解决字符串匹配问题
     * 有一个字符串一和另一个字符串二
     * 现在要判断字符串一中是否含有字符串二
     * 如果存在，就返回第一次出现的位置，如果没有则返回-1
     */
    public static int kmp(String str1, String str2) {
        //获取要查询字符串的部份匹配表
        int[] next = kmpNext(str2);
        for(int i = 0, j = 0; i < str1.length(); i++){
            //KMP算涵核心点
            while(j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j-1];
            }

            if(str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    //获职到一个字符串(子串))的部分匹配值表
    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        for(int i = 1, j = 0; i < dest.length(); i++) {
            while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    //暴力匹配算法实现
    public static int violenceMatch(String str1, String str2) {
        char[]s1 = str1.toCharArray();
        char[]s2 = str2.toCharArray();
        int siLen = s1.length;
        int s2Len = s2.length;
        int i = 0;// i泰引指向s1
        int j = 0;//j索引指向s2
        while(i < siLen && j < s2Len){// 保证匹配时，不越界
            if(s1[i] == s2[j]) {//匹配成功
                i++;
                j++;
            } else{//匹配失配
                i = i - (j - 1);
                j = 0;
            }
        }
        if (j == s2Len) {
            return i - j;
        }
        return -1;
    }
}

普里姆算法

普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。

  1. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
  2. 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1
  3. 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边(ui,vj)加入集合D中，标记visited[vj]=1
  4. 重复步骤2，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-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
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
/**
 * 普里姆算法
 */
public class Prim {
    public static void main(String[] args) {
        //初始化村庄路线图
        char[] data = new char[] {'A','B','C','D','E','F','G'};
        int verxs = data.length;//村庄个数
        //邻接矩阵的关系使用二维数组表示//0表示不连通，其他表示距离
        int[][] weight = new int[][] {
                //A B C D E F G (A-B距离是5，A-C距离是7，A-D不连通)
                {0,5,7,0,0,0,2},//A
                {5,0,0,9,0,0,3},//B
                {7,0,0,0,8,0,0},//C
                {0,9,0,0,0,4,0},//D
                {0,0,8,0,0,5,4},//E
                {0,0,0,4,5,0,6},//F
                {2,3,0,0,4,6,0} //G
        };
        //创建MGraph对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //输出
        minTree.showGraph(graph);
        prim(graph, 0);
    }

    /**
     * 普里姆算法解决村庄修路问题
     * 有胜利乡有7个村庄(A,B,C,D,E,F,G)，如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
     * @param graph 村庄路线图
     * @param v     村庄下标
     */
    public static void prim(MGraph graph, int v) {
        //标记结点(村庄)是否被访问过
        int[] visited = new int[graph.verxs];
        //把当前这个结点标记为已访问
        visited[v] = 1;
        //h1 和 h2 记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000;//初始成一个大数，后面在遍历过程中，会被替换
        //因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边
        for(int k= 1; k < graph.verxs; k++) {
            //这个是确定每一次生成的子图，和哪个结点的距离最近
            // i结点表示被访问过的结点
            for(int i = 0; i < graph.verxs; i++) {
                //j结点表示还没有访问过的结点
                for(int j = 0; j < graph.verxs; j++) {
                    if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] != 0 && graph.weight[i][j] < minWeight) {
                        //替换minweight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //找到一条边是最小
            System.out.println("边<" + graph.data[h1] + ","+ graph.data[h2] + ">权值:" + minWeight);
            //将当前这个结点标记为已经访问
            visited[h2] = 1;
            //重新设置
            minWeight = 10000;
        }
    }
}

//创建最小生成树->村庄的图
class MinTree {
    /**
     * 创建图的邻接矩阵
     * @param: graph    图对象
     * @param: verxs    图对应的顶点个数
     * @param: data     图各个顶点的值
     * @param: weight   图的邻接矩阵
     * @return: void
     */
    public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
        int i, j;
        for(i = 0; i < verxs; i++) {
            graph.data[i] = data[i];
            for(j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    //显示图的邻接矩阵
    public void showGraph(MGraph graph) {
        for(int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
}

class MGraph {
    int verxs;//表示图的节点个数
    char[] data;//存放结点数据
    int[][] weight;//存放边，就是我们的邻接矩阵
    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}

二分查找算法

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 class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,3,8,10,11,67,100};
        int index = bs(arr, 1);
        System.out.println(index);
    }

    /**
     * @param arr    待查找的数组，arr是升序排序
     * @param target 需要查找的数
     * @return 返回对应下标，-1表示没有找到
     */
    public static int bs(int[] arr, int target) {
        int left = 0;
        int right = arr.length -1;
        while(left <= right) { //说明继续查找
            int mid = (left + right) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid -1;//需要向左边查找
            } else {
                left = mid + 1;//需要向右边查找
            }
        }
        return -1;
    }
}

动态规划算法

动态规划(Dynamic Programming)算法的核心思想是，将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，动态规划适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

动态规划可以通过填表的方式来逐步推进，得到最优解。

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
/**
 * 动态规划算法
 */
public class Dynamic {
    public static void main(String[] args) {
        knapsackProblem();
    }

    /**
     * 动态规划算法解决背包问题
     * 指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。
     * 其中又分01背包（每种物品不可重复）和完全背包（每种物品可以重复)
     * 这个问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
     */
    public static void knapsackProblem() {
        int[] w = {1,4,3};//物品的重量
        int[] val = {1500,3000,2000};//物品的价值
        int m = 4;//背包的容量
        int n = val.length;//物品的个数
        //表示能够装入背包的最大价值
        int[][] v = new int[n+1][m+1];
        //最大价值所对应的物品
        int[][] p = new int[n+1][m+1];

        for(int i = 1; i < v.length; i++) {
            for (int j = 0; j < v[0].length; j++) {
                if (w[i-1] > j) {
                    v[i][j] = v[i-1][j];
                } else {
                    if(v[i-1][j] < val[i-1] + v[i-1][j-w[i -1]]) {
                        v[i][j] = val[i-1] + v[i-1][j-w[i -1]];
                        p[i][j] = 1;
                    } else {
                        v[i][j] = v[i-1][j];
                    }
                }
            }
        }

        //背包价值
        for(int i = 0; i < v.length; i++) {
            System.out.println(Arrays.toString(v[i]));
        }
        int i = p.length -1;//行的最大下标
        int j= p[0].length-1;//列的最大下标
        while(i > 0 && j > 0) {
            if(p[i][j] == 1) {
                System.out.printf("第%d个商品放入到背包\n", i);
                j-= w[i-1];
            }
            i--;
        }
    }
}

弗洛伊德算法

弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。

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
/**
 * 弗洛伊德算法
 */
public class Floyd {
    private static final int N = 65535;

    public static void main(String[] args) {
        //初始化图
        char[] vertexs ={'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                //N 表示顶点不连通
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/{ 0,   5,   7,   N,   N,   N,   2},
                /*B*/{ 5,   0,   N,   9,   N,   N,   3},
                /*C*/{ 7,   N,   0,   N,   8,   N,   N},
                /*D*/{ N,   9,   N,   0,   N,   4,   N},
                /*E*/{ N,   N,   8,   N,   0,   5,   4},
                /*F*/{ N,   N,   N,   4,   5,   0,   6},
                /*G*/{ 2,   3,   N,   N,   4,   6,   0},
        };
        FGraph graph = new FGraph(vertexs, matrix);
        floyd(graph);
        graph.print();//图信息
    }

    /**
     * 迪杰斯特拉算法解决最短路径问题
     * 有7个村庄(A,B,C,D,E,F,G)
     * 计算出各村庄到其它各村庄的最短距离?
     * @param graph 图对象
     */
    public static void floyd(FGraph graph) {
        //从各个顶点出发到其它顶点的距离
        int[][] dis = graph.dis;
        //到达目标顶点的前驱顶点
        int[][] pre = graph.pre;

        int len = 0;//保存距离
        for(int k = 0; k < dis.length; k++) {
            //从i顶点开始出发
            for(int i = 0; i < dis.length; i++) {
                //到经过k中间顶点，到达j顶点距离
                for(int j = 0; j < dis.length; j++) {
                    len = dis[i][k] + dis[k][j];
                    if(len < dis[i][j]) {
                        dis[i][j] = len;//更新距离
                        pre[i][j] = pre[k][j];//更新前驱项点
                    }
                }
            }
        }
    }
}

//图
class FGraph {
    char[] vertexs;//顶点数组
    int[][] matrix;//邻接矩阵
    int[][] dis;//从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
    int[][] pre;//到达目标顶点的前驱顶点

    public FGraph(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
        this.dis = matrix;
        this.pre = new int[vertexs.length][vertexs.length];
        //对pre数组初始化，注意存放的是前驱顶点的下标
        for(int i = 0; i < vertexs.length; i++) {
            Arrays.fill(pre[i], i);
        }
    }

    //显示图
    public void print() {
        System.out.println("图为:");
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d", matrix[i][j]);
            }
            System.out.println();
        }

        System.out.println("到达目标顶点的前驱顶点为:");
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = 0; j < vertexs.length; j++) {
                System.out.printf("%c", vertexs[pre[i][j]]);
            }
            System.out.println();
        }

        System.out.println("从各个顶点出发到其它顶点的距离为:");
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = 0; j < vertexs.length; j++) {
                System.out.printf("(" + vertexs[i] + "到" + vertexs[j] + "的最短路径是:%10d)", dis[i][j]);
            }
            System.out.println();
        }
    }
}

克鲁斯卡尔算法

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。

具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。

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
/**
 * 克鲁斯卡尔算法
 */
public class Kruskal {

    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        //初始化图
        char[] vertexs ={'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                //0 表示顶点本身，INF 表示顶点不连通
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/{  0,  12, INF, INF, INF,  16,  14},
                /*B*/{ 12,   0,  10, INF, INF,   7, INF},
                /*C*/{INF,  10,   0,   3,   5,   6, INF},
                /*D*/{INF, INF,   3,   0,   4, INF, INF},
                /*E*/{INF, INF,   5,   4,   0,   2,   8},
                /*F*/{ 16,   7,   6, INF,   2,   0,   9},
                /*G*/{ 14, INF, INF, INF,   8,   9,   0}
        };
        Graph graph = new Graph(vertexs, matrix);
        graph.print();//图信息
        //计算
        EData[] kruskal = kruskal(graph);
        for (EData eData : kruskal) {
            if (eData != null) {
                System.out.println(eData.toString());
            }
        }
    }

    /**
     * 克鲁斯卡尔算法解决公交站问题
     * 一个城市新增7个站点(A,B,C,D,E,F,G)，现在需要修路把7个站点连通
     * 如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
     */
    public static EData[] kruskal(Graph graph) {
        //获取边
        EData[] edges = graph.getEdges();
        //根据权值从小到大排序
        graph.sortEdges(edges);

        //用于保存"已有最小生成树"中的每个顶点在最小生成树中的终点
        int[] ends = new int[graph.edgeNum];
        //创建结果数组，保存最后的最小生成树
        EData[] rets = new EData[graph.edgeNum];

        //表示最后结果数组的索引
        int index = 0;
        for(int i = 0; i < graph.edgeNum; i++) {
            //获职到第i条边的第一个顶点(起点)
            int p1 = graph.getPosition(edges[i].start);
            //获取到第i条边的第2个顶点
            int p2 = graph.getPosition(edges[i].end);
            //获职p1这个顶点在已有最小生成树中的终点
            int m = graph.getEnd(ends,p1);
            //获取p2这个顶点在已有最小生成树中的终点
            int n = graph.getEnd(ends, p2);
            //是否构成回路
            if(m != n) {//没有构成回路
                ends[m] = n;// 设置m 在"已有最小生成树"中的终点
                rets[index++] = edges[i];
            }
        }
        return rets;
    }
}

//图
class Graph {
    int edgeNum; //边的个数
    char[] vertexs;//顶点数组
    int[][] matrix;//邻接矩阵
    // 使用 INF 表示两个顶点不连通
    private static final int INF= Integer.MAX_VALUE;

    public Graph(char[] vertexs, int[][] matrix) {
        //初始化顶点数和边的个数
        int vlen = vertexs.length;
        //初始化顶点，不直接复制
        this.vertexs = new char[vlen];
        for(int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }
        //初始化边
        this.matrix = new int[vlen][vlen];
        for(int i = 0; i < vlen; i++) {
            for(int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
        //统计边
        for(int i = 0; i < vlen; i++) {
            for(int j = i + 1; j < vlen; j++) {
                if(this.matrix[i][j] != INF){
                    edgeNum++;
                }
            }
        }
    }

    //打印图
    public void print() {
        System.out.println("图为:");
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    //获取顶点对应的下标
    public int getPosition(char ch) {
        for(int i= 0; i < vertexs.length; i++) {
            if(vertexs[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    //获取图中的边放到EData[]数组中
    public EData[] getEdges() {
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = i + 1; j < vertexs.length; j++) {
                if(matrix[i][j]!= INF) {
                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    //对边进行排序
    public void sortEdges(EData[] edges) {
        for(int i = 0; i < edges.length - 1; i++) {
            for(int j = 0; j < edges.length- 1 -i; j++) {
                if(edges[j].weight > edges[j+1].weight) {
                    EData tmp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = tmp;
                }
            }
        }
    }

    //获取下标为i的顶点的终点
    public int getEnd(int[] ends, int i) {
        while(ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }
}

//边
class EData {
    char start;//边的一个顶点
    char end;//边的另外一个顶点
    int weight;//边的杈值

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}

迪杰斯特拉算法

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

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
/**
 * 迪杰斯特拉算法
 */
public class Dijkstra {
    private static final int N = Integer.MAX_VALUE;

    public static void main(String[] args) {
        //初始化图
        char[] vertexs ={'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                //N 表示顶点不连通
                     /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/{ N,   5,   7,   N,   N,   N,   2},
                /*B*/{ 5,   N,   N,   9,   N,   N,   3},
                /*C*/{ 7,   N,   N,   N,   8,   N,   N},
                /*D*/{ N,   9,   N,   N,   N,   4,   N},
                /*E*/{ N,   N,   8,   N,   N,   5,   4},
                /*F*/{ N,   N,   N,   4,   5,   N,   6},
                /*G*/{ 2,   3,   N,   N,   4,   6,   N},
        };
        DGraph graph = new DGraph(vertexs, matrix);
        graph.print();//图信息
        dijkstra(graph, 2);
    }

    /**
     * 迪杰斯特拉算法解决最短路径问题
     * 有7个村庄(A,B,C,D,E,F,G)
     * 现在有六个邮差，从G点出发，需要分别把邮件分别送到A,B,C,D,E,F六个村庄
     * 计算出G村庄到其它各个村庄的最短距离?
     * @param graph 图对象
     * @param index 出发顶点对应的下标
     */
    public static void dijkstra(DGraph graph, int index) {
        VisitedVertex visitedVertex = new VisitedVertex(graph, index);
        visitedVertex.update(index);
        for(int j = 0; j < graph.vertexs.length; j++) {
            index = visitedVertex.updateArr();//选择并返回新的访问顶点
            visitedVertex.update(index);//更新index顶点到周围顶点的距离和前驱顶点
        }
        visitedVertex.show();
    }
}

// 已访问顶点集合
class VisitedVertex {
    //图对象
    DGraph graph;
    //记录各个顶点是否访问过1表示访问过,0未访问，会动态更新
    public int[] already_arr;
    //每个下标对应的值为前一个顶点下标，会动态更新
    public int[] pre_visited;
    //记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
    public int[] dis;

    /**
     * @param graph 图对象
     * @param index 出发顶点对应的下标，比如G顶点，下标就是6
     */
    public VisitedVertex(DGraph graph, int index) {
        this.graph = graph;
        this.already_arr = new int[graph.vertexs.length];
        this.pre_visited = new int[graph.vertexs.length];
        this.dis = new int[graph.vertexs.length];
        //初始化 dis数组
        Arrays.fill(dis, Integer.MAX_VALUE);
        this.already_arr[index] = 1;
        this.dis[index] = 0;
    }

    //判断index顶点是否被访问过
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    //更新出发顶点到index顶点的距离
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    //更新顶点的前驱为index结点
    public void updatePre(int index, int pre) {
        pre_visited[pre] = index;
    }

    //返回出发顶点到index顶点的距离
    public int getDis(int index) {
        return dis[index];
    }

    //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
    public void update(int index) {
        int len = 0;
        for(int j = 0; j < graph.matrix[index].length; j++) {
            if (graph.matrix[index][j] == Integer.MAX_VALUE) {
                continue;
            }
            //出发顶点到index顶点的距离+从index顶点到j顶点的距离的和
            len = getDis(index) + graph.matrix[index][j];
            //如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新
            if(!in(j) && len < getDis(j)) {
                updatePre(j, index);//更新j顶点的前驱为index顶点
                updateDis(j, len);//更新出发顶点到j顶点的距离
            }
        }
    }

    //继续选择并返回新的访问顶点，比如这里的G完后，就是A点作为新的访问顶点(注意不是出发项点)
    public int updateArr() {
        int min = Integer.MAX_VALUE, index = 0;
        for(int i = 0; i < already_arr.length; i++) {
            if(already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }
        //更新 index 顶点被访问过
        already_arr[index] = 1;
        return index;
    }

    //显示结果
    public void show() {
        int count = 0;
        for(int i : dis) {
            if (i != Integer.MAX_VALUE) {
                System.out.print(graph.vertexs[count]+"("+i+")");
            } else {
                System.out.println("N");
            }
            count++;
        }
    }
}

//图
class DGraph {
    char[] vertexs;//顶点数组
    int[][] matrix;//邻接矩阵

    public DGraph(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
    }

    //显示图
    public void print() {
        System.out.println("图为:");
        for(int i = 0; i < vertexs.length; i++) {
            for(int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d", matrix[i][j]);
            }
            System.out.println();
        }
    }
}

学习资源