[learn C from me and master the key to programming] insertion sort of eight sorts

1. Insertion sort

Purple is the subscript .

I drew a picture for you , Insert , It's like playing cards , A novice may start by simply taking a hand , Then insert one by one . The same is true for insert sorting , We have to start at a specific location , Compare with the previous position in turn , Then we can sort according to our ideas , The graph above is in ascending order .

We probably understand the meaning , What about us , Think about it Code ：

First, we need to write the insertion logic ：

void InsertSort(int* arr, int n)
{
    
	int end = 0;
	int temp = arr[end + 1];
	if (arr[end] > temp)
	{
    
		arr[end + 1] = arr[end];
		arr[end] = temp;
	}
	else 
	{
    
		;
	}
}

The above is a relatively simple logic , We need to control the loop that is in the range of an array , To meet our requirements .

void InsertSort(int* arr, int n)
{
    
	int end = 0;
	
	while (end >= 0)
	{
    
		int temp = arr[end + 1];
		if (arr[end] > temp)
		{
    
			arr[end + 1] = arr[end];
			arr[end] = temp;
		}
		else
		{
    
			;
		}
		end--;
	}
}

Some people may feel it's over when they get here , Let's run , See if it's over ？

What's going on? ？

Why is it still out of order ？

We found that the above code can only insert end+1 The previous subscript , Make it orderly , So we have to set a quantity , send end It can change .

void InsertSort(int* arr, int n)
{
    
	for (int i = 0;i < n - 1;i++)
	{
    
		int end = i;
		while (end >= 0)
		{
    
			int temp = arr[end + 1];
			if (arr[end] > temp)
			{
    
				arr[end + 1] = arr[end];
				arr[end] = temp;
			}
			else
			{
    
				;
			}
			end--;
		}
	}
}
int main()
{
    
	int arr[] = {
     9,8,7,6,5,4,3,2,1 };
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

result ：

This is c Language to achieve insertion sorting .