Take you to know about direct insertion sorting (C language)

introduce ：
In fact, it is the same principle as playing cards （ Take ascending order as an example ）： Take the first card first , Take the second card , Compare backwards and forwards , At this time, it can only be compared with the first card （ If the second card has more points , Put it behind the first card , Otherwise, put it in front ）, Then take the third card , Take it Compare backwards and forwards , Put it in place , Keep your cards in ascending order , The next cards are the same as the previous ones .

The basic idea ： Give Way end Point to the first number , First use tmp Save subscript as (end + 1) Number of numbers , then tmp And, in turn,
Subscript from end To 0 Number of numbers （ From back to front ） Compare （ The direction of symbols depends on whether they are in ascending or descending order , And this step needs to move the element ）, hold tmp Insert the stored value into the appropriate position .
Make the above basic idea into a cycle （ Give Way end The pointing range of is [ 0 , n-1 ] ）

You can find ,
Existing cards in hand ----------------> Subscript from 0 To end The elements of

tmp ----------------> A new card

Compare backwards and forwards , Insert the card into the right place ----------------> take tmp And Subscript from end To 0
Compare the elements of （ Need to move elements ）, hold tmp Insert the stored value into the appropriate position

therefore , After each execution of the loop , Subscript from 0 To end All the elements are ordered .

Code implementation

void InsertSort(int* a,int n)
{
    
	for (int i = 0; i < n - 1;i++)
	{
    
		int end = i;  // Assign a value to end, bring end Move back , Outspread 
		int tmp = a[end + 1];
		while (end >= 0)
		{
    
			if (a[end] > tmp)
			{
    
				a[end + 1] = a[end];
				end--;  // by end Backward to compare two numbers 
			}
			else
				break;
		}

		a[end + 1] = tmp;
	}
}

More articles
Let you understand the sorting of choices （C Language ）
Let you understand bubble sort （C Language ）