JIYIK CN >

What is "insertion sort"? The concept is as follows: each time a record to be sorted is inserted into the previously sorted sequence according to its key size, until all records are inserted.

Concepts are always somewhat abstract, and can also be called basic ideas. The concept of insertion sort mentioned above can also be said to be the basic idea of ​​insertion sort. Abstract things are always difficult to understand, so what is needed here is to concretize the abstract concepts.

Let's convert it into a team problem: There will be two teams at the beginning, one of which is arranged in order from low to high, named Team A. The other team is disordered, named Team B. As shown below:

Now put the first person of Team B (let's call him Jack) into Team A, and keep Team A in order. To keep Team A in order, we need to find a suitable position for Jack in Team A. The person in front of this position should be shorter than Jack, and the person behind this position should be taller than Jack. Now we can let Jack stand in this position, and Team A is still in order.

Then put the second person of team B (call him Tom) into team A in the same way as jack, to ensure that team A remains in order.

This continues until all the people in Team B join Team A. At this point, the two teams have become one, and this team is in order.

After seeing this, you should have a clearer understanding of insertion sort. But there is still a question here. The sorting problem is to sort a queue, so where are the two teams? Let's change it again. At the beginning, teams A and B stand in the same row, and team A is in front of team B as a whole, and team A is one person. For one person, the queue must be orderly.

Then, let's get closer to the code and map teams A and B into arrays.

3 represents the initial team A, 5, 2, etc. represent the initial team B. 5 is Jack, and 2 is Tom.

When I was learning insertion sort, I understood it according to this idea. At this point, I have basically mastered the idea of ​​insertion sort.

Different ways of converting thoughts into codes will also produce different "factions". For example, the "Spring and Autumn Annals" is always difficult to read, so someone came out to write a commentary on the Spring and Autumn Annals. Different people wrote different comments, such as "Zuo Zhuan", "Gongyang Zhuan", and "Guliang Zhuan". Although they are different, they all inherit the thoughts of the "Spring and Autumn Annals".

Now let's go back to our insertion sort. Now that the ideas are clear, the only difference is the implementation method. The key point is still Team A. When Team A is looking for the right position for Team B, there are many ways to find it.
    1. Starting from the beginning each time to traverse and find the position is called direct insertion sort
    2. Using the binary search method to find the position is called binary insertion sort/half insertion sort

The above two methods are to search and move elements in a queue, and the main time is spent on searching and moving.
There is also a third method, which is to use an additional queue to do a mapping, which can save the time spent on moving.
This method is called:
    3. Table insertion sort

This involves two concepts: time complexity and space complexity. I will not explain these two concepts in this article. I will explain how I understand these two concepts in other blog posts.
Due to space constraints, this chapter does not involve any code. I will only share my understanding of insertion sort. In other articles later, I will provide you with the implementation code of each method I wrote.