Recently, there was a little partner interview. I had a headache about data structure and algorithm. I sorted out a wave of data to help you quickly master the interview of data structure and algorithm. I feel useful. I like and support you!

No, go straight to the dry goods.

**catalogue**

Q1: sorting of knowledge points of data structure and algorithm:

Q2: the difference between linked list, queue and stack

Q3: brief description of quick sort process

Q4: principle of quick sort algorithm

Q8: what is the difference between AVL trees and "red" trees?

Q9: what is the difference between B tree and B + tree?

Q10: what are the classifications of sorting?

Q11: principle of direct insertion sorting?

Q13: principle of direct selection sorting?

Q14: how does heap sorting work?

Q15: principle of bubble sorting?

Q16: how does quick sort work?

Q17: what's the difference between loop and recursion?

Q18: how to select sorting algorithm?

# Q1: sorting of knowledge points of data structure and algorithm:

The knowledge of data structure and algorithm needs to be mastered. My good friend started the ship to sort out:

# Q2: the difference between linked list, queue and stack

A linked list is a discontinuous data structure on a physical storage unit. By looking at the name, we know that it is a linked structure, just like a group of hands holding hands. Linked lists are unidirectional, bidirectional and circular.

Queue is a special linear table. Its particularity lies in that we can only operate the elements of its head and tail. We can't operate the elements in the middle. We can only delete them in its head and add them in its tail. Just like everyone queuing up to the bank to withdraw money, the first ones must be in the front, and the later ones can only be at the end of the line. All elements must comply with this operation. There are no VIP members, so the phenomenon of jumping in the queue through the back door is impossible. It is a first in first out data structure. Let's take a look at the data structure of the queue.

Stack is also a special linear table. It can only add and delete elements at the top of the stack. There are two operations of stacking in and out of the stack. It's like we stack books one by one. The first book must be stacked at the bottom, and the last book must be stacked at the top. When stacking, it is not allowed to put in from the middle. When taking books, it is also allowed to take them from the top, and it is not allowed to take them out from the bottom or middle.

# Q3: brief description of quick sort process

1) Select a datum element, usually the first element or the last element,

2) The records to be sorted are divided into two independent parts by one-time sorting, and the element values of some records are smaller than the benchmark element values. The element value recorded in the other part is larger than the reference value.

3) At this time, the datum element is in the correct position after it is arranged in order

4) Then, the two parts of records are sorted in the same way until the whole sequence is in order.

# Q4: principle of quick sort algorithm

It is an improvement of bubble sorting, unstable, average / best time complexity O (nlogn), and the worst time complexity O (n) when the elements are basically ordered ²)， Spatial complexity O (logn).

⾸ select ⼀ benchmark elements first, and divide the data to be sorted into two separate parts through ⼀ times sorting, and all ⼀ parts are equal to and equal to the benchmark Elements, all parts are equal to the reference elements, and then recursively sort the two parts of data according to this method.

The ⼀ times division of quick sorting is searched alternately from the two ends until the low and high pointers coincide. The time complexity of ⼀ times is O (n). The time complexity of the whole algorithm is related to the number of division times.

The best case is that the middle number selected for each partition just divides the current sequence equally. After log (n) times, a ⻓ table with ⻓ degree of 1 can be obtained, so that the time complexity is O (nlogn).

The worst case is that the number of selected intervals each time is the most ⼤ or ⼩ element in the current sequence, which makes ⼦ tables obtained from each partition empty ， In this way, the data table with ⻓ degree n needs n times of division, and the overall sorting time complexity O (n ²)。

# Q5: briefly describe the time complexity, space complexity and stability comparison of various algorithms

Sorting algorithm | Average time complexity | Worst time complexity | Spatial complexity | Is it stable |

Bubble sorting | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | yes |

Select sort | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | no |

Direct insert sort | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | yes |

Merge sort | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（n）O（n） | yes |

Quick sort | O(nlogn)O(nlogn) | O（n2）O（n2） | O（logn）O（logn） | no |

Heap sort | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（1）O（1） | no |

Shell Sort | O(nlogn)O(nlogn) | O（ns）O（ns） | O（1）O（1） | no |

Count sort | O(n+k)O(n+k) | O(n+k)O(n+k) | O(n+k)O(n+k) | yes |

Cardinality sort | O(N∗M)O(N∗M) | O(N∗M)O(N∗M) | O(M)O(M) | yes |

Q6: what is an AVL tree?

AVL tree is a balanced ⼆ fork search tree. After adding and deleting nodes, balance is achieved again through tree rotation. Right rotation refers to taking a node as the middle node, sinking it to the position of the current right node, and making the current left node as the root node of the new tree, also known as clockwise rotation. Similarly, left-handed It takes a node as the middle node, sinks it to the position of the current left node, and makes the current right node as the root node of the new tree, also known as Rotate counterclockwise.

#

Q7: what is a "red tree"?

The "red" tree was invented in 1972 and is called a symmetric "B" tree. It was officially named "red" tree in 1978. The main feature is to add "attributes" on each node to represent the node color, which can be red or "red".

The "red" tree is similar to the AVL tree. It maintains the body balance through rotation during insertion and deletion, so as to obtain better search performance from the "red" tree. Compared with AVL trees, the red tree does not pursue that the degree difference of all recursive trees does not exceed 1, and ensures that the shortest path from the root node to the leaf tail does not exceed twice the shortest path, so the worst time complexity is O (log n).

Through re - landing and left - right rotation, the "red" tree has more effectively completed the "balance adjustment" after insertion and deletion. In essence, a "red" tree is also a "cross search tree", which introduces five additional constraints: ① nodes can only be "red" or "red". ② The root node must be "". ③ All nil nodes are. ④ Two adjacent red nodes cannot appear on each path. ⑤ In any recursive ⼦ tree, all paths from the root node to the leaf ⼦ node contain the same number of ⾊ nodes.

These five constraints ensure that the worst time complexity of adding, deleting, and searching the "red" tree is zero O(logn)。 If the left node or the right node of a tree does not exist, it is recognized as a tree. Any rotation of the "red" tree can be completed within three times.

#

Q8: what is the difference between AVL trees and "red" trees?

The balance of "red" tree is not as good as that of AVL tree. It only maintains the balance caused by planting, and does not strictly ensure that the degree difference between the left and right trees does not exceed 1. This leads to the fact that when the number of nodes is the same, the degree of "red" tree may be higher, that is, the average number of searches will be higher than that of AVL tree in the same case.

During insertion, both the "red" tree and AVL tree can restore balance within two more rotations. During deletion, because the "red" tree only pursues balance, the "red" tree can restore balance by three more rotations, and the "AVL tree" needs o (logn) times at most. When inserting and deleting the AVL tree, it will backtrack upward to determine whether rotation is required. The worst time cost of this backtracking is O (logn), and the step of each upward backtracking of the "red" tree is 2. The backtracking cost is low. Therefore, it is more suitable for frequently inserting and deleting red trees.

Q9: what is the difference between B tree and B + tree?

Each node in the B + tree stores key and data at the same time. In the ⽽ B + tree, only the leaf node stores data, and the ⾮ leaf node only stores key. InnoDB optimizes the B + tree and adds ⼀ linked list pointers to adjacent leaf ⼦ nodes on each leaf ⼦ node to form a B + tree with sequential pointers, which improves the performance of ⾼ interval access.

The advantages of B + tree are: ① since the B + tree does not contain data information on the leaf node, it can store more keys in the memory, store the data more closely, have better space efficiency, and access the associated data on the leaf node also has better cache life Medium rate. ② The leaf ⼦ nodes of B + tree are connected, so the traversal of the whole tree only needs ⼀ sublinear traversal of leaf ⼦ nodes. The ⽽ B tree requires recursive traversal of each ⾏ layer. Adjacent elements may not be adjacent in memory, so the cache life is not as good as the B + tree. However, B-tree also has advantages. Since each node contains key and value, the frequently accessed elements may be closer to the root node and access more quickly.

Q10: what are the classifications of sorting?

Sorting can be divided into internal sorting and external sorting. What is entered in memory is called internal sorting. When the amount of data is very large, it is necessary to copy all data to memory and make external memory, which is called external sorting.

Internal sorting includes ⽐ comparison sorting and ⾮ comparison sorting, ⽐ comparison sorting includes insertion / selection / exchange / merge sorting, and ⾮ comparison sorting includes counting/ Cardinality / bucket sort.

Insertion sort includes direct insertion / Hill sort, selection sort includes direct selection / heap sort, and exchange sort includes bubble / quick sort.

#

Q11: principle of direct insertion sorting?

Stable, average / worst time complexity O (n) ²)， When the elements are basically ordered, the best time complexity is O (n) and space complexity is O (1).

Insert the records to be sorted into the appropriate position of the ordered group records according to the keyword of each time until all records to be sorted are inserted into ⽌.

Direct insertion does not benefit the orderly sequence to be inserted. When inserting the i-th element, you can find the insertion position insertindex through sub search, and then move all elements between I and insertindex back to the insertion position.

# Q12: how does Hill sort work?

It is called reduced incremental sorting, which is an improvement on direct interpolation sorting. It is unstable, with average time complexity O (n ^ 1.3 ^) and worst time complexity O (n ²)， The best time complexity O (n) and space complexity O (1).

The records are grouped according to the "fixed increment" of the subscript, and each group is sorted by "direct interpolation". After each sorting, the increment is reduced. When the increment is reduced by ⾄ 1, the sorting is completed.

# Q13: principle of direct selection sorting?

Unstable, time complexity O (n) ²)， Spatial complexity O (1).

Each time the most ⼩ element is found in the unordered sequence, the position is exchanged with the ⼀ element of the unordered sequence, and then repeated in the remaining unordered sequence This operation continues until all elements are sorted.

#

Q14: how does heap sorting work?

It is an improvement of direct selection sorting, unstable, time complexity O (nlogn), space complexity O (1).

Treat the records to be sorted as a complete ⼆ fork tree. You can create a ⽴ root heap or ⼩ root heap. The value of each node in the ⼤ root heap is not different from its ⼦ node Value, the value of each node in the root heap is not equal to its node value.

Take the ⼤ root heap as an example. When building the heap ⾸ first take the last ⼀ node as the current node. If the current node has ⽗ node and the value ⼤ is in ⽗ node, the current node and ⽗ node will be exchanged. When removing, first temporarily store the value of the root node, and then the last node replaces the root node and serves as the current node. If the current node has a node with a value of ⼦ and the value of ⼩ node, it will be exchanged with the node with a value of ⼤ and the heap will be adjusted Returns the temporary value after.

Q15: principle of bubble sorting?

Stable, average / worst time complexity O (n) ²)， When the elements are basically ordered, the best time complexity is O (n) and space complexity is O (1).

⽐ for adjacent elements, if the ⼀ th ⼆ th ⼤ is exchanged, do the same for each ⼀ pair of adjacent elements, starting from the ⼀ th pair To the last ⼀ pair at the end, the end elements are ordered after each ⼀ round of sorting. Repeat the above steps for n elements n - 1 times to complete the sorting.

When the sequence has been ordered, it will still enter unnecessary comparison. You can set a flag to record whether there is element exchange. If you do not end the comparison directly.

# Q16: how does quick sort work?

It is an improvement of bubble sorting, unstable, average / best time complexity O (nlogn), and the worst time complexity O (n) when the elements are basically ordered ²)， Spatial complexity O (logn).

⾸ select ⼀ benchmark elements first, and divide the data to be sorted into two separate parts through ⼀ times sorting, and all ⼀ parts are equal to and equal to the benchmark Elements, all parts are equal to the reference elements, and then recursively sort the two parts of data according to this method.

The ⼀ times division of quick sorting is searched alternately from the two ends until the low and high pointers coincide. The time complexity of ⼀ times is O (n). The time complexity of the whole algorithm is related to the number of division times.

The best case is that the middle number selected for each partition just divides the current sequence equally. After log (n) times, a ⻓ table with ⻓ degree of 1 can be obtained, so that the time complexity is O (nlogn).

The worst case is that the number of selected intervals each time is the most ⼤ or ⼩ element in the current sequence, which makes ⼦ tables obtained from each partition empty ， In this way, the data table with ⻓ degree n needs n times of division, and the overall sorting time complexity O (n ²)。

Q17: what's the difference between loop and recursion?

Recursive algorithm:

Advantages: less code, introduction.

Disadvantages: its operation requires many function calls. If the number of call layers is deep, additional stack processing needs to be added. For example, stack pressing is required for parameter transfer, which will have a certain impact on the execution efficiency. However, for some problems, if recursion is not used, it will be extremely ugly code.

Loop algorithm:

Advantages: high speed and simple structure.

Disadvantages: not all problems can be solved. Some problems are suitable for recursion rather than loops. If it is not difficult to use a loop, it is best to use a loop.

# Q18: how to select sorting algorithm?

The data volume scale is relatively large, so direct interpolation or direct selection shall be considered. When the elements are distributed orderly, direct interpolation will reduce the number of times to compare and move records. If stability is not required, it can be selected directly, and the efficiency is slightly higher than direct interpolation.

The data volume and scale are medium, and Hill sorting is selected.

The data volume scale is relatively large, and heap sorting (element distribution close to positive order or reverse order), quick sorting (element distribution random) and merge sorting stability) are considered. Generally, it doesn't bubble.

**Well, after finishing the sorting, the partners will like, collect and comment, and walk up three times with one button. See you next time~~**