Merge sort / quick sort

“ Merger ” To combine two or more ordered tables into a new ordered table .

  The code is as follows ：

// One time fusion function    Time complexity O（n）   Spatial complexity O（n）
void Merge(int arr[], int len, int gap)
{
	int low1 = 0;
	int high1 = low1+gap-1;
	int low2 = high1+1;
	int high2 = low2+gap-1<len ? low2+gap-1 : len-1;

	int *brr = (int*)malloc(len * sizeof(int));
	assert(brr != NULL);
	int i=0;//i Point to the auxiliary space brr The subscript 

	while(low2 < len)// The writing method is not unique ： The purpose is one , Prove that both groups caught by both hands have data 
	{
		while(low1<=high1 && low2<=high2)// Make sure there are still data in the two groups to compare 
		{
			if(arr[low1] <= arr[low2])
			{
				brr[i++] = arr[low1++];
			}
			else
			{
				brr[i++] = arr[low2++];
			}
		}

		// here , There must be a group of hands empty , You need to judge which hand , Do the corresponding 

		while(low1 <= high1)// The left hand is not free , At this time, the left-hand data is transferred to brr Move in 
		{
			brr[i++] = arr[low1++];
		}
		while(low2 <= high2)// The right hand is not free , At this time, the right-hand data is sent to brr Move in 
		{
			brr[i++] = arr[low2++];
		}

		// It should be at this time , Continue to grab two groups back 
		low1 = high2+1;
		high1 = low1+gap-1;
		low2 = high1+1;
		high2 = low2+gap-1<len ? low2+gap-1: len-1;
	}
	// here , Outermost layer while sign out , There are two possibilities ：1. The left hand has data , The right hand is empty   2. Left and right hands are empty 

	while(low1 < len)// The left hand is not free , At this time, the left-hand data is transferred to brr Move in  // Don't write as low1<=high1   Because there's no way to guarantee high1 Legitimacy 
	{
		brr[i++] = arr[low1++];
	}

	// The final will be brr All the data in are overwritten to arr in , that will do 
	for(int i=0; i<len; i++)
	{
		arr[i] = brr[i];
	}
	free(brr);
}

// Merge sort   Time complexity O(nlogn)   Spatial complexity O（n）   stability ： Stable 
void MergeSort(int *arr, int len)
{
	for(int i=1; i<len; i*=2)// O（logn）
	{
		Merge(arr, len, i);
	}
	
}

Quick sort ：

 

 

 

  This is the result of a division , Then continue to divide the two subsequences , Until there is only one element or empty in each part .

The code is as follows （ Recursive writing ）

// Primary partition function    Core function   // Returns the final subscript of the reference value 
int Partition(int *arr, int left, int right)
{
	// Let's talk first. arr In the array [left, right] First value of   As a reference value 
	int tmp = arr[left];

	while(left < right)
	{
		while(left<right && arr[right] > tmp)// The left and right boundaries do not meet, and the current value on the right is greater than the reference value tmp
		right--;

		if(left < right)// If at this time , The left and right boundaries do not meet , That can only prove the right right Found a reference value less than or equal to tmp Value 
		{
			arr[left] = arr[right];
		}
		else
		{
			break;
		}
		

		while(left<right && arr[left] <= tmp)// The left and right boundaries do not meet, and the current value on the left is less than or equal to the reference value tmp
		left++;

		if(left < right)// If at this time , The left and right boundaries do not meet , That only proves the left left Found a value greater than the reference value tmp Value 
		{
			arr[right] = arr[left];
		}
		else
		{
			break;
		}
		
	}

	arr[left] = tmp;// here   because  left == right
	return left;//return right ok
}
void Quick(int* arr, int left, int right)
{
	if(left < right)// Ensure at least two data within this range 
	{
		int par = Partition(arr, left, right);
		if (left < par - 1)
		{
			Quick(arr, left, par-1);
		}
		if (par + 1 < right)
		{
			Quick(arr, par + 1, right);
		}
	}
}
// Quick sort ： Time complexity O（nlogn）  Spatial complexity O（1）   stability ： unstable  
void QuickSort(int *arr, int len)
{
	Quick_Stack(arr, 0, len-1);
}

Characteristics of fast platoon ： The more ordered the data, the slower , The more chaotic, the faster .

Therefore, the code needs to be optimized , Let the data become as messy as possible

// Quick platoon optimization ：
// 1. You need to determine len The length of , The amount of data is too small , Direct call direct insert sort
// 2. Take the middle of three , Take the first value , The value of the middle position , The final value , Take a moderate value and put it in the first position
// 3. Random number method （ Ensure that the more chaotic the original data, the better ）

The code is as follows ：

// Add a new function , Used for the middle of three numbers 
// Take the middle of three , Take the first value , The value of the middle position , The final value , Take a moderate value and put it in the first position 
void Three_Mid(int *arr, int left, int mid, int right)
{
	if(arr[mid] > arr[right])// Make sure the middle value is less than the value on the right 
	{
		int tmp = arr[mid];
		arr[mid] = arr[right];
		arr[right] = tmp;
	}
	if(arr[mid] > arr[left])// Guarantee the middle value   It must be the minimum of three numbers 
	{
		int tmp = arr[mid];
		arr[mid] = arr[left];
		arr[left] = tmp;
	}
	// here   That's not a big or small value    Or on the left , Or on the right 
	if(arr[left] > arr[right])
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
	}
	// here    No big or small value is arr Of left It's in place 

}
// Add a judgment condition to the quick sorting function of the above code , If the data length is less than or equal to 1000, Direct call direct insert function 
void QuickSort(int* arr, int len)
{
	if (len <= 1000)
	{
		InsertSort(arr, len);
		return;
	}

	Quick(arr, 0, len - 1);
}

Quick row non recursive writing （ You need a stack ）

Here I directly call the stack related functions I wrote before , The code will have corresponding comments .

// Non recursive writing of quick sort 
void Quick_Stack(int *arr, int left, int right)
{
	LStack st;// Create a stack header node 
	Init_LStack(&st);// initialization 
	if(left < right)
	{
		int par = Partition(arr, left, right);
		if(left < par-1)
		{
			Push(&st, left);//push For stack function 
			Push(&st, par-1);
		}
		if(par+1 < right)
		{
			Push(&st, par+1);
			Push(&st, right);
		}
	}


	while(!IsEmpty(&st))// Sentenced to empty 
	{
		int p;
		int q;
		Pop(&st, &q);
		Pop(&st, &p);//pop For the stack function 

		int par = Partition(arr, p, q);
		if(p < par-1)
		{
			Push(&st, p);
			Push(&st, par-1);
		}

		if(par+1 < q)
		{
			Push(&st, par+1);
			Push(&st, q);
		}
	}

}
// Quick sort ： Time complexity O（nlogn）  Spatial complexity O（1）   stability ： unstable  
void QuickSort(int *arr, int len)
{
	if(len<=1000)  // Optimize 1： If n Very small 
	{
		return InsertSort(arr, len);
	}


	Quick_Stack(arr, 0, len-1);
}