Several common sorts

Sort

   Sort ： Sort , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order , There are many applications of sorting in life , Such as the product ranking of a treasure , Ranking of institutions, etc .
 
   Common sorting is divided into ： Insertion sort 、 Selection sort 、 Exchange sort 、 Merge, sort, etc , Insert sort includes direct insert sort and Hill sort , Select sort contains ： Selection sort 、 Heap sort , The exchange sort includes ： Bubble sort 、 Quick sort , Merge sort contains itself .
 
   This time mainly introduces heap sorting in insert sorting and select sorting , The idea of inserting sorting is relatively simple , Its basic idea is like playing cards at ordinary times , Insert the disordered cards from large to small or from small to large into the orderly playing cards one by one , Until all the cards are in order , A more detailed description is as follows ： When inserting the i(i>=1) Element time , Ahead array[0],array[1],…,array[i-1] It's in order , Use at this time array[i] The sort code of and array[i-1],array[i-2],… Compare the sort code order of , Find the insertion position array[i] Insert , The elements in the original position move backward in order .
   Its main code is as follows ：

void InserSort(int* a, int n)
{
    
	
	for (int 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;
	}

}

   To understand first while What's in it , It is equivalent to a single insertion sort , hypothesis end The position is 3, Then start with the third number of the array , from end Subscript to the array 0 The position of... Approaches one by one , if a[end]>a[end+1] Words , take end Move the number of positions back one , then end–, Is to approach the array step by step, and the subscript is 0 The process of , Until before end The number of is ordered , and for The process of statement is equivalent to before control n An orderly process , This is the process of direct insertion , But the time complexity of direct insertion is O(N^2), Because in the worst case of the array （ The array is in reverse order , At this time, ascending order is required ）, Therefore, in view of this situation , Hill proposed an improved direct insertion sorting method , Hill sort .
   The process of Hill sort is from pre sort to direct sort , In the process of pre sorting , Use the method of space sorting , Use gap To represent the size of the entire interval , Its pre sorting idea is consistent with direct insertion sorting , The difference is , Direct insertion sorting is to compare two adjacent numbers , Then move the larger one back （ In ascending order , The descending order is the opposite ）, The pre sorting process is interval gap Compare the two numbers of , The larger one moves back , When gap by 1 when , It is direct insertion sorting ,gap The bigger the value is. , The larger the number, the faster it will reach the end （ In ascending order ）, But the less it approaches order ,gap The smaller it is , The closer it is to order , But the larger the number, the slower it reaches the end , The following figure shows the different gap Under value , Different states of array sorting .
   The code for Hill's sorting is as follows ：

void ShellSort(int* a, 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 = a[end + gap];
			while (end >= 0)
			{
    
				if (a[end] > tmp)
				{
    
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
    
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

   Hill sort through gap To control the pre sorting process , When gap The value is 1 when , The sort is direct insert sort , Finally finish sorting the array , The time complexity of hill sorting is O（n^1.5） about , The calculation of time complexity is cumbersome , There will be no discussion here , In the future, I will continue to share several other sorting ideas , And discuss its time complexity , And stability .