Sort - quicksort

Quick sort
   Quick sort can be done by Hoare Law 、 Excavation method 、 The front and back pointer method is completed in three ways , among Hoare The core idea of law is ： Select the leftmost value of the array as KEY, Then let the rightmost marker point of the array （ Write it down as end） Go ahead （ Go from right to left ） Until you find the first one less than KEY Array of , Then let the leftmost marker point of the array （ Write it down as begin） Go to the right , Until we find the first one greater than KEY The number of , Then exchange the two numbers found above , Repeat the process , Until the two marked points meet （ Because the step length of two marked points is one , So the marker points must meet ） Finally, at the meeting point , take KEY The value of is placed here , The new array must be smaller than... From here to the left KEY value , To the right must be greater than KEY value , And then to begin To KEY-1 And KEY+1 To end It is divided into two intervals for recursion , straight begin>end Main recursion ends , At this time, the recursive returned array is an ordered array , The process is shown in the figure below


   The number after the first trip is shown in the figure below ：

6 The left is smaller than 6, The right side is larger than 6, Then, with 6 The left is an interval and 6 The right is an interval , Repeat the above process respectively , Complete the sorting process of the array ,Hoare The method code is as follows ：

void Swap(int* p, int* q)
{
    
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

int Part1Sort(int* a, int begin, int end)
{
    
	int Mid = GetMidIndex(a, begin, end);
	Swap(&a[Mid], &a[begin]);

	int left = begin;
	int right = end;
	int keyi = left;
	
	while (left < right)
	{
    
		while (a[right] >= a[keyi]&&left<right)
		{
    
			--right;
		}
		while (a[left] <= a[keyi]&&left<right)
		{
    
			++left;
		}
		Swap(&a[left], &a[right]);

	}
	Swap(&a[right],&a[keyi]);
	keyi = left;
	return keyi;
}

void QuickSort(int *a,int begin,int end)
{
    
	if (begin >= end)
	{
    
		return;
	}

	if (end - begin > 10)
	{
    
		int keyi = Part1Sort(a,begin,end);
	    //int keyi = Part2Sort(a, begin, end);
		//int keyi = Part3Sort(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
    
		// Not necessarily the first ten numbers , It could be the middle ten numbers , so a+begin
		InserSort(a+begin,end-begin+1);
	}
}

void TestQuickSort()
{
    
	int a[] = {
     1,2,9,4,6,5,3,7,8 ,-1,-5,15,20,25,100,111};
	int n = sizeof(a) / sizeof(int);
	QuickSort(a,0,n-1);
	PrintArray(a, n);
}

   We will continue to share the other two methods of quick sorting .