Insert sort and Hill sort

Insertion sort

Insert an element into the sorted array

You can think of the first element of an unordered array as An ordered array with only one element

Then insert the elements in the array one by one into the appropriate position in the ordered array

When all elements are inserted into an ordered array , This array has been set to order

Dynamic diagram demonstration

 

The code logic is as follows ：

Take ascending order

Pass the inserted element through tmp preservation

hypothesis At this time, there are i+1  Elements

The last element of the ordered array （ Largest element ） The subscript , Write it down as end

adopt end Traversal array , Find out the appropriate position for element insertion  

		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;

take tmp And a[end] Compare ,

When  a[end] > tmp when , take a[end] Move back one position , after end--

Then with tmp Compare , Until you find the right place

Two cases of suitable location

1. tmp > end

2.tmp Less than all elements in the array

When you find the right place , The cycle ends , Store the data in the right place （end + 1）

This is the step of inserting an element into an ordered array

Yes n Inserting and sorting an array of elements can be understood as

Insert... Into an ordered array containing one element n-1 Elements

When converted into code, it is

//  Insertion sort 
void InsertSort(int* a, int n)
{
	int i = 0;
	for(i=0;i<n-1;i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

  The time complexity is O(N^2)

Shell Sort

Hill sort is an advanced sort of insert sort , Greatly optimize the efficiency of the insertion sort algorithm

Basic idea and code analysis implementation

Suppose the array has N Elements

Take one less than N The positive integer gap

Set the distance in the array to gap The elements of are divided into a group

Be careful ： The elements between the groups do not coincide , When taking elements , The first group is marked below 0 The element of is the first element

                                                                      The second type is marked as 1 The element of is the second element

                                                                                                                          ......

Insert and sort each group of elements

        int j = 0;
        // Sort each group of elements 
		for (j = 0; j < gap; j++)
		{
			int i = 0;
            // Sort a set of elements 
			for (i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}

After the gap Reduce and repeat the above steps

Take ascending order as an example

When gap > 1 when

This process is called pre sorting , In order to facilitate better and faster insertion sorting

gap The bigger it is , Large elements will reach the rear faster , Small elements move faster to the front

gap The smaller it is , The closer the data is to order

When gap == 1 when

Sort for insertion

in summary

void ShellSort(int* a, int n)
{
	// according to gap  Do the nesting 
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int j = 0;
		for (j = 0; j < gap; j++)
		{
			int i = j;
			for (i = 0; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}

}