Hill sort c language

Read it in pieces

Hill sort is a kind of insertion sort , It's an improved version of direct insert sort .

Let's first look at direct insertion sorting , The basic idea is , Usually isolate the first number of this pile of numbers first , Then one of its own is order , Then compare the latter number with it , Find the right size and position to insert , After that, the small pile is still orderly , Then compare the back one with the front one , Find the right place to insert , Until it's all plugged in .

Advantages of direct insertion sorting

From the idea of direct insertion sorting, we can know , If this pile of numbers had been more orderly , So direct insertion sorting is very efficient , Because the number of exchanges will be much less .

Disadvantages of direct insertion sorting

But one situation is , Suppose it is sorted from small to large , Ten thousand ordinal numbers have been arranged in front , Here we are 10001 When we count , It happens to be the smallest one , Then you have to exchange all the previous numbers ,, This leads to the problem that the exchange distance is too long , This is what we don't want to see .

Shell Sort

Based on these two characteristics of direct insertion sorting , We introduced an upgraded version of it —— Shell Sort .

Hill sort is also called reduced incremental sort .

In order to solve the problem that the exchange distance of direct insertion sorting is too long , We imagine that if we can put the smaller number in this pile of numbers to be sorted aside , The larger number is on the other side , Then you don't have to cross mountains and rivers when the exchange occurs .

in other words , We need to pre sort this pile of numbers first , The specific operation is , Select a number first interval（ Usually half of the total number of numbers ） As the first increment , Then set the interval to interval As a group , Sort this group by direct insertion , Then shrink interval（ In general, let's go interval halve ） As the second increment , Continue to sort by direct insertion in groups , And so on , Go on , To interval be equal to 1 When , The interval between groups is 1, That is to insert and sort all elements directly , But all the time , This pile of numbers has been relatively orderly , Direct insertion sorting is very efficient at this time .

Code

#include<stdio.h>
void insert(int a[],int n) 
{
	int i,temp,j,interval;
	while(interval>0)// Compared with direct insertion , Namely i and j Changes in interval In units . 
	{
		for(i=interval;i<n;i=i+interval)// Divide into groups . 
		for(j=i;j>0;j=j-interval)// Direct insertion sorting in groups . 
		if(a[j]<a[j-interval]) 
		{
			temp=a[j];
			a[j]=a[j-interval];
			a[j-interval]=temp;
		}
		interval=interval/2;	
	}
} 
int main()
{
	int a[10]={7,3,1,6,2,0,5,8,4,9};
	insert(a,10);
	for(int i=0;i<10;i++)
	printf("%d ",a[i]);
}

link —— Direct insert sort

https://blog.csdn.net/weixin_62264287/article/details/122895216?spm=1001.2014.3001.5501