Three versions and optimization of quick sorting by interval -- friends may not know it

3.2-1 Quick sort （ A sort of permutation ）

The basic idea ： So called exchange , It is to exchange the positions of the two records in the sequence according to the comparison results of the key values of the two records in the sequence , The characteristics of exchange sorting are ： Move the record with large key value to the end of the sequence , Records with smaller key values move to the front of the sequence .

1.hoare edition

Exchange sort links The link to this blog says hoare Sorting method of versions .

Specific code content ：

//1. hoare edition 
int PartSort1(int* a, int begin, int end)
{
    
	int left = begin;
	int right = end;
	int keyi = left; # When the subscript position of the spoon .

	while (left < right)
	{
    
		// Go first on the right , Looking for a small 
		while (left < right && a[right] >= a[keyi])
			--right;
		// Go left , Looking for big 
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[right], &a[left]);

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

	keyi = left;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
    
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort1(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

2. Excavation method （ Pay attention to the digging method. Remember the value of the spoon rather than the subscript , The pit will change ）.

Method planing ： First of all, we know that the first step of quick sorting is to determine the spoon （key） The subscript of this position We regard this position as a （pit） pit （ That is, take this number as a dividing line , Definite interval ）, We pass two subscripts （left and right） Search for .right Look from right to left for comparison key This number is small , Then compare key Fill in the small number to pit（ pit ） in , then right At this time, the subscript position is a new pit; turn left Look for Bi from left to right key It's a big number , Find it and compare it key Fill in this large number to pit in ;left and right When you're done , Fill this hole key This value . At this time, use key This position is divided into two sections , At this time, it's recursion .

Let's look at the code first , There will be a picture demonstration later ：

int PartSort2(int* a, int begin, int end)
{
    
	int left = begin;
	int right = end;
	int key = a[left];
	int piti = left;

	while (left < right)
	{
    
		// Go first on the right , Looking for a small 
		while (left < right && a[right] >= key)
			--right;
		a[piti] = a[right];
		piti = right;

		// Go left , Looking for big 
		while (left < right && a[left] <= key)
			++left;
		a[piti] = a[left];
		piti = left;

	}
	
	a[piti] = key;
	return piti;

}


void QuickSort(int* a, int begin, int end)
{
    
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

Graphic explanation ：

while (left < right)
	{
    
		// Go first on the right , Looking for a small 
		while (left < right && a[right] >= key)
			--right;
		a[piti] = a[right];
		piti = right;

		// Go left , Looking for big 
		while (left < right && a[left] <= key)
			++left;
		a[piti] = a[left];
		piti = left;

	}

And so on to left<right, This condition does not hold .

while (left < right)
		// Go first on the right , Looking for a small 

This time it is a[piti] = key

a[piti] = key;

Results after debugging ：
Insert picture description here

3. Front and back pointer versions （ Note that the subscript of the spoon is prev The subscript ）

Method planing ： First of all, it's the same , First find the subscript position of the spoon （keyi）. We now need two more variables （prev and cur,cur The initial position of pre Back – Namely pre The subscript plus one is cur The location of the subscript of ）, This is different from the previous one ; We just need to know that we pass prev and cur Value exchange of subscript position To ensure that the value less than the spoon moves to the front , Move the big one to the back .（ The concrete is cur Keep moving back , Meet the ratio keyi Small subscript value stop ,cur And pre Subscript plus 1 after （ Notice that it's not prev The value of this position ） The value exchange of the position ; Last cur Stop beyond subscript range .） At this time, use keyi( Namely prev) This position is divided into two sections , At this time, it's recursion .

Let's look at the code first , There will be a picture demonstration later ：

//3.  Front and back pointer versions 
int PartSort3(int* a, int begin, int end)
{
    
	int prev = begin;
	int cur = prev + 1;
	int keyi = begin;


	while (cur <= end)
	{
    
		if (a[cur] < a[keyi] && ++prev != cur)# When prev Add one position and cur Do not exchange at the same time , In fact, exchange can also .
			Swap(&a[cur], &a[prev]);
	  /*if (a[cur] < a[keyi]) { ++prev Swap(&a[cur], &a[prev]); }*/

		++cur;
	}
	Swap(&a[prev], &a[keyi]);

	keyi = prev;
	return keyi;
}


void QuickSort(int* a, int begin, int end)
{
    
	assert(a);

	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);

	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

Graphic explanation ：

while (cur <= end)
	{
    
		if (a[cur] < a[keyi] && ++prev != cur)# When prev Add one position and cur Do not exchange at the same time , In fact, exchange can also .
			Swap(&a[cur], &a[prev]);

		++cur;
	}

end Is the maximum subscript of the array .
Than keyi Move back if the subscript position is large , Move the small one forward .

Debug the first result :

3.2-2 Quicksort optimization

1. The middle of three numbers key
2. Recursion to a small subinterval , Consider using insert sort （ When the number we want to sort is 100000 , When the number recursively to each block is 20 We can use insert sorting — reason ： We can reduce %70-%80 Number of recursions , It can also prevent recursion to the deep stack overflow .）

The middle of three numbers key

Find the middle one in a range as a medicine spoon , In this way, we can reduce the number of recursion , Sometimes I give you an array that is nearly ordered , Maybe the subscript of the spoon you choose is the maximum or minimum , And this method appears This probability is almost No, .

This is very simple for example ： Subscript 0 To 9 Choose from these ten numbers 0 9 4 These three Subscripts in Select the value between （ Be careful ： Not subscript ）.

Code content ：

int GetMidIndex(int* a, int left, int right)
{
    
	int midi = left + (right - left)/2;

	if (a[left] < a[midi])
	{
    
		if (a[midi] < a[right])
		{
    
			return midi;
		}//a[mid] > a[right]  Can be seen as a[mid] Maximum .
		else if (a[right] > a[left])  
		{
    
			return right;
		}
		else
		{
    
			return left;
		}
		
	}
	else  //a[left] >= a[mid]
	{
    
		if (a[midi] > a[right])
		{
    
			return midi;
		}//a[mid] < a[right]  Can be seen as a[mid] Minimum .
		else if (a[right] < a[left])
		{
    
			return right;
		}
		else
		{
    
			return left;
		}

	}
}

3.2-3 Quick sort non recursive

Methods to analyze ： We need to use stacks （ Opened up on the pile ） The nature of – First in, then out （ We can deal with it recursively from left to right .）; Queues cannot be implemented .cpp There are special library functions ,c No, . We achieve this by storing first and then partitioning .

Stack link

Look at the code first and then analyze ：

void QuickSortNonR(int* a, int begin, int end)
{
    
	assert(a);
	
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))// Inside ： If the stack is empty StackEmpty(&st) return Ture（ really ）.
	{
    
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, left, right);
		// left keyi right.
		
		if (keyi - 1 > left)
		{
    
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
		
		if (keyi + 1 < right)
		{
    
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}

		
	}

	StackDestroy(&st);
}

Create a stack , Save the head and tail first .

ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

Out of the stack

		int left = StackTop(&st);
		StackPop(&st);// Delete 

		int right = StackTop(&st);
		StackPop(&st);// Delete 

Determine the range

int keyi = PartSort3(a, left, right);
//[left, keyi-1] keyi [keyi+1, right]

If keyi-1 Less than keyi Push , keyi+1 Greater than keyi Push

		if (keyi - 1 > left)
		{
    
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}
		
		if (keyi + 1 < right)
		{
    
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}

		

while (!StackEmpty(&st))
{
    }// The content inside is equivalent to recursion   The next stack diagram is analogized .

Of course, don't forget to destroy the stack at last .

StackDestroy(&st);