Sort 1-insert sort and Hill sort

Preface

One 、 Insertion sort

Direct insertion sort is a simple insertion sort method , Insert the records to be sorted into one by one according to their key values
In an ordered sequence that has been ordered , Until all the records are inserted , We get a new ordered sequence .

In a nutshell ： Upper figure

Of course , The method on the graph inevitably has some special cases

Upper figure ： When it comes to the fourth insertion sort
Of course , When you start writing code , We can write a single trip first , Before hypothesis n-1 It's in order , Let's insert the last number ,

Then write more times , In this way, you can simply write the insertion sort . Of course , I write like this , Is to write the Hill sort introduced below .

void InsertSort(int *arr, int n)// there n yes · The number of elements in the array 
{
	for (int i = 0; i<n-1; i++)// The picture above shows , When we control the outer cycle , As long as the control is less than n-1
	{
		int end=i;
		int tmp=arr[end+1];
		while (end >= 0)
		{
			if (arr[end] > tmp)// Compare the size 
			{	
				arr[end + 1] = arr[end];// Move backward 
				end--;//end--, Move forward 
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;// Prevent the situation mentioned above , Insert... Outside the loop 
	}
}

summary ：

1. The closer the elements are to order , The time efficiency of inserting sorting is higher
2. The time complexity is O(N)
3. The space complexity is O(1)
4. stability ： Stable

The characteristics of the code inserted above are , The front and back pointers are associated , And from left to right

Two 、 Shell Sort

Shell Sort ： Hill sort is also known as reduction increment method , Choose an integer first , Divide all records in the file to be sorted into
Group , All records at a distance of are in the same group , And sort the records in each group . then , take , Repeat the above work of grouping and sorting . When they arrive in =1 when , All records are arranged in a unified group .

To put it simply ：

1. Pre sort first —> Close to order
2. Direct insert sort

Pictured ：

When the data is large , How should we control gap Well ？

1. We can use data to control , First gap=n
2. How to... In the loop gap=(gap/3+1), We use gap/3 Come on, zoom out slowly gap Value
3. When gap When I was younger , The closer to order

Why gap=（gap/3+1） instead of gap=（gap/3） Well ？

1. for instance , When gap=6 when , If it is gap=（gap/3）, So the first cycle ,gap=2, When doing the second cycle ,gap=0 了 , Then you can't play when you go through the following cycle .
2. But when gap=（gap/3）+1 When , First cycle ,gap=3, The second cycle ,gap=2, The third cycle gap=1, And then it's over , Now , The insertion sort to be carried out after the pre sort , Sort complete .
3. gap=1 It is equivalent to inserting sorting , So control gap To control whether the whole program ends , Of course, when performing insertion sorting , The array is nearly ordered , So at this time, the insertion efficiency is very high .

Careful friends should find out , When in the following code gap=1 Is to insert sort

// Shell Sort 

void ShellSort(int *arr,int n )
{
    
	int gap=n;
	while (gap>1)
	{
    
		gap = (gap / 3 + 1);
		for (int i = 0; i < n - gap; i++)
		{
    
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
    
				if (arr[end] > tmp)
				{
    
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}	
}

The outermost part of this code for loop , Take a good look ,
Pictured ： This is a gap=3 When
summary ：

1. Hill sort is an optimization of direct insert sort .
2. When gap > 1 It's all pre sorted , The goal is to make arrays more ordered . When gap == 1 when , The array is nearly ordered , This will soon . So on the whole , Can achieve the effect of optimization . We can compare the performance test after implementation .
3. The time complexity of Hill sort is not easy to calculate , You need to deduce , Derive the average time complexity ： O(N^1.3~N²）
4. stability ： unstable

summary

Learn from the above , We know that the key to Hill's ranking is not the respective ranking after random grouping , It's going to be separated by something “ The incremental ” The records of , Jump around , Improve the efficiency of sorting .