数据结构与算法

心得：

  1. 灵活运用取余计算！
  2. 算法中优先排除特殊情况（死去的高考数学开始攻击我）

数据结构

数据结构 包括 线性结构 与 非线性结构

线性结构分为顺序存储结构（顺序表）与链式存储结构（链表），区别在于内存分布连续与否

线性结构：数组、队列、链表、栈

非线性结构：二维数组、多维数组、广义表、树结构、图结构

稀疏数组 SparseArray

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

处理思路：

1.记录数组一共有几行几列，有多少个不同的值

2.把具有不同值的元素的行、列及值记录在一个小规模的数组中

二维数组转稀疏数组的方法：

1.遍历原始的二维数组，得到有效数据的个数sum

2.根据sum创建稀疏数组int[sum + 1][3] sparseArray

3.将原数组中的有效数据转存入稀疏数组

稀疏数组转二维数组的方法：

1.读取稀疏数组的第一行，以此创建新的二维数组

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
public class SparseArray {
    public static void main(String[] args){
        int[][] intArray_1;
        intArray_1 = new int[][]
                {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
        printArray(intArray_1);
        int[][] sparseArray;
        sparseArray = intToSparse(intArray_1);
        printArray(sparseArray);
        int[][] intArray_2;
        intArray_2 = sparseToInt(sparseArray);
        printArray(intArray_2);
    }
    public static int[][] intToSparse(int[][] intArray){
        int sum = 0;
        for (int i = 0; i < intArray.length; i++){
            for (int j = 0; j < intArray[i].length; j++){
                if (intArray[i][j] != 0){
                    sum++;
                }
            }
        }
        int[][] sparseArray = new int[sum + 1][3];
        sparseArray[0][0] = intArray.length;
        sparseArray[0][1] = intArray[0].length;
        sparseArray[0][2] = sum;
        int count = 1;
        for (int i = 0; i < intArray.length; i++){
            for (int j = 0; j < intArray[i].length; j++){
                if (intArray[i][j] != 0){
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = intArray[i][j];
                    count++;
                }
            }
        }
        return sparseArray;
    }
    public static int[][] sparseToInt(int[][] sparseArray){
        int[][] intArray;
        intArray = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 0; i < intArray.length; i++){
            Arrays.fill(intArray[i], 0);
        }
        for (int i = 1; i < sparseArray.length; i++){
            intArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return intArray;
    }
    public static void printArray(int[][] array){
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[i].length; j++){
                System.out.print(array[i][j] + "  ");
            }
            System.out.println();
        }
    }
}

队列 Queue

  • 队列是一个有序列表，可以用数组或是列表来实现
  • 遵循先进先出的原则（FIFO）

数组实现队列：

因为队列的输出与出入分别从前后端进行处理，所以需要两个变量front及rear分别记录队列前后端的下标，front随数据输出而改变，而rear随数据输入而改变

示例：
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
class QueueArray {
    //队列的最大元素个数
    private int maxSize;
    //用于保存队列数据的数组
    private int[] queueArray;
    //队列前后端的下标
    private int front;
    private int rear;
    //初始化
    public QueueArray(int maxSize){
        this.maxSize = maxSize;
        this.queueArray = new int[maxSize];
        this.front = -1;  //指向队列头的前一个数据
        this.rear = -1;  //指向队列尾的数据
    }
    //添加数据
    public void addQueue(int num){
        if (!isFull()){
            queueArray[rear + 1] = num;
            rear++;
            System.out.println("已将数据" + num + "添加到队列中，位置为" + rear);
        }
        else {
            System.out.println("队列已满，不能再添加数据");
        }
    }
    //获取数据
    public int getQueue(){
        if (!isEmpty()){
            front++;
            return queueArray[front];
        }
        else {
            throw new RuntimeException("队列为空，不能取出数据");
        }
    }
    //显示队列的所有数据
    public void showQueue(){
        if (!isEmpty()){
            for (int i = 0; i < queueArray.length; i++){
                System.out.print(queueArray[i] + "  ");
            }
        }
        else {
            System.out.println("队列空，无法读取数据");
        }
    }
    //显示队列的头部数据
    public int showHeadQueue(){
        if (!isEmpty()){
            return queueArray[front + 1];
        }
        else {
            throw new RuntimeException("队列为空，无法获取数据");
        }
    }
    //判断队列是否已满
    public boolean isFull(){
        return rear == maxSize - 1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return front == rear;
    }
}

存在的问题：因为数组只能使用一次，所以队列满后即便取出前端数据也不能再添加数据，使用过的空间无法重复使用，造成空间的浪费

改进方法：利用数组实现环形队列

数组实现环形队列：

将front, rear修改为分别指向数组前端数据与后端数据的下一位，利用front == rear判断队列是否为空， 利用*(rear + 1) % maxSize == front* 判断队列是否已满，此时队列中有效数据个数为*(rear - front + maxSize) % maxSize*

环形队列实际上牺牲了一个空间，队列大小为maxSize - 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
class CircleQueueArray{
    //队列的最大元素个数
    private int maxSize;
    //用于保存队列数据的数组
    private int[] queueArray;
    //队列前后端的下标
    private int front;
    private int rear;
    public CircleQueueArray(int maxSize){
        this.maxSize = maxSize;
        this.queueArray = new int[maxSize];
        this.front = 0;  //指向队列头的数据
        this.rear = 0;  //指向队列尾的后一个数据
    }
    //添加数据
    public void addQueue(int num){
        if (!isFull()){
            queueArray[rear] = num;
            //特殊情况：若后标到达最大处则回到0（环形）
            rear = (rear + 1) % maxSize;
            System.out.println("已将数据" + num + "添加到队列中，位置为" + (rear - 1));
        }
        else {
            System.out.println("队列已满，不能再添加数据");
        }
    }
    //获取数据
    public int getQueue(){
        if (!isEmpty()){
            int value = queueArray[front];
            front = (front + 1) % maxSize;
            return value;
        }
        else {
            throw new RuntimeException("队列为空，不能取出数据");
        }
    }
    //显示队列的所有数据
    public void showQueue(){
        if (!isEmpty()){
            for (int i = front; i < getSize() + front; i++){
                System.out.print(queueArray[i % maxSize] + "  ");
            }
        }
        else {
            System.out.println("队列空，无法读取数据");
        }
    }
    //显示队列的头部数据
    public int showHeadQueue(){
        if (!isEmpty()){
            return queueArray[front];
        }
        else {
            throw new RuntimeException("队列为空，无法获取数据");
        }
    }
    //判断队列是否已满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return front == rear;
    }
    //求出队列当前有效数据的量
    public int getSize(){
        return (rear - front + maxSize) % maxSize;  //加maxSize排除负数
    }
}

链表 LinkedList

  • 链表是有序的列表，由多个节点(*node)*构成
  • 每个节点中含data域与next域，next域指向下一个节点
  • 链表的每个节点在内存中是不连续存放的
  • 链表可带头节点或不带头节点(head)，其不存放具体数据，用于指向单链表头
  • 双向链表同时还含有pre域，指向上一个节点

示例：

用带head头的单向链表实现水浒英雄排行榜管理

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
//定义mySingleLinkedList用于管理英雄
class mySingleLinkedList{
    HeroNode head = new HeroNode(0, null, null);

    public void addHero(HeroNode newHero){
        //因为head节点不能改变，因此创建一个变量用于遍历
        HeroNode temp = head;
        while (true){
            if (temp.next == null){
                break;
            }
            else {
                temp = temp.next;
            }
        }
        temp.next = newHero;
    }

    public void addHeroByOrder(HeroNode newHero){
        HeroNode temp = head;
        boolean flag = false;  //用于表示该编号是否已经存在
        while (true){
            if (temp.next == null){
                break;
            }
            else {
                if (temp.next.number > newHero.number){
                    break;
                }
                else if (temp.next.number == newHero.number){
                    flag = true;
                    break;
                }
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("要加入的英雄编号已存在");
        }
        else {
            newHero.next = temp.next;
            temp.next = newHero;
        }
    }

    public void showAllHero(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            else {
                System.out.println(temp);
                temp = temp.next;
            }
        }
    }
}

class HeroNode{
    //英雄排名
    int number;
    //英雄姓名
    String name;
    //英雄称号
    String nickname;
    //next节点
    HeroNode next;

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

    @Override
    public String toString() {
        return "英雄编号：" + number + "  英雄姓名：" + name + "  英雄称号：" + nickname;
    }
}

栈 Stack

  • 栈为有序列表
  • 栈遵循先入后出(FILO)的原则
  • 栈是元素的添加与删除都只能在线性表中的同一端进行的一种特殊线性表，允许插入的一端和删除的一端为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)
  • 出栈称为pop，入栈称为push

示例：

用栈完成计算机（从字符串中提取数字与符号进行计算）

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
public class CalculatorWithStack {
    public static void main(String[] args){
        StackCalculator stackCalculator = new StackCalculator(10, 10);
        System.out.println("计算结果为：" + stackCalculator.calculate("3*2+3"));
    }
}

class StackCalculator{
    NumberStack numberStack;
    OperatorStack operatorStack;

    public StackCalculator(int numberSize, int operatorSize){
        this.numberStack = new NumberStack(numberSize);
        this.operatorStack = new OperatorStack(operatorSize);
    }

    public int calculate(String formula){
        for (int i = 0; i < formula.length(); i++){
            if (isOperator(formula.charAt(i))){
                if (operatorStack.isEmpty()){
                    operatorStack.push(formula.charAt(i));
                }
                else {
                    if (compareOperator(operatorStack.getOperator(), formula.charAt(i))){
                        operatorStack.push(formula.charAt(i));
                    }
                    else {
                        char operator = operatorStack.pop();
                        int int02 = numberStack.pop();
                        int int01 = numberStack.pop();
                        numberStack.push(calculate(int01, int02, operator));
                        operatorStack.push(formula.charAt(i));
                    }
                }
            }
            else if (isNumber(formula.charAt(i))){
                numberStack.push(charToInt(formula.charAt(i)));
            }
            else {
                throw new RuntimeException("输入的算式不合法");
            }
        }
        int counter = operatorStack.getSize();
        for (int i = 0; i < counter; i++){
            char operator = operatorStack.pop();
            int int02 = numberStack.pop();
            int int01 = numberStack.pop();
            numberStack.push(calculate(int01, int02, operator));
        }
        return numberStack.pop();
    }

    private int calculate(int int01, int int02, char operator){
        if (operator == '+'){
            return int01 + int02;
        }
        else if (operator == '-'){
            return int01 - int02;
        }
        else if (operator == '*'){
            return int01 * int02;
        }
        else if (operator == '/'){
            return int01 / int02;
        }
        else {
            throw new RuntimeException("未知错误！！www");
        }
    }

    //返回第二个运算符的优先级是否高于第一个运算符
    private boolean compareOperator(char a, char b){
        return (b == '*' || b == '/') && (a == '+' || a == '-');
    }

    private boolean isOperator(char a){
        return a == '+' || a == '-' || a == '*' || a == '/';
    }

    private boolean isNumber(char a){
        return a == '0' || a == '1' || a == '2' || a == '3' || a == '4' || a == '5' || a == '6' || a == '7' || a == '8' || a == '9';
    }

    private int charToInt(char a){
        if (a == '0') {
            return 0;
        }
        else if (a == '1') {
            return 1;
        }
        else if (a == '2') {
            return 2;
        }
        else if (a == '3') {
            return 3;
        }
        else if (a == '4') {
            return 4;
        }
        else if (a == '5') {
            return 5;
        }
        else if (a == '6') {
            return 6;
        }
        else if (a == '7') {
            return 7;
        }
        else if (a == '8') {
            return 8;
        }
        else if (a == '9') {
            return 9;
        }
        else {
            throw new RuntimeException("未知错误！！www");
        }
    }
}


class NumberStack{
    int head;
    int[] array;
    int maxSize;

    public NumberStack(int maxSize){
        this.head = 0;
        this.maxSize = maxSize;
        this.array = new int[maxSize];
    }

    public void push(int a){
        if (isFull()){
            return;
        }
        else {
            array[head] = a;
            head++;
        }
    }

    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空，不能取出数据");
        }
        else {
            head--;
            return array[head];
        }
    }


    public boolean isFull(){
        return head == maxSize;
    }

    public boolean isEmpty(){
        return head == 0;
    }
}

class OperatorStack{
    int head;
    char[] array;
    int maxSize;

    public OperatorStack(int maxSize){
        this.head = 0;
        this.maxSize = maxSize;
        this.array = new char[maxSize];
    }

    public void push(char a){
        if (isFull()){
            return;
        }
        else {
            array[head] = a;
            head++;
        }
    }

    public char pop(){
        if (isEmpty()){
            throw new RuntimeException("栈为空，不能取出数据");
        }
        else {
            head--;
            return array[head];
        }
    }

    public char getOperator(){
        if (isEmpty()){
            throw new RuntimeException("栈为空，不能读取数据");
        }
        else {
            return array[head - 1];
        }
    }

    public int getSize(){
        return head;
    }

    public boolean isFull(){
        return head == maxSize;
    }

    public boolean isEmpty(){
        return head == 0;
    }
}

算法

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

时间复杂度： 将算法对应的时间频度改为保留系数为1的最高阶次项，记为O(n)。

空间复杂度： 一个算法所耗费的存储空间称为空间复杂度，同样记为O(n)。

递归 Recursion

递归是一种编程技术，其中函数在其定义中直接或间接调用自身。

递归的基本条件包括：子问题与原始问题相同且更简单，以及存在一个终止条件，以防止无限递归。

注：不要在一开始就陷入细节，优先思考母问题与子问题之间的相似性

由于子问题的规模比母问题小，不断递下去，总会有个尽头，即递归的终止条件（base case），直接返回它的答案（归）

回溯算法 Back Tracking

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

可以把回溯法看成是递归调用的一种特殊形式。其核心就是 for 循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择。

排序算法 Sort Algorithm

排序是将一组数据按指定的顺序进行排列的过程

排序的分类：

  1. 内部排序 使用内存
  2. 外部排序 使用内存与外存（数据量偏大）

常见内部排序：

  • 插入排序 直接插入排序、希尔排序
  • 选择排序 简单选择排序、堆排序
  • 交换排序 冒泡排序、快速排序
  • 归并排序
  • 基数排序

冒泡排序 Bubble Sort

冒泡排序通过对 待排序序列从前向后依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，像水底的气泡般逐渐上浮。

冒泡排序优化：若在一次循环中没有出现交换，则说明已排序完成，此时可提前退出程序

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static int[] bubbleSorting(int[] array){
    boolean flag = false;
    int count = 0;
    for (int i = 0; i < array.length - 1; i++){
        for (int j = 0; j < array.length - 1; j++){
            if (array[j] > array[j + 1]){
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag){
            break;
        }
        flag = false;
        count++;
    }
    System.out.println("总排序循环次数为：" + count);
    return array;
}

选择排序 Select Sort

选择排序通过从欲排序的数据中按指定的规则选择出元素，再按规定交换位置后达到排序的目的。

以从小到大排列为例，第一次从第1个至第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
private static int[] selectSorting(int[] array){
    for (int i = 0; i < array.length - 1; i++){
        int minimumNumber = 0;
        int minimumIndex = 0;
        for (int j = i; j < array.length; j++){
            if (j == i){
                minimumNumber = array[j];
                minimumIndex = j;
            }
            else {
                if (minimumNumber > array[j]){
                    minimumNumber = array[j];
                    minimumIndex = j;
                }
            }
        }
        int temp = array[i];
        array[i] = array[minimumIndex];
        array[minimumIndex] = temp;
    }
    return array;
}

插入排序 Insertion Sort

插入排序通过对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中含n-1个元素，排序过程中每次从无序表中取出第一个元素，依次与有序表元素比较并插入到适当位置，使之成为新的有序表。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int[] insertionSorting(int[] array){
        for (int i = 1; i < array.length; i++){
            for (int j = i - 1; j >= 0; j--){
                if (array[i] < array[j]){
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i = j;
                }
            }
        }
        return array;
    }

希尔排序 Shell Sort

希尔排序是插入排序的一种，它是针对直接插入排序算法的改进。又称缩小增量排序，因 Donald Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

即为分层嵌套的插入排序。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int[] shellSorting(int[] array){
    for (int gap = array.length / 2; gap > 0; gap /= 2){
        //内部算法即为插入排序
        for (int i = gap; i < array.length; i++){
            for (int j = i; j >= 0; j -= gap){
                if (array[i] < array[j]){
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i = j;
                }
            }
        }
    }
    return array;
}

快速排序 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
private static void quickSorting(int[] array, int left, int right){

        if (left >= right){
            return ;
        }
        int key = partSort(array, left, right);
        quickSorting(array, left, key - 1);
        quickSorting(array, key + 1, right);
    }

    private static int partSort(int[] array, int left, int right){
        int pivot = left;
        int key = array[left];
        while (left < right){
            while (left < right && array[right] >= key){
                right--;
            }
            array[pivot] = array[right];
            pivot = right;
            while (left < right && array[left] <= key){
                left++;
            }
            array[pivot] = array[left];
            pivot = left;
        }
        array[pivot] = key;
        return pivot;
    }

归并排序 Merge Sort

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and 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
private static void mergeSorting(int[] arr, int l, int r) {
        if (l >= r){
            return;
        }
        int mid = l + ((r - l) / 2);
        mergeSorting(arr,l,mid);
        mergeSorting(arr,mid + 1,r);
        if (arr[mid] > arr[mid + 1]) {
            partMergeSort(arr,l,mid,r);
        }
    }

    private static void partMergeSort(int[] arr, int left, int mid, int right) {
        // 先创建一个新的数组aux,将子数组的值复制给新数组
        int[] aux = new int[right - left + 1];

        for (int i = 0; i < aux.length; i++) {

            aux[i] = arr[i + left];
        }
        int i = left; //数组1的开始下标
        int j = mid + 1; //数组2的开始下标

        for (int k = left; k <= right; k++) {
            if (i > mid) {
                arr[k] = aux[j - left];
                j ++;
            }else if (j > right) {
                arr[k] = aux[i - left];
                i ++;
            }else if (aux[i - left] <= aux[j - left]) {
                arr[k] = aux[i - left];
                i ++;
            }else {
                arr[k] = aux[j - left];
                j ++;
            }
        }
    }

查找算法 Search Algorithm

略

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的工作原理是通过不断地将搜索范围缩小一半来找到目标元素

实际问题

约瑟夫问题(Josephus problem)

约瑟夫环问题起源于一个犹太故事：
罗马人攻占了桥塔帕特，41个人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家Josephus（约瑟夫）和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家制定了一个自杀方案，所有这41个人围成一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀……，直到所有的人都自杀身亡为止。约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀。

简化问题：

设有N个人围坐一圈，编号为1到N，现从编号为1的人开始报数，数到M的人出列，接着从出列的下一个编号（人）开始重新报数，数到M的人出列，如此下去，直到只剩下最后一个人，并输出其编号。

递推公式法：

$$
f(N,M)=(f(N−1,M)+M)%N
$$

详细推导过程：[约瑟夫环——公式法（递推公式）-CSDN博客]

示例代码：

1
2
3
4
5
6
7
public static int remove(int n, int m){
        int p = 0;
        for (int i = 2; i <= n; i++){
            p = (p + m) % i;
        }
        return p;
    }

递归法：

也基于上述公式

示例代码：

1
2
3
4
5
6
7
8
public static int remove(int n, int m){  
    if (n == 1){
        return (n + m) % n;
    }
    else {
        return (remove(n - 1, m) + m) % 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
class CircleLinkedList{
    private Person first = null;

    public void addPerson(int personNumber){
        if (personNumber < 1){
            System.out.println("error");
            return;
        }
        Person currentPerson = null;
        for (int i = 0; i < personNumber; i++){
            Person newPerson = new Person(i + 1);
            if (i == 0){
                first = newPerson;
                first.setNext(first);
                currentPerson = first;
            }
            else {
                newPerson.setNext(first);
                currentPerson.setNext(newPerson);
                //newPerson.setNext(first);
                currentPerson = newPerson;
            }
        }
    }

    public void showPerson(){
        Person temp = first;
        while (true){
            System.out.println(temp.getNumber());
            if (temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
    }

    public void deletePerson(int gap, int sum){
        Person helper = first;
        while (true){
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        while (true){
            if (first == helper){
                break;
            }
            for (int j = 0; j < gap - 1; j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println(first.getNumber());
    }

}

class Person {
    private int number;
    private Person next;

    public Person(int number){
        this.number = number;
    }

    public Person getNext() {
        return next;
    }

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

    public int getNumber() {
        return number;
    }
}

八皇后问题(Eight queens)

八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在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
public class EightQueens {

    private static int count = 0;

    public static void main(String[] args){
        char[][] charArray = createArray(8, 8);
        System.out.println(isValid(charArray, 0, 0));
        findSolution(charArray, 0);
    }

    private static void findSolution(char[][] array, int x){
        if (x == array.length){
            printArray(array);
            count++;
            System.out.println();
            System.out.println(count);
            System.out.println();
            return;
        }
        for (int y = 0; y < array.length; y++){
            if (isValid(array, x, y)){
                //char[][] temp = array.clone();
                array[x][y] = 'Q';
                //printArray(temp);
                findSolution(array, x + 1);
                array[x][y] = '.';
            }
        }
    }

    private static char[][] createArray(int x, int y){
        char[][] charArray = new char[x][y];
        for (int i = 0; i < x; i++){
            for (int j = 0; j < y; j++){
                charArray[i][j] = '.';
            }
        }
        return charArray;
    }

    private static void printArray(char[][] array){
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[i].length; j++){
                System.out.print(array[i][j] + "  ");
            }
            System.out.println();
        }
    }

    private static boolean isValid(char[][] array, int x, int y){
        boolean a = true;
        if (array[x][y] == 'Q'){
            a = false;
        }
        for (int i = 0; i < array[x].length; i++){
            if (i != y && (array[x][i] == 'Q') ){
                a = false;
            }
        }
        for (int i = 0; i < array.length; i++){
            if (i != x && (array[i][y] == 'Q') ){
                a = false;
            }
        }
        for (int i = 1; i < array.length; i++){
            if ((x + i == 8) || (y + i == 8)){
                break;
            }
            if (array[x + i][y + i] == 'Q'){
                a = false;
            }
        }
        for (int i = 1; i < array.length; i++){
            if ((x - i == -1) || (y + i == 8)){
                break;
            }
            if (array[x - i][y + i] == 'Q'){
                a = false;
            }
        }
        for (int i = 1; i < array.length; i++){
            if ((x + i == 8) || (y - i == -1)){
                break;
            }
            if (array[x + i][y - i] == 'Q'){
                a = false;
            }
        }
        for (int i = 1; i < array.length; i++){
            if ((x - i == -1) || (y - i == -1)){
                break;
            }
            if (array[x - i][y - i] == 'Q'){
                a = false;
            }
        }
        return a;
    }
}