# Sparse array SparseArray

## demand

Recording the position of the chessboard can be saved with a binary array, but it will be found that recording a lot of meaningless data and a lot of space waste can be optimized with a sparse array

## introduce

Sparse array is to compress redundant data

The first row records the number of rows and columns of the original table and the number of non-zero values

## code implementation

```package com.luyi.DataStructures.sparse;

import java.util.Date;

/**
* @author Lu Yi
* @create 2020-12-01 9:26
*/
public class SparseArray {
public static void main(String[] args) {
// Create an original two-dimensional array 11 * 11
// 0 means there are no pieces, 1 means sunspots, and 2 means whites
int chessArray[][] = new int[11][11];
chessArray[1][2] = 1;
chessArray[2][3] = 2;
// Output the original two-dimensional array
System.out.println("Output the original two-dimensional array");
for(int row[] : chessArray){
for (int data : row){
System.out.print(data + "\t");
}
System.out.println();
}

// The idea of transforming two-dimensional array into sparse array
// 1 first traverse the two-dimensional array to get the number of non-0 data
int sum = 0;
for(int i = 0; i < chessArray.length; i++){
for(int j = 0; j<chessArray.length; j++ ){
if(chessArray[i][j] != 0){
sum++;
}
}
}
System.out.println("Number of non-0 data sum="+ sum);
// 2 create the corresponding sparse array
int sparseArray[][] = new int[sum+1][3];
// Assign values to sparse arrays
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;

// Traverse a two-dimensional array and store non-zero values in a sparse array
int index = 1;
for(int i = 0; i < chessArray.length; i++){
for(int j = 0; j<chessArray.length; j++ ){
if(chessArray[i][j] != 0){
sparseArray[index][0] = i;
sparseArray[index][1] = j;
sparseArray[index][2] = chessArray[i][j];
index++;
}
}
}
// Output sparse array
System.out.println("The resulting sparse array is:");
for (int i = 0;i<sum+1;i++){
System.out.print(sparseArray[i][0] + "\t");
System.out.print(sparseArray[i][1] + "\t");
System.out.print(sparseArray[i][2] + "\t");
System.out.println();
}

// Restore sparse array to two-dimensional array
// 1 read the first row of the sparse array and create the original two-dimensional array according to the data of the first row
// 2 read the last few lines of the sparse array and assign values
int row = sparseArray[0][0];
int cos = sparseArray[0][1];
int newChessArray[][] = new int[row][cos];
for(int i = 0; i < row; i++){
for(int j = 0; j < cos; j++ ){
newChessArray[i][j] = 0;
}
}
for (int i = 1; i < sparseArray.length;i++){
newChessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}

System.out.println("Output recovered 2D array");
for(int rows[] : chessArray){
for (int data : rows){
System.out.print(data + "\t");
}
System.out.println();
}

}

}

```

## Code execution results

Output the original two-dimensional array
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
Number of non-0 data sum=2
The resulting sparse array is:
11 11 2
1 2 1
2 3 2
Output recovered 2D array
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

# queue

## introduce

The clear figure in the figure above shows that the tail front of the queue of the real to be table represents the head of the data. When the data is stored, the front remains unchanged and the position of the front changes. When the data is stored, the position of the rear remains unchanged and the position of the front changes

## Array simulation queue idea

rear == maxSize-1 is full. front points to the first position of the queue head. rear points to the specific position of the queue tail

## code implementation

```package com.luyi.DataStructures.queue;

import java.util.Scanner;

/**
* @author Lu Yi
* @create 2020-12-01 10:08
* Array simulation queue
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
// test
// Create a queue
ArrayQueue arrayQueue = new ArrayQueue(3);
char key = ' '; // Receive user input
Scanner scanner = new Scanner(System.in);
boolean loop = true; // Control cycle
while (loop){
System.out.println("s(show): Show pairs of columns");
System.out.println("e(exit): Exit program");
System.out.println("g(get): Fetching data from a pair of columns");
key = scanner.next().charAt(0); //Receive this character
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("Enter a number");
int value = scanner.nextInt();
break;
case 'g':
try {
System.out.println("Extracted data:"+arrayQueue.getQueue());
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default :
break;
}
}
System.out.println("Program exit");

}
}

// Write an ArrayQueue class using an array to simulate a queue
class ArrayQueue {
private int maxSize; // Represents the maximum capacity of the array
private int front; // Queue header
private int rear; // End of queue
private int[] arr; // Storage data simulation queue

// Constructor to create a queue
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr= new int[maxSize];
front = rear = -1; // The queue head and tail front point to the first position of the queue head, and the rear point to the specific position of the queue tail
}

// Determine whether the queue is full
public Boolean isFull(){
return rear == maxSize - 1;
}

// Judge whether the column is empty
public Boolean isEmpty(){
return rear == front;
}

// Add data to pair column
// Determine whether the queue is full
if(isFull()){
return;
}
// rear shift back
arr[++rear] = n;
}

// Data out of queue
public int getQueue(){
// Judge whether the opponent is empty
if(isEmpty()){
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
return arr[++front];
}

// Displays all data for the column
public void showQueue(){
// Judge whether the queue is empty
if(isEmpty()){
System.out.println("Queue is empty");
return;
}
for (int i = 0; i < arr.length; i++){
System.out.println("arr["+i+"]="+arr[i]);
}
}

// The data displayed on the header of the column is not fetched data
// Judge whether it is empty
if(isEmpty()){
throw new RuntimeException("Queue is empty,No header data");
}
return arr[front + 1];
}
}

```

Console results

s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
s
Queue is empty
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
a
Enter a number
10
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
s
arr[0]=10
arr[1]=0
arr[2]=0
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
a
Enter a number
20
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
a
Enter a number
30
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
s
arr[0]=10
arr[1]=20
arr[2]=30
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
a
Enter a number
40
The queue is full and data cannot be added
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
h
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
g
Extracted data: 10
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
h
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
g
Extracted data: 20
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
g
Extracted data: 30
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
g
The queue is empty and data cannot be retrieved
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column
h
The queue is empty and has no header data
s(show): displays the pair of columns
e(exit): exit the program
g(get): fetch data from the opposite column

## problem

Now the queue has been filled up and all of them are taken out. The current list is theoretically empty
However, the data cannot be added. This array cannot be reused. It can only be used once, which does not achieve the effect of reuse
This array needs to be transformed from an algorithm into a ring array (Modular)

## Array simulation ring queue

Note that the front and rear queues have now been adjusted

## Ring queue code implementation

```package com.luyi.DataStructures.queue;

import java.util.Scanner;

/**
* Circular array pair column
* @author Lu Yi
* @create 2020-12-01 13:54
*/
public class CircleArrayQueue {
public static void main(String[] args) {
// test
// Create a ring queue
CircleArray arrayQueue = new CircleArray(4); // The array space set to 4 is valid
char key = ' '; // Receive user input
Scanner scanner = new Scanner(System.in);
boolean loop = true; // Control cycle
while (loop){
System.out.println("s(show): Show pairs of columns");
System.out.println("e(exit): Exit program");
System.out.println("g(get): Fetching data from a pair of columns");
key = scanner.next().charAt(0); //Receive this character
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("Enter a number");
int value = scanner.nextInt();
break;
case 'g':
try {
System.out.println("Extracted data:"+arrayQueue.getQueue());
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
} catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default :
break;
}
}
System.out.println("Program exit");

}
}

// Write an ArrayQueue class using an array to simulate a queue
class CircleArray  {
private int maxSize; // Represents the maximum capacity of the array
// The meaning of the variable of front is adjusted to point to the first element of the queue, that is, arr[front] is the first header element
// The initial value of front becomes 0
private int front; // Queue header
// Adjust the meaning of the rear variable. Rear points to the next position of the last element of the queue, because you want to free up a space for convention. The initial value of rear is 0
private int rear; // End of queue
private int[] arr; // Storage data simulation queue

// Constructor to create a queue
public CircleArray(int maxSize){
this.maxSize = maxSize;
arr= new int[maxSize];
//front = rear = 0 ; //  The queue head and tail front point to the first position of the queue head, and the rear point to the specific position of the queue tail
}

// Determine whether the queue is full
public boolean isFull(){
return (rear + 1)% maxSize == front;
}

// Judge whether the column is empty
public boolean isEmpty(){
return rear == front;
}

// Add data to pair column
// Determine whether the queue is full
if(isFull()){
return;
}
// Real points to the last position of the alignment and directly adds data to the backward moving real pointer
arr[rear] = n;
// If the rear is already at the last position of the array, you need to take the module to the beginning of the array
rear = (rear + 1) % maxSize;
}

// Data out of queue
public int getQueue(){
// Judge whether the opponent is empty
if(isEmpty()){
throw new RuntimeException("The queue is empty and data cannot be retrieved");
}
// Here, we need to analyze that front is the first element pointing to the queue
// 1 first save the value corresponding to front to the temporary variable
// 2 move the front back
// 3 Return temporarily saved variables
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}

// Displays all data for the column
public void showQueue(){
// Judge whether the queue is empty
if(isEmpty()){
System.out.println("Queue is empty");
return;
}
// Idea: start traversing from front, and how many elements are traversed
//
for (int i = front; i < front + size(); i++){
System.out.println("arr["+ i % maxSize +"]="+arr[i % maxSize]);
}
}

// The data displayed on the header of the column is not fetched data
// Judge whether it is empty
if(isEmpty()){
throw new RuntimeException("Queue is empty,No header data");
}
return arr[front];
}

// Find the number of valid data in the current queue
public int size() {
return  (rear + maxSize - front) % maxSize;
}
}

```

Operation results

```s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
s
Queue is empty
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a
Enter a number
10
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a 20
Enter a number
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
s
arr[0]=10
arr[1]=20
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a
Enter a number
30
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
s
arr[0]=10
arr[1]=20
arr[2]=30
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a
Enter a number
40
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns

g
Extracted data:10
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
s
arr[1]=20
arr[2]=30
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a 10
Enter a number
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
s
arr[1]=20
arr[2]=30
arr[3]=10
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a 70
Enter a number
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
h
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
g
Extracted data:20
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
g
Extracted data:30
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
g
Extracted data:10
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
g
The queue is empty and data cannot be retrieved
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a 50
Enter a number
s(show): Show pairs of columns
e(exit): Exit program
g(get): Fetching data from a pair of columns
a
```

Summary above:

1. Linked list is stored in the form of nodes, which is chain storage
2. Each node contains data field and next field: point to the next node
3. As shown in the figure: it is found that each node of the linked list is not necessarily stored continuously
4. The linked list is divided into the linked list with the leading node and the linked list without the head node, which is determined according to the actual needs

The single linked list looks continuous, but it's not. It's just a logical structure

### modify

Idea: (1) first find the node and traverse, (2) temp name = newHeroNode. name ; temp. nickname= newHeroNode. nickname

### code implementation

```package com.luyi.DataStructures.linkedlist;

/**
* @author Lu Yi
* @create 2020-12-01 21:10
*/

public static void main(String[] args) {
// Create node first
HeroNode heroNode1 = new HeroNode(1, "Song Jiang", "Timely rain");
HeroNode heroNode2 = new HeroNode(2, "Lu Junyi", "Jade Unicorn");
HeroNode heroNode3 = new HeroNode(3, "Wu Yong", "Zhiduoxing");
HeroNode heroNode4 = new HeroNode(4, "Lin Chong", "Leopard head");

// join
/**
* result:
* HeroNode{no=1, name='Name = 'song Jiangyu'}
* HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
* HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
* HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
*/
// Add in order of number
/**
* result
* The number [3] of the hero to be inserted already exists and cannot be added!
* HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
* HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
* HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
* HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
*/
// display

// Test modification node
HeroNode newHeroNode = new HeroNode(2, "Xiao Lu", "Little Unicorn");
HeroNode newHeroNode1 = new HeroNode(5, "Xiao Lu", "Little Unicorn");
/**
* result
* HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
* HeroNode{no=2, name='Lu Junyi ', nickName =' jade Qilin '}
* HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
* HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
* No node with number [5] found
*
* HeroNode{no=1, name='Song Jiang ', nickName =' timely rain '}
* HeroNode{no=2, name='Xiao Lu ', nickName =' Xiao Qilin '}
* HeroNode{no=3, name='Wu Yong ', nickName =' Zhiduoxing '}
* HeroNode{no=4, name='Lin Chong ', nickName =' leopard head '}
*/
// Modified display
System.out.println("After modification of the linked list");
System.out.println();

System.out.println("Delete a node");
/**
* result
* Delete a node
* The linked list is empty
*/

}
}
// Define a one-way linked list to manage our heroes
// Initialize the header node and nod the node. Don't move and don't store specific data

// Train of thought when the numbering sequence is not considered
// 1. Find the last node of the current linked list
// 2. Point the next of the last node to the new node
// Because the head node cannot be moved, we need an auxiliary node temp
// Traverse the linked list to find the last
while (true){
// Find the end of the linked list
if(temp.next == null){
break;
}
temp = temp.next;
}
// When exiting the white loop, temp points to the end of the linked list
temp.next = heroNode;
}

// The second way to add a hero is to insert the hero into the specified position according to the ranking
// If there is this ranking, the addition fails and a prompt is given
// Because the head node cannot be moved, we still use an auxiliary pointer (variable) to help find the added position
// Because it is a single list, temp is to find the previous node to add nodes, otherwise it cannot be inserted
boolean flag = false; // Whether the number added by the flag exists. The default is false
while(true) {
if(temp.next == null) { // It indicates that it has reached the end of the linked list
break;
}
if (temp.next.no > heroNode.no) { // Location found in temp and temp Insert this node between next
break;
}else if (temp.next.no == heroNode.no) { // Note the number of the heroNode you want to add already exists and cannot be added
flag = true; // Description number exists
break;
}
temp = temp.next;
}
// Judge the value of flag
if (flag){ // Cannot add description. Number exists
System.out.println("The number of the hero to insert["+heroNode.no+"]Already exists,Can't join!");
}else {
// Insert temp in linked list
heroNode.next = temp.next;
temp.next = heroNode;
}
}

public void list(){
// Judge whether the linked list is empty
return;
}
// Because the head node cannot be moved, we need a replication node temp
while(true){
// Output the information of this node
System.out.println(temp);
if(temp.next == null){
break;
}
// Move temp backward, otherwise it will be an endless loop
temp = temp.next;
}

}
// The information of the modified node is modified according to the number. The number cannot be modified
public void update (HeroNode newHeroNode){
return;
}
// Finding the node that needs to be modified is a no query
boolean flag = false; // Indicates whether the node is found
while (true) {
if (temp == null) {
break; // Indicates that the traversal of the linked list has ended (not that the last node has gone out)
}
if (temp.no == newHeroNode.no){
// Find the node to modify
flag = true;
break;
}
temp = temp.next;
}
// Judge whether to find the node to be modified according to the flag
if(!flag){
}else {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}

}

// Delete node
//Train of thought 1 The head node cannot be moved, so we need a temp auxiliary node to find the previous node to delete the node
//    2. We need to compare with the label of the last node of temp node
public void delete(int no){
boolean flag = false; // Flag whether the node to be deleted is found
while (true) {
if (temp.next == null){ // temp has reached the end of the linked list
break;
}
if (temp.next.no == no){
// The previous node of the node to be deleted was found
flag = true;
break;
}
temp = temp.next;
}
if (flag){
// Can delete
HeroNode t = temp.next;
temp.next = t.next;
t.next = null;
}else {
}

}

}

// Define a HeroNode, and each HeroNode object is a node
class HeroNode {
public int no;
public String name;
public String nickName;
public HeroNode next; // Point to next node

// constructor
public HeroNode(int hNo, String hName, String hNickName){
this.no = hNo;
this.name = hName;
this.nickName = hNickName;
}

// For display convenience, override the toString method

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

```

## Single chain surface test

### Find the number of effective nodes of the single linked list

```	/**
*
* @return Returns the number of valid nodes
*/
return 0;
}
int length = 0;
// Define an auxiliary variable
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}
```

#### Find the penultimate K node of the single linked list

```	// Find the penultimate K node of the single linked list
// Idea 1 write a method to receive the head node and receive the index (the penultimate index node)
//     2 first calculate the length of the linked list to find the node of length index
public HeroNode findNodeStartLast(HeroNode head ,int index){
// If the linked list is empty, null is returned
return null;
}
// Change the calendar to get the length of the linked list
// Traversal again returns the length - index
// First do an index check
if(index <= 0 || index > length){
return null;
}
// Define a secondary node
for(int i = 0 ;i < length-index ;i++ ){
temp = temp.next;
}
return  temp;
}
```

### Reversal of single linked list (a little difficult)

```	// Inversion of single linked list
}
HeroNode reverseHeroNode = new HeroNode(0, null, null);
if (reverseHeroNode.next == null){
reverseHeroNode.next.next = null;
}else {
HeroNode temp = reverseHeroNode.next;
reverseHeroNode.next.next = temp;
}
}
}
```

### Print the list of orders from the beginning to the end

```	// Using stack to print single linked list in reverse order
System.out.println("Queue is empty,Single linked list cannot be printed in reverse order");
return;
}
Stack<HeroNode> heroNodeStack = new Stack<>();
while (temp.next != null){
temp = temp.next;
}
while (heroNodeStack.size() > 0){
System.out.println(heroNodeStack.pop());
}
}

```

## code implementation

```package com.luyi.DataStructures.linkedlist;

/**
* @author Lu Yi
* @create 2020-12-02 22:06
*/
public static void main(String[] args) {
System.out.println("A test of bidirectional linked list");
// Create node first
HeroNode2 heroNode1 = new HeroNode2(1, "Song Jiang", "Timely rain");
HeroNode2 heroNode2 = new HeroNode2(2, "Lu Junyi", "Jade Unicorn");
HeroNode2 heroNode3 = new HeroNode2(3, "Wu Yong", "Zhiduoxing");
HeroNode2 heroNode4 = new HeroNode2(4, "Lin Chong", "Leopard head");

//Create a two-way linked list object

// Modify test
System.out.println();
System.out.println("Modify test");
HeroNode2 newHeroNode = new HeroNode2(4, "Gongsun Sheng", "Ruyunlong");

// Test delete
System.out.println("Delete test");

System.out.println();
HeroNode2 newHeroNode2 = new HeroNode2(0, "Small worker", "Father in law");
}
}

// Create a class of two-way linked list
// Initialize the header node and nod the node. Don't move and don't store specific data

}

}

// The method of traversing a two-way linked list is the same as that of a single linked list
public void list(){
// Judge whether the linked list is empty
return;
}
// Because the head node cannot be moved, we need a replication node temp
while(true){
// Output the information of this node
System.out.println(temp);
if(temp.next == null){
break;
}
// Move temp backward, otherwise it will be an endless loop
temp = temp.next;
}
}

// This method is added to the tail of the bidirectional linked list by default
// Because the head node cannot be moved, we need an auxiliary node temp
// Traverse the linked list to find the last
while (true){
// Find the end of the linked list
if(temp.next == null){
break;
}
temp = temp.next;
}
// When exiting the white loop, temp points to the end of the linked list
// Form a two-way linked list
temp.next=heroNode;
heroNode.pre = temp;
}

boolean flag = false; // Identifies whether it can be inserted
}else {
while (true) {
if (temp.no == heroNode.no){
flag = true;
break;
}else if (temp.no > heroNode.no){
break;
}
if(temp.next == null){
break;
}
temp = temp.next;
}
if (!flag){
heroNode.next = temp;
heroNode.pre = temp.pre;
temp.pre.next=heroNode;
temp.pre=heroNode;
}
}

}

// Modifying the order receiving content of a two-way linked list is the same as that of a one-way linked list, except that the type of node has changed
public void update (HeroNode2 newHeroNode){
return;
}
// Finding the node that needs to be modified is a no query
boolean flag = false; // Indicates whether the node is found
while (true) {
if (temp == null) {
break; // Indicates that the traversal of the linked list has ended (not that the last node has gone out)
}
if (temp.no == newHeroNode.no){
// Find the node to modify
flag = true;
break;
}
temp = temp.next;
}
// Judge whether to find the node to be modified according to the flag
if(!flag){
}else {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}
}

// Delete a node from the bidirectional linked list
// For a two-way linked list, you can directly find the node to be deleted, instead of finding the previous node of the node to be deleted like a single linked list
// You can delete it after you find it
public void delete(int no){
// Judge whether the current linked list is empty
if (temp == null) {
System.out.println("The current linked list is empty and cannot be deleted");
}
boolean flag = false; // Flag whether the node to be deleted is found
while (true) {
if (temp.no == no){
// The previous node of the node to be deleted was found
flag = true;
break;
}
temp = temp.next;
}
if (flag){
// Can delete
// temp.next = temp.next.next;  [single linked list]
temp.pre.next = temp.next;
if (temp.next != null) {
//  If the last node is not deleted
temp.next.pre = temp.pre;
}
}else {
}
}

}

// Define a HeroNode, and each HeroNode object is a node
class HeroNode2 {
public int no;
public String name;
public String nickName;
public HeroNode2 next; // Point to the next node, which is null by default
public HeroNode2 pre; // Point to the previous node, which is null by default

// constructor
public HeroNode2(int hNo, String hName, String hNickName){
this.no = hNo;
this.name = hName;
this.nickName = hNickName;
}

// For display convenience, override the toString method

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

```

### Train of thought analysis

```package com.luyi.DataStructures.linkedlist;

import com.sun.xml.internal.ws.wsdl.writer.document.soap.Body;
import jdk.nashorn.internal.ir.IfNode;

/**
* josephus problem
* @author Lu Yi
* @create 2020-12-03 16:49
*/
public class Joseph {
public static void main(String[] args) {
}
}

// Create a circular single linked list
// Create a first node. There is no number at present. You are setting the number
private Boy first = new Boy(-1);

// nums does a data check
if (nums < 1 ) {
System.out.println("nums The value of is incorrect");
return;
}
Boy currentBoy = null; // Auxiliary pointers help build circular linked lists
// Use a for loop to create a circular linked list
for (int i =1; i <= nums; i++) {
// Create child nodes by number
Boy newBoy = new Boy(i);
// If it's the first child
if (i == 1){
first = newBoy;
first.setNext(first); // Form a ring
currentBoy = first; // Let currentBoy point to the first child, and the first node cannot be moved
}else {
currentBoy.setNext(newBoy);
newBoy.setNext(first);
currentBoy = newBoy;
}
}
}

// Traverse the current circular linked list
public void list(){
Boy currentBoy = first;
if (currentBoy.getNo() == -1){
System.out.println("The current circular linked list is empty,Unable to traverse");
return;
}
while (true) {
System.out.println("Child number"+currentBoy.getNo());
currentBoy = currentBoy.getNext();
if (currentBoy == first){
break;
}
}
}

// Calculate the order of the child's circle according to the user's input

/**
*
* @param startNo  It means counting from the first child
* @param countNum It means counting
* @param num Indicates how many children there were at first
* @return
*/
public void solveJoseph(int startNo, int countNum, int num){
// Check the data first
if (first.getNo() == -1 || startNo < 1 || startNo > num){
return;
}
// Create an auxiliary pointer helper to help complete the child's circle
Boy helper = first;
// Let the helper point to the last node of the ring queue first
while (true) {
if (helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
//Let the child move first before no-starter
for (int j = 0; j < startNo-1; j++) {
first = first.getNext();
helper = helper.getNext();
}
// When the child counts off, let the first and helper pointers move countNum - 1 time at the same time, and then circle
// Here is a loop operation until there is only one node in the circle
while (true) {
if (helper == first) { // There is only one person in the current circle
System.out.print("Last circle: "+first.getNo()+"");
break;
}
for (int i = 0; i < countNum -1; i++ ) {
first = first.getNext();
helper = helper.getNext();
}
// This is the child's circle after the first point
System.out.print(first.getNo()+" ");
first = first.getNext();
helper.setNext(first);

}

}

}

// Create a Boy class to identify a node
class Boy {
private int no; // number
private Boy next; // Point to the next node, which is null by default

public Boy(int no) {
this.no = no;
}

public int getNo() {
return no;
}

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

public Boy getNext() {
return next;
}

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

```

# Stack

## Array simulation stack

### code implementation

```package com.luyi.DataStructures.stack;

import java.lang.reflect.Array;
import java.util.Stack;

/**
* @author Lu Yi
* @create 2020-12-03 19:54
*/
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack =new ArrayStack(4);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop());
System.out.println(stack.pop());

System.out.println("Traversal stack");
stack.list();
}

}

// Define an ArrayStack to represent the stack
class ArrayStack {
private int maxSize; // Stack size
private int[] stack; // Array, array simulation stack, put the data of the stack into the array
private int top = -1; //Indicates that the stack top is initialized to - 1

// constructor
public ArrayStack (int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}

// Stack full judgment
public boolean isFull() {
}

// Stack empty
public boolean isEmpty() {
}

// Stack operation
public void push (int value) {
// Judge whether it is full
if (isFull()){
System.out.println("The stack is full,Unable to stack");
return;
}
top++;
stack[top] = value;
}

// Out of the stack returns the data at the top of the stack
public int pop () {
// First judge whether the stack is empty
if (isEmpty()){
throw new RuntimeException("Stack empty,no data");
}
return  stack[top--];
}

// Display stack information (traverse the stack). During traversal, it needs to be displayed from the top of the stack
public void list() {
if (isEmpty()) {
System.out.println("Stack empty,no data");
return;
}
int i = top;
while (i >= 0){
System.out.println(stack[i--]);
}
}

}

```

## Stack implementation calculator

### Code implementation (regardless of parentheses)

```package com.luyi.DataStructures.stack;

import java.awt.print.Pageable;
import java.util.Stack;

/**
* @author Lu Yi
* @create 2020-12-03 20:48
*/
public class Calculator {
public static void main(String[] args) {
// Complete the operation of the expression according to the previous idea
String expression = "7*2*2-5+1-5+3-4";
// Create two stacks, count stacks, and turn a symbol
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
// Define the relevant variables required
int index = 0; // For scanning
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' '; // Save the char of each scan to ch
String keepNum = ""; // For splicing multiple bits
// Start scanning Expression with the scanning statement of the while loop
while (true) {
// Get each character of Expression in turn
ch = expression.substring(index, index + 1).charAt(0);
// Judge whether it is numbers and symbols and deal with them accordingly
if (operStack.isOper(ch)) { // If operator
// Judge whether the current symbol stack is empty
if (!operStack.isEmpty()) {
// If there are operators in the symbol stack, compare them. If the priority of the current operator is less than or equal to the operator in the stack, you need to pop out two numbers from the number stack
// Then pop out a symbol from the symbol stack for operation, put the obtained result into the number stack, and then put the current operator into the symbol stack
if (operStack.priority(ch) <= operStack.priority(operStack.peak())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
// Put the result of the operation on the stack
numStack.push(res);
// Put the current operator on the symbol stack
operStack.push(ch);
}else {
// If the priority of the current operator is higher than that of the operator in the stack, it will be directly put into the symbol stack
operStack.push(ch);
}
}else {
operStack.push(ch);
}
}else { // If it's a number, put it directly into the stack. Note that this is a character, not a real number
// numStack.push(ch - 48);   In this case, there is a problem 13 + 1 = > '1', '3' + '1'
// When processing multi digit numbers, you can't find a number and put it on the stack immediately, because it may be multi digit numbers
// When processing numbers, you need to look at one bit after the index of the expression. If it is a number, it will be scanned. If it is a symbol, it will be put on the stack
// Therefore, we need to define a variable keepNum string to splice multiple bits

//Number of processing
keepNum += ch;

// If ch is the last bit of expression, it is directly put on the stack
if (index == expression.length()-1){
numStack.push(ch - 48);
}else {
// Judge whether the next character is an array, continue scanning, and if it is an operator, put it on the stack
// Just look at the last one, not the index++
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// If the latter bit is an operator, the number is stacked
numStack.push(Integer.parseInt(keepNum));
// important!!!!!! Empty keepNum
keepNum = "";
}
}
}
// index +1 and judge whether to scan to the end
index++;
if (index >= expression.length()) {
break;
}
}
// When the expression is scanned, pop out the corresponding numbers and symbols from the number stack and symbol stack in sequence and run
while (true) {
// If the symbol stack is empty, there is only one result in the number stack calculated to the last result
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
System.out.println(expression+" = "+res);
}
}

// You need to create an extension stack directly
// Define an ArrayStack to represent the stack
class ArrayStack2 {
private int maxSize; // Stack size
private int[] stack; // Array, array simulation stack, put the data of the stack into the array
private int top = -1; //Indicates that the stack top is initialized to - 1

// constructor
public ArrayStack2 (int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}

// Stack full judgment
public boolean isFull() {
}

// Stack empty
public boolean isEmpty() {
}

// Stack operation
public void push (int value) {
// Judge whether it is full
if (isFull()){
System.out.println("The stack is full,Unable to stack");
return;
}
top++;
stack[top] = value;
}

// Out of the stack returns the data at the top of the stack
public int pop () {
// First judge whether the stack is empty
if (isEmpty()){
throw new RuntimeException("Stack empty,no data");
}
return  stack[top--];
}

// Display stack information (traverse the stack). During traversal, it needs to be displayed from the top of the stack
public void list() {
if (isEmpty()) {
System.out.println("Stack empty,no data");
return;
}
int i = top;
while (i >= 0){
System.out.println(stack[i--]);
}
}

// View the value at the top of the stack and do not exit the stack
public int peak() {
if (top == -1) {
System.out.println("Empty stack");
return -1;
}
return stack[top];
}

// The finite sum of the return operator assumes that the larger the number of the return value, the higher the priority
public int priority(int oper){
if (oper == '*' || oper == '/') { // java can compare numbers and characters
return 1;
}else if(oper == '+' || oper == '-') {
return 0;
}else {
return -1; // Jiading has only addition, subtraction, multiplication and division in the current calculation formula
}
}

// Judge whether it is an operator
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}

// computing method
public int cal(int num1, int num2, int oper ){
int res = 0;
switch (oper){
case '+' :
res = num1 + num2;
break;
case '-' :
res = num2 - num1; // Pay attention to the order
break;
case '*' :
res = num2 * num1;
break;
case '/' :
res = num2 / num1; // Pay attention to the order
break;
default:break;
}
return res;
}

}
```

## Inverse Polish calculator

### code implementation

```package com.luyi.DataStructures.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
* @author Lu Yi
* @create 2020-12-07 8:45
*/
public class PolandNotation {

public static void main(String[] args) {
// First define an inverse Polish expression
//(3+4)*5-6 => 3 4 + 5 * 6 -
// For convenience, the middle is separated by a space
String suffixExpression = "3 4 + 5 * 6 -";
// 1 now put suffixExpression into an ArrayList
// 2 pass the ArrayList to a method to traverse the ArrayList and complete the calculation with the stack
List<String> rpnList=getListString(suffixExpression);
System.out.println("rpnList:"+rpnList);
System.out.println("The result is: "+calculator(rpnList) );

}

// Put an inverse expression and put data and operators into an ArrayList at a time
public static List<String> getListString(String suffixExpression) {
// Separate suffixExpression by spaces
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>(Arrays.asList(split));
return list;
}
// Complete the operation of the inverse Polish expression
// 1. Scan from left to right and press 3 and 4 into the stack;
// 2. Encounter the + operator, so pop up 4 and 3 (4 is the top element of the stack and 3 is the secondary top element), calculate the value of 3 + 4, get 7, and then put 7 on the stack;
// 3. Put 5 into the stack;
// 4. Next is × Operator, so pop up 5 and 7 and calculate 7 × 5 = 35, put 35 into the stack;
// 5. Put 6 into the stack;
// 6. Finally, the - Operator calculates the value of 35-6, i.e. 29, so as to obtain the final result
public static int calculator(List<String> ls) {
// Creating a stack requires only one
Stack<String> stack = new Stack<>();
// Traversal ls
for(String item : ls) {
// Use a regular expression to get the number
if(item.matches("\\d+")) { // The number of multiple bits matches
// Push
stack.push(item);
}else { // If operator
// pop out two numbers and operate
int b = Integer.parseInt(stack.pop());
int a = Integer.parseInt(stack.pop());
int res = 0;
switch (item) {
case "+":
res = a+b;
break;
case "-":
res = a-b;
break;
case "*":
res = a*b;
break;
case "/":
res = a/b;
break;
default:
throw new RuntimeException("There is a problem with the symbol");
}
stack.push(res+"");
}
}
return Integer.parseInt(stack.pop());
}
}

```

## Convert infix expression to suffix expression

### code implementation

```package com.luyi.DataStructures.stack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
* @author Lu Yi
* @create 2020-12-07 8:45
*/
public class PolandNotation {

public static void main(String[] args) {

// Complete the function of converting infix expression into suffix expression
// 1.  1+((2+3)*4)-5   =>     1 2 3 + 4 * + 5 -
// 2. Because it is inconvenient to directly operate Str, first convert 1 + ((2 + 3) * 4) - 5 to the List corresponding to infix expression
//     ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
// 3. List of infix expression = > list of suffix expression
// 4.  ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =>  ArrayList [1,2,3,+,4,*,+,5]
String expression = "1+((2+3)*4)-5";
System.out.println("Infix expression:"+ toInfixExpression(expression));
List<String> parseSuffixExpressList = parseSuffixExpressionList(toInfixExpression(expression));
System.out.println("Reverse Polish notation :" +parseSuffixExpressList );
//result
System.out.println("expression:"+expression+"="+ calculator(parseSuffixExpressList));

// First define an inverse Polish expression
//(3+4)*5-6 => 3 4 + 5 * 6 -
//(30+4)*5-6 => 30 4 + 5 * 6 -
//4*5-8+60+8/2 =>  4 5 * 8 - 60 + 8 2 / +
// For convenience, the middle is separated by a space
String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
// 1 now put suffixExpression into an ArrayList
// 2 pass the ArrayList to a method to traverse the ArrayList and complete the calculation with the stack
List<String> rpnList=getListString(suffixExpression);
System.out.println("rpnList:"+rpnList);
System.out.println("The result is: "+calculator(rpnList) );

}
// Convert infix expression to corresponding List
public static List<String> toInfixExpression(String s) {
// Define an ArrayList to store the contents of infix expressions
List<String> arrayList = new ArrayList<String>();
int i = 0;
String str; // Splice multiple numbers
char c; // Put each character into c
do {
// If c is a non number, add it directly to ls
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57 ){
i++;
}else { // If it is a number, we need to consider the problem of multiple numbers
str = ""; // str null
while (i < s.length() && (s.charAt(i) >= 48 && s.charAt(i) <= 57)) {
str += c;
i++;
}
}
}while (i < s.length());
return arrayList;
}

// List of infix expression = > list of suffix expression LS = ArrayList [1, +, (, (, 2, +, 3,), *, 4,), -, 5]
public static List<String> parseSuffixExpressionList(List<String> ls) {
// Define two stacks
Stack<String> s1 = new Stack<String>(); // Symbol stack
// The second stack has no pop operation in the whole conversion process, and we need to output it in reverse order later. We replace it with list < string > S2
// Stack<String> s2 = new Stack<String>();
List<String> s2 = new ArrayList<String>();

// Traversal ls
for (String item : ls) {
// If it is a number, add s2
if(item.matches("\\d+")) {
}else if (item.equals("(")) {
s1.push(item);
}else if (item.equals(")")) {
//If it is the closing parenthesis ")", the operators at the top of s1 stack will pop up in turn and press s2 until the left parenthesis is encountered. At this time, this pair of parentheses will be discarded
while (!s1.peek().equals("(")){
}
s1.pop(); // Pop up(
}else {
// When the priority of item is less than that of the operator at the top of s1 stack, pop up the operator at the top of s1 stack and add it to s2. Go to (4.1) again and compare it with the new operator at the top of s1 stack
while (s1.size() != 0 && (Operation.getValue(item) <= Operation.getValue(s1.peek()))) {
}
// You also need to stack the Item
s1.push(item);
}
}
// Add the remaining operators of s1 to s2
while (s1.size() !=0){
}
return s2; // Because it exists in the list without reverse order, the normal output is an inverse expression
}
// Put an inverse expression and put data and operators into an ArrayList at a time
public static List<String> getListString(String suffixExpression) {
// Separate suffixExpression by spaces
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>(Arrays.asList(split));
return list;
}

// Complete the operation of the inverse Polish expression
// 1. Scan from left to right and press 3 and 4 into the stack;
// 2. Encounter the + operator, so pop up 4 and 3 (4 is the top element of the stack and 3 is the secondary top element), calculate the value of 3 + 4, get 7, and then put 7 on the stack;
// 3. Put 5 into the stack;
// 4. Next is × Operator, so pop up 5 and 7 and calculate 7 × 5 = 35, put 35 into the stack;
// 5. Put 6 into the stack;
// 6. Finally, the - Operator calculates the value of 35-6, i.e. 29, so as to obtain the final result
public static int calculator(List<String> ls) {
// Creating a stack requires only one
Stack<String> stack = new Stack<>();
// Traversal ls
for(String item : ls) {
// Use a regular expression to get the number
if(item.matches("\\d+")) { // The number of multiple bits matches
// Push
stack.push(item);
}else { // If operator
// pop out two numbers and operate
int b = Integer.parseInt(stack.pop());
int a = Integer.parseInt(stack.pop());
int res = 0;
switch (item) {
case "+":
res = a+b;
break;
case "-":
res = a-b;
break;
case "*":
res = a*b;
break;
case "/":
res = a/b;
break;
default:
throw new RuntimeException("There is a problem with the symbol");
}
stack.push(res+"");
}
}
return Integer.parseInt(stack.pop());
}
}
// Write a class Operation to return the priority corresponding to an operator
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;

// Write a method that returns a priority number
public static int getValue(String operation) {
int result = 0;
switch (operation){
case "+":
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("The operator does not exist");
break;
}
return result;
}

}
```

# recursion

## Maze problem

### code implementation

```package com.luyi.DataStructures.recursion;

import com.sun.org.apache.xml.internal.resolver.helpers.PublicId;

/**
* @author Lu Yi
* @create 2020-12-07 16:01
*/
public class MiGong {
public static void main(String[] args) {
// Create a two-dimensional array to simulate the maze
int[][] map = new int[8][7];
// Use 1 for walls
// Upper and lower position 1
for (int i = 0; i < 7; i++ ) {
map[0][i] = 1;
map[7][i] = 1;
}
//Left and right position 1
for (int i = 0; i < 8; i++ ) {
map[i][0] = 1;
map[i][6] = 1;
}
//
// Set baffle 1 to indicate
map[3][1] = 1;
map[3][2] = 1;
//map[1][2] = 1;
//map[2][2] = 1;
// Output map
System.out.println("Output map");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
// Using recursive backtracking to find the path map is a reference type, which can dynamically change the value equal to the public variable
if(setWay(map, 1, 1)){
// Export new map
System.out.println("Path of the ball");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}else {
System.out.println("Unable to find");
}

}

// Use recursive backtracking to find the way for the ball
// Description map is a map
//     i. J indicates where to start (i,j)
//     If the ball reaches map[6][5] = the path is found
//     It is agreed that when map[i][j] is 0, it means that the point has not passed. 1 is the wall, 2 is the path (path of small ball) and 3 is that the position has passed but can't pass
//     When going through the maze again, you need to determine a strategy (the direction of action, when you can't get through, go to the next direction of the strategy) down - > right - > up - > left. If you can't get through at this point, go back
/**
*
* @param map Map
* @param i Where do you start
* @param j
* @return Returns true if the path is found, otherwise false
*/
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2){
// Indicates that the path has been found
return true;
}else {
//If the current point has not passed
if (map[i][j] == 0){
// Try down - > right - > Top - > left according to the above strategy
map[i][j] = 2; // False current point can go
if (setWay(map, i + 1, j )){ // Go down
return true;
}else if (setWay(map,i , j + 1)){ // turn right
return true;
}else if (setWay(map, i - 1, j)){ // Go up
return true;
}else if (setWay(map, i,j - 1)){ // turn left
return true;
}else {
// It's a dead end to fail to get through this point
map[i][j] = 3;
return false;
}
}else { // Ken can't walk for 1 is the wall 2 goes through 3
return false;
}
}
}

}

```

### Shortest path analysis

At present, the more stupid method
Set all the strategies in four directions: up, down, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left, right, left

## Eight queens problem

### code implementation

```package com.luyi.DataStructures.recursion;

/**
* @author Lu Yi
* @create 2020-12-07 18:25
*/
public class Queen {
// Define a max to indicate how many queens there are
int max = 8;
static int count = 0;
// Define an array to save the results of Queen placement. Arr [8] = {0, 4, 7, 5, 2, 6, 1, 3}
int[] arr = new int[max];
public static void main(String[] args) {
// Test one
Queen queen = new Queen();
queen.check(0); // Put it in the first position

}
// Write a method to place the n th queen
// Note that when entering the check, there will be a for loop, so there will be backtracking
private void check(int n) {
if(n == max){ // max has put it in place after changing
print();
return;
}
// Put the queen in turn to judge whether there is conflict
for (int i = 0; i < max; i++) {
// First put the current queen in the first column of the row
arr[n] = i;
// Is there a conflict when placing the queen to column i
if (judge(n)){ // No conflict
check(n + 1);
}// If there is a conflict, continue to execute arr[n] = i; Move the line back one position
}
}
/**
* Check whether the queen conflicts with the queen already placed in front when placing the nth queen
* @param n The n th queen
* @return
*/
private boolean judge(int n) { // Indicates the nth queen of the
for (int i = 0; i < n; i++){
// arr[i] == arr[n] judge whether the nth queen and the ith queen are on the same line
// Math.abs(n - i) == Math.abs(arr[n] - arr[i]) determines whether the nth queen and the ith queen are on the same slash (because it is currently a one-dimensional array, and the two-dimensional array needs
//   (by other methods)
// n = 1 represents the second queen. If it is placed in the second row of the second column, arr[1] = 1
// Math.abs(1-0) == 1   Math.abs(1 - 0) == Math.abs(1 - 0) established
// You don't need to judge the same line because n is increasing
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])){ // Math.abs is absolute
return false;
}
}
return true;
}

// Write a position for the printing queen
private void print() {
System.out.print("The first"+(++count)+"species: ");
for (int i = 0;i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}

```

# Sorting algorithm

## Time complexity

### Time frequency

Conclusion:

1. 2n+20 and 2n as n becomes larger, the execution curve is infinitely close, and 20 can be ignored
2. 3n+10 and 3n as n becomes larger, the execution curve is infinitely close, and 10 can be ignored

Conclusion:

1. 2n^2+3n+10 and 2n^2 as n becomes larger, the execution curve is infinitely close, and 3n+10 can be ignored
2. As n^2+5n+20 and n^2 become larger, the execution curve is infinitely close, and 5n+20 can be ignored

Neglect coefficient (not to be ignored for 3rd power and above)

## Bubble sorting

The basic idea of Bubble Sorting is to compare the sorting sequence from front to back (starting from the elements with smaller subscripts)
If the values of adjacent elements are found to be in reverse order, they will be exchanged, so that the elements with larger values will gradually move from the front to the back, just like bubbles under the water.

Optimization:
Because in the process of sorting, each element is constantly close to its own position. If there is no exchange after a comparison, it indicates that the sequence is orderly. Therefore, it is necessary to
During sorting, set a flag flag to judge whether the elements have been exchanged. This reduces unnecessary comparisons. (the optimization mentioned here can be in the bubbling row
(after the preface is written, proceed)

### Code implementation (step)

```package com.luyi.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
* Bubble sorting
* @author Lu Yi
* @create 2020-12-08 13:46
*/
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {3,9,-1,10,-2};

// Show the evolution process of bubble sorting, and compare arr.length-1 times to get the results
/**
* Array after the first sorting
* [3, -1, 9, -2, 10]
* Array after the second sorting
* [-1, 3, -2, 9, 10]
* Array after the third sorting
* [-1, -2, 3, 9, 10]
* Array after the fourth sorting
* [-2, -1, 3, 9, 10]
*/

// The first sort is to put the largest number last
int temp = 0; // Temporary variable
for(int j = 0; j < arr.length - 1; j++ ){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
System.out.println("Array after the first sorting");
System.out.println(Arrays.toString(arr));

// For the second sorting, put the second largest number in the penultimate place, and the last number does not participate in the sorting
for(int j = 0; j < arr.length - 2; j++ ){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
System.out.println("Array after the second sorting");
System.out.println(Arrays.toString(arr));

// For the third sorting, put the third largest number in the penultimate place, and the last two numbers do not participate in the sorting
for(int j = 0; j < arr.length - 3; j++ ){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
System.out.println("Array after the third sorting");
System.out.println(Arrays.toString(arr));

// For the fourth sorting, put the fourth largest number in the penultimate position, and the last three numbers do not participate in the sorting
for(int j = 0; j < arr.length - 4; j++ ){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
System.out.println("Array after the fourth sorting");
System.out.println(Arrays.toString(arr));
}
}

```

### Integrated code

```	int temp = 0; // Temporary variable
for (int i = 0; i < arr.length -1; i++){
for (int j = 0; j< arr.length -1 -i;j++){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
}
}
}
System.out.println("Bubble sorted array");
System.out.println(Arrays.toString(arr));
```

### Optimization of bubble sorting

```		int arr[] = {3,9,-1,10,20};
int count = 0; // How many times did you run
int temp = 0; // Temporary variable
boolean flag = false; // The identification variable indicates whether to exchange
for (int i = 0; i < arr.length -1; i++){
count++;
for (int j = 0; j< arr.length -1 -i;j++){
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag){ // None of the exchanges have taken place, which means that the order has been arranged and there is no need to conduct n-1 again
break;
}else {
flag = false;
}
}
System.out.println("Run away"+count+"Trip");
System.out.println("Bubble sorted array");
System.out.println(Arrays.toString(arr));
/**
* Three times
* Bubble sorted array
* [-1, 3, 9, 10, 20]
*/
```

## Select Sorting Algorithm

### code implementation

```package com.luyi.sort;

import com.sun.xml.internal.txw2.output.IndentingXMLFilter;

import java.util.Arrays;

/**
* @author Lu Yi
* @create 2020-12-08 14:27
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {101,34,119,1};
//selectSort(arr);   Step analysis
selectSortAll(arr);
}
// Select sort
public static void selectSort(int[] arr){
// Use step-by-step derivation
// first round
// Original array 101,34119,1
// First round sorting 1,34119101
int minIndex = 0;
int min = arr[0]; // Initial value
for(int j = 1; j < arr.length;j++){
if (min > arr[j]){
minIndex = j;
min = arr[j];
}
}
int temp = arr[0];
arr[0] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("First round sorting");
System.out.println(Arrays.toString(arr));

// Second round
// First round sorting 1, 34, 119, 101
// Second round sorting 1, 34, 119, 101
min = arr[1]; // Initial value
minIndex = 1;
for(int j = 1; j < arr.length;j++){
if (min > arr[j]){
minIndex = j;
min = arr[j];
}
}
temp = arr[1];
arr[1] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("Second round sorting");
System.out.println(Arrays.toString(arr));

// Third round
// First round sorting 1, 34, 119, 101
// Second round sorting 1, 34, 119, 101
// Second round sorting 1, 34, 101, 119
min = arr[2]; // Initial value
minIndex = 2;
for(int j = 2; j < arr.length;j++){
if (min > arr[j]){
minIndex = j;
min = arr[j];
}
}
temp = arr[2];
arr[2] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("Third round sorting");
System.out.println(Arrays.toString(arr));

/**
* First round sorting
* [1, 34, 119, 101]
* Second round sorting
* [1, 34, 119, 101]
* Third round sorting
* [1, 34, 101, 119]
*/
}
// Complete code
public static void selectSortAll(int[] arr){

for (int i = 0; i < arr.length -1; i++){
int min = arr[i];
int minIndex = i;
for (int j = i+1; j < arr.length; j++ ){
if (min > arr[j]){
min = arr[j];
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = min;
arr[minIndex] = temp;
}
}
System.out.println("Select sort");
System.out.println(Arrays.toString(arr));
}

}

```

## Insertion sort method

### code implementation

There are a group of calves whose test scores are 101, 34, 119 and 1 respectively. Please rank them from small to large

```package com.luyi.sort;

import java.util.Arrays;

/**
* @author Lu Yi
* @create 2020-12-08 15:09
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = {101,34,119,1};
//insertSort(arr);  Step by step demonstration
insertSortAll(arr);
}
// Insert sort
public static void insertSort(int[] arr){
// Use step-by-step derivation to explain, which is easy to understand
// First round 101,34119,1 = > 34101119,1

// Define a number to insert
int insertVal = arr[1]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
int insertIndex = 1 -1 ; // Initializes the previous number of the number to be inserted

// Find the insertion position for insertVal
// Insertindex > = 0 ensures that the inserted position does not exceed the limit
// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
while (insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex]; // 101 101 119 1
insertIndex--; // Insertindex > = 0 terminates when it is less than zero
}
// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
arr[insertIndex+1] = insertVal;
System.out.println("After the first round");
System.out.println(Arrays.toString(arr));

// Second round 34, 101, 119, 1 = > 34, 101, 119, 1

// Define a number to insert
insertVal = arr[2]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
insertIndex = 2 -1 ; // Initializes the previous number of the number to be inserted

// Find the insertion position for insertVal
// Insertindex > = 0 ensures that the inserted position does not exceed the limit
// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
while (insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex];
insertIndex--; // Insertindex > = 0 terminates when it is less than zero
}
// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
arr[insertIndex+1] = insertVal;
System.out.println("After the second round");
System.out.println(Arrays.toString(arr));

// Third round 34, 101, 119, 1 = > 1, 34, 101, 119

// Define a number to insert
insertVal = arr[3]; // Initialization because 101 is already in an ordered array, allowing the number to be inserted
insertIndex = 3 -1 ; // Initializes the previous number of the number to be inserted

// Find the insertion position for insertVal
// Insertindex > = 0 ensures that the inserted position does not exceed the limit
// Insertval < arr [insertIndex] the number of inserts to be inserted needs to be moved back if the insertion position has not been found
while (insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex]; //
insertIndex--; // Insertindex > = 0 terminates when it is less than zero
}
// When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
arr[insertIndex+1] = insertVal;
System.out.println("After the third round");
System.out.println(Arrays.toString(arr));
/**
* After the first round
* [34, 101, 119, 1]
* After the second round
* [34, 101, 119, 1]
* After the third round
* [1, 34, 101, 119]
*/
}

// Total insertion sort
public static void insertSortAll(int[] arr){
int insertIndex = 0; // Previous position of data to be inserted
int insertValue = arr[0];
for (int i = 1; i < arr.length; i++) {
insertIndex = i - 1; // Previous position of data to be inserted
insertValue = arr[i];
while (insertIndex >=0 && insertValue < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];// The previous number of the number to be inserted moves back
insertIndex --; // Position to be inserted
}
// Determine whether assignment is required
if (insertIndex + 1 != i){
arr[insertIndex + 1] = insertValue; // When exiting the while loop, insertIndex + 1 is found at the insertion position (because insertIndex is the previous number of the number to be inserted when it is initialized)
}
}
}
System.out.println("Insert sort");
System.out.println(Arrays.toString(arr));
}
}

```

## Hash sorting algorithm diagram

### The efficiency of code implementation (exchange method) is not very high. Mr. Han's computer spent 17 seconds sorting 80000 random numbers

```package com.luyi.sort;

import java.util.Arrays;

/**
* @author Lu Yi
* @create 2020-12-08 19:45
*/
public class HellSort {
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
//Step by step
//hellSort(arr);
hellSortAll(arr);
}
// Write Hill sort using step-by-step push to (exchange method)
public static void hellSort(int[] arr){
// First round sorting of hill array
// Because the first round of sorting divides 10 data into 10 / 2 = 5 groups
int temp = 0;
for (int i = 5; i < arr.length; i++){
// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
for(int j = i - 5; j >= 0; j -= 5){
// If the current element is larger than the element with step size, it indicates the exchange
if (arr[j] > arr[j + 5]) {
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
System.out.println("After the first round of sorting of hill array");
System.out.println(Arrays.toString(arr));

// Second round sorting of hill array
// Because the second round of sorting divides 10 data into 5 / 2 = 2 groups
for (int i = 2; i < arr.length; i++){
// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
for(int j = i - 2; j >= 0; j -= 2){
// If the current element is larger than the element with step size, it indicates the exchange
if (arr[j] > arr[j + 2]) {
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
System.out.println("After the second round of sorting of hill array");
System.out.println(Arrays.toString(arr));

// The third round of sorting of hill array
// Because the third round of sorting divides 10 data into 2 / 2 = 1 groups
for (int i = 1; i < arr.length; i++){
// Traverse all elements in each group (a total of five groups, two elements in each group) with a step field of 5, such as the comparison between the first number and the fifth number
for(int j = i - 1; j >= 0; j -= 1){
// If the current element is larger than the element with step size, it indicates the exchange
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println("After the third round of sorting of hill array");
System.out.println(Arrays.toString(arr));
/**
* After the first round of sorting of hill array
* [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
* After the second round of sorting of hill array
* [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
* After the third round of sorting of hill array
* [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/
}
// Total Hill ranking (exchange method)
public static void hellSortAll(int[]arr){
int temp = 0;
int group = arr.length/2;
while (group != 0) {
for (int i = group; i < arr.length; i++) {
for (int j = i - group; j >= 0; j -= group) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
group /= 2;
}
System.out.println("Hill sort results");
System.out.println(Arrays.toString(arr));
}

}

```

### The efficiency of code implementation (shift method) is high. Mr. Han's computer spent 1 second sorting 80000 random numbers

```	// Optimize Hill sort method of exchange - > shift method
public static void hellSortBetter(int[] arr){
int temp = 0;
int group = arr.length/2;
while (group != 0) {
// From group elements, directly insert and sort the groups one by one
for (int i = group; i < arr.length; i++) {
int insertIndex = i; //Location to insert
temp = arr[insertIndex];
if(arr[insertIndex] < arr[insertIndex - group]){
while (insertIndex - group >= 0 && temp < arr[insertIndex - group]){
// move
arr[insertIndex] = arr[insertIndex - group];
insertIndex -= group;
}
// The insertion position was found after exiting the while loop
arr[insertIndex] = temp;
}
}
group /= 2;
}
System.out.println("Hill sort results");
System.out.println(Arrays.toString(arr));
}
```

## Quick sorting algorithm

### code implementation

```package com.luyi.sort;

import java.util.Arrays;

/**
* @author Lu Yi
* @create 2020-12-08 21:06
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-9,78,0,23,-567,70};
quickSort(arr, 0,arr.length-1 );
System.out.println("arr: "+ Arrays.toString(arr));
}

/**
*
* @param arr
* @param left Index on the left
* @param right Index on the right
*/
public static void quickSort(int[] arr, int left, int right){
int l = left; // Left subscript
int r = right; // Right subscript
int temp = 0; //Temporary variable
// pivot axis
int pivot = arr[(left + right) / 2];
// As long as the index on the right is larger than the index on the left, the cycle continues. The purpose is to put the value smaller than pivot on the left and the value larger than pivot on the right
while (l < r){
// On the left of pivot, always find a value greater than or equal to pivot before exiting
while (arr[l] < pivot){ //Find the pivot itself at most
l += 1;
}
// On the left of pivot, always find a value less than or equal to pivot before exiting
while (arr[r] > pivot){ //Find the pivot itself at most
r -= 1;
}
// If it is true, it means that the values on the left of pivot have all been less than or equal to the values of pivot, and the values on the right have all been greater than or equal to the values of pivot
if(l >= r){
break;
}
// exchange
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;

// Judge if it is found that arr[l] = pivot r moves forward L after the exchange--
if (arr[l] == pivot){
r -= 1;
}else if (arr[r] == pivot){// Judge if it is found that arr[r] = pivot l moves backward L after the exchange++
l++;
}
}
// If l == r, L + + and r --, otherwise stack overflow will occur
if (l == r ){
l++;
r--;
}
// Left recursion
if (left < r) {
quickSort(arr,left,r);
}
// Recursive right
if (right > l) {
quickSort(arr, l, right);
}
}
}

```

## Merge sort

### code implementation

```package com.luyi.sort;

import java.util.Arrays;

/**
* Merge sort
* @author Lu Yi
* @create 2020-12-09 9:50
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8,4,5,7,1,3,6,2};
int[] temp = new int[arr.length]; // Merging and sorting requires additional space
mergeSort(arr, 0, arr.length-1, temp);

System.out.println("After merging and sorting: "+ Arrays.toString(arr));
}

//Opening + closing method
public static void mergeSort(int[] arr, int left, int right, int[] temp){
if (left < right) {
int mid = (left + right) / 2; // Intermediate index
//Decompose recursively to the left
mergeSort(arr, left, mid, temp);
// Decompose recursively to the right
mergeSort(arr, mid+1, right, temp);

// The above is the decomposition method
// Merge once after each decomposition
merge(arr, left, mid, right,temp);
}
}

/**
*  Merging method
* @param arr Original array
* @param left Initial index of left ordered sequence
* @param mid  Intermediate index
* @param right Index right
* @param temp  Transit array
*/
public static void merge(int[] arr,int left, int mid, int right, int[] temp){
int i = left; //Initialization i, the initial index of the ordered sequence on the left
int j = mid+1;// Initialize j the initial index on the right
int t = 0; //Initialize the index of temp array

// First fill the left and right (ordered) data into temp according to the rules
// Until one of the ordered sequences on the left and right is processed
while (i <= mid && j <= right){
// If the current element of the ordered sequence on the left < = the current element of the ordered sequence on the right, put the current element on the left at the position of t of temp
if (arr[i] <= arr[j]){
temp[t++] = arr[i++];// Put back
}else {
temp[t++] = arr[j++];
}
}
// Add the data of the remaining array to the tail of temp at one time
while (i <= mid){ //The ordered sequence on the left has the remaining data. Add the remaining ordered data to the temp array in turn
temp[t++] = arr[i++];
}
while (j <=right){ //The ordered sequence on the right has the remaining data. Add the remaining ordered data to the temp array in turn
temp[t++] = arr[j++];
}

// Put the temp array back into the arr
// Note that not all are copied at a time
t = 0;
int tempLeft = left;// The first merge tempLeft=0 right=1 / / the second merge tempLeft=2 right=3 / / the third merge tempLeft=0 right=3
//  Last merge tempLeft=0 right=7
while (tempLeft <= right){
arr[tempLeft++] = temp[t++];
}
}

}

```

## Cardinality sort (bucket sort)

Stable sorting: if the array to be sorted has two identical numbers, such as A1 = A2 = 1 {a1,2,3}, A2} after sorting {a1,a2,2,3} a1 is still in front of A2

### code implementation

```package com.luyi.sort;

import java.util.Arrays;

/**
* @author Lu Yi
* @create 2020-12-09 13:43
*/
public static void main(String[] args) {
int[] arr = {53,3,542,748,14,214};
}
// Simulate one round of sorting (sorting for the single digit of each element)

// Define a two-dimensional array to represent a two-dimensional array, and each bucket is a one-dimensional array
// Description the two-dimensional array contains 10 one-dimensional arrays
//     In order to prevent data overflow when putting in numbers, the size of each one-dimensional array is array length()
//     Obviously, space changes time
int[][] bucket = new int[10][arr.length];
// In order to record how many data are actually stored in each bucket, we define a one-dimensional array to record the number of each bucket
// Bucket elementcounts [0] is the number of data put into bucket[0]
int[] bucketElementCounts = new int[10];
for (int j = 0; j < arr.length; j++){
// Fetches the bits of each element
int digitOfElement = arr[j] % 10;
// Put it into the corresponding bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// Put the data in the bucket
int index = 0;
// Traverse each bucket and put the data in the bucket into the original array
for (int k = 0;k < bucket.length; k++){
if (bucketElementCounts[k] != 0){
for (int j = 0; j < bucketElementCounts[k]; j++){
arr[index++] = bucket[k][j];
}
}
// In the first round, you need to set the bucket elementcounts array to zero
bucketElementCounts[k]= 0;
}
System.out.println("The array after the first round of single digit processing:" + Arrays.toString(arr));

// Simulate the second round (sort the ten digits of each element)

for (int j = 0; j < arr.length; j++){
// Fetch the ten digits of each element
int digitOfElement = arr[j] / 10 % 10;
// Put it into the corresponding bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// Put the data in the bucket
index = 0;
// Traverse each bucket and put the data in the bucket into the original array
for (int k = 0;k < bucket.length; k++){
if (bucketElementCounts[k] != 0){
for (int j = 0; j < bucketElementCounts[k]; j++){
arr[index++] = bucket[k][j];
}
}
bucketElementCounts[k]= 0;
}
System.out.println("The second round is the array after processing ten digits:" + Arrays.toString(arr));

// Simulate three rounds (sort the hundreds of each element)

for (int j = 0; j < arr.length; j++){
// Fetch the hundredth of each element
int digitOfElement = arr[j] /100 % 10;
// Put it into the corresponding bucket
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// Put the data in the bucket
index = 0;
// Traverse each bucket and put the data in the bucket into the original array
for (int k = 0;k < bucket.length; k++){
if (bucketElementCounts[k] != 0){
for (int j = 0; j < bucketElementCounts[k]; j++){
arr[index++] = bucket[k][j];
}
}
bucketElementCounts[k]= 0;
}
System.out.println("The array after the third round of processing hundreds:" + Arrays.toString(arr));

}

// Total cardinality sort
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10];
int index;
// Need to get the maximum number
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) {
for (int j = 0; j < arr.length; j++){
int digitOfElement = arr[j] / n % 10;
// Put the corresponding bucket into
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// Put the data in the bucket
index = 0;
// Traverse each bucket and put the data in the bucket into the original array
for (int k = 0;k < bucket.length; k++){
if (bucketElementCounts[k] != 0){
for (int j = 0; j < bucketElementCounts[k]; j++){
arr[index++] = bucket[k][j];
}
}
bucketElementCounts[k]= 0;
}

}
System.out.println("Results of cardinality sorting" + Arrays.toString(arr));
}

}

```

## Comparison of eight sorting algorithms

Heap sorting can only be understood after learning binary tree

# Search algorithm

## Binary search algorithm

### d

Posted by billy_111 on Mon, 02 May 2022 15:25:11 +0300