当前位置：网站首页>[C language] three implementations of quick sorting and optimization details

Here for quick sort , To achieve its recursive edition ：hoare edition ( At the very beginning )、 Dig a hole edition 、 Front and back pointer edition , Then there are some optimizations for these problems . In the end Non recursive Implementation of version .

One 、hoare edition

1. thought

First , This is the first quick sort version .

Again , We first sort a number , Sort the two sides in the back . This makes use of the idea of partition , Recursive version .

Then we aim at each round , It starts with Make sure the leftmost one is the target value , As the key, Subscript to be keyi, Define a variable to store the left left( One grid ahead of the target value ), Store the variables on the right right We aim at ascending arrangement , So look for small on the right , Look big on the left ( If the definition of the rightmost is just the opposite , Look for small on the right , Look big on the left , Depending on personal preference )

then , We need to Find the small one first (right), Find a small one or encounter left stop , then left Moving to the right , Find a big stop or encounter right stop . If the two meet, that is, any of the above encounters left/right Just exchange with the target value , Otherwise, it would be right and left Exchange values , Which step should I take after the exchange .

* During this period, we must strictly guarantee right>left Unless we meet , Otherwise it will happen left and right The result of cross miss . additional , The judgment condition cannot only be greater than or less than , Also equal to the situation, write , Otherwise, there will be an endless cycle left and right I can't walk ~

This is the way of one round , Then we can use the recursive method of divide and conquer to arrange the two sides after our round ~

* Arrange this round and pack it . In this way, the latter three methods can be packaged , Divide and conquer only needs to be in one , And add the judgment that when the tail passed in is greater than or equal to the head, the recursion can be ended .

2. Code

//hoare edition 
int PartSort1(int* a, int head, int end)
{
	int target = head;
	int left = target + 1;
	int right = end;

	while (right > left)
	{
		// Look on the right first , Find the ratio target Stop the small number at     The following is a graphic analysis , If you don't add an equal sign , You're going to fall into a dead circle ~
		while (right > left && a[right] >= a[target])
		{
			right--;
		}

		while (right > left && a[left] <= a[target])
		{
			left++;
		}

		if (right > left)
			Swap(&a[right], &a[left]);
	}
	if (a[right] < a[target])// Prevent two numbers from being passed in , Not once into the cycle , Then you can't judge and target The size of the array element where the position is located 
		Swap(&a[target], &a[right]);
	target = right;
	return target;
}

The subsequent version is in divide and conquer ~

Two 、 Pit version

1. thought

Maybe I want to hoare The version looks easier to understand , With the basic idea unchanged , It is slightly improved, and the exchange of the two becomes pit filling .left right and key keyi All unchanged , That is, the left moving part Moving part on the right The target Target subscript .

Just at the beginning , preservation key value And then I'm going to take this keyi The array value of the position is treated as the first pit , Then look for the small one on the right and start looking for the small , Find a small stop or encounter left stop , The same is true of looking on the left . If the two meet , Just talk key The value is filled in this position . without , At the beginning, it is to find a small position on the right and fill its value keyi The location of , Then form a pit by yourself and find the big one on the left to fill , Then you can fill in left and right , Until the two meet .

There is nothing to say about divide and conquer . The general idea is as follows .

2. Code

// Pit version 
int PartSort2(int* a, int head, int end)
{
	int keyi = head;
	int left = head + 1;
	int right = end;
	int key = a[keyi];
	while (right > left)
	{
		// First, find the ratio on the right key Small value , Then fill the pit to produce a new pit 
		while (right > left && a[right] >= key)
			right--;
		a[keyi] = a[right];
		keyi = right;

		// Find the big one on the left and fill the hole 
		while (right > left && a[left] <= key)
			left++;

		a[keyi] = a[left];
		keyi = left;
	}
	a[keyi] = key;
	return keyi;
}

3、 ... and 、 Front and back pointer versions

1. thought

First , This method is completely different from the above two in the core operation steps .

Here, the double pointer moves back and forth , The front pointer starts from the second , The first is the target value and is also the position of the subsequent pointer , The front pointer keeps moving back , When it is lower than the target value , The back pointer moves one step back ,（ At this time, it must be larger than the target value , Because the front pointer did not stop ） Then the values in the two positions are exchanged .

Until the post pointer moves out of the bounds of the array , Then the position of the back pointer is at the original position ( Place of birth ) Or swap the small back position , In short, the position pointed by the pointer at this time is either the target value or a smaller value , So the target value is exchanged , It's done in one round , The rest can be solved by divide and conquer .

* Be careful , You may encounter that the front pointer has not moved , Then the back pointer moves , At this time, the two repeat , There is no need to exchange , Reduce the time complexity when writing code .

2. Code

// Front and back pointer versions 
int PartSort3(int* a, int head, int end)
{
	int keyi = head;
	int prev = head;
	int cur = head + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	return keyi;
}

Four 、 Divide and conquer thoughts ：

Here is the execution of each round , Then finally complete the process of the program ： Start with the first round , After the first round , To the left of the target value is begin And the target value subscript minus one , Add one sum to this paragraph and the target value end These two paragraphs can . The later recursion agrees with this principle , Until the recursion stops when there is no element or only one .

Code :

// Quick sort ：
void QuickSort(int* a, int head, int end)
{
	// End mark 
	if (head >= end)
		return;
	assert(a);

	int target = PartSort(a, head, end);

    // Enter recursion , The idea of divide and rule 
    // On the left 
	QuickSort(a, head, target - 1);
	// On the right 
	QuickSort(a, target + 1, end);

}

5、 ... and 、 Two optimizations

After the introduction of the above methods , I believe you have a certain understanding of fast platoon . Now propose a scenario , Let's take a look at the performance of our fast platoon .( notes The above three methods achieve the effect of fast uniform arrangement )

1. Take the three Numbers

Like platoon 1 2 3 4 5 6 7....n and 3 2 5 1 4 6 7....

It's almost time to row first Probably N*N The second is the normal time complexity , Why is that ？ The reason is that according to the characteristics of quick sorting , The speed of quick sort depends on the position of the target value At the beginning, if you row in the middle , Then it can evolve into dichotomy , But like this closer to order , Then every time the target value is at the edge , Then the other end of the divide and conquer will be useless , Always deal with one side , Efficiency is naturally low .

therefore , This shows that the target value is good or bad . To avoid this happening , We can do something about choosing the target value , There are random values , Take medium from three ..... But it is easier to use three numbers to get the middle , After all, random values have certain randomness , I don't know . Now let's talk about triple arithmetic ：

Pass in the original array , Take the head , tail , Three values in , Then compare the three values , Choose the middle value , return . The code is very simple , as follows ：


// Three data extraction optimization key
int TakeMiddle(int* a, int head, int end)
{
	int middle = (head + end) / 2;
	if (a[head] < a[middle])
	{
		if (a[end] > a[middle])
			return middle;
		else if (a[end] > a[head])
			return end;
		else
			return head;
	}
	else
	{
		if (a[middle] > a[end])  //head  > middle
			return middle;
		else if (a[end] > a[head])
			return head;
		else
			return end;
	}
}

Then the operation is to select the target value , Unchanged before the cycle ( All three methods are ), Then get the subscript , Exchange with it , You don't need to touch the code written below ：

	int keyi = TakeMiddle(a, head, end);
	Swap(&a[target], &a[keyi]);

2. Inter cell optimization

When the number of recursion to row is relatively small , At this time, you will find that there are a lot of iterations , At this time, compared with ordinary methods such as ( Insertion sort ) Efficiency will be a little low , therefore , For each incoming head and end, It is enough to divide in a certain interval ：

	// Insert sorting is used between cells to alleviate the problem of excessive recursion in the last few layers 
	if (head - end > 10)
	{
		// Enter recursion , The idea of divide and rule 
		// On the left 
		QuickSort(a, head, target - 1);
		// On the right 
		QuickSort(a, target + 1, end);
	}
	else
	{
		// Micro data can be sorted by inserting 
		InsertSort(a, end - head + 1);
	}

6、 ... and 、 Non recursive implementation of quick sorting

1. thought

actually , Non recursive sorting is theoretically no different from recursive sorting , Just divide and conquer or store Section , stay Between partitions Changes have taken place during each round of operation .

First , This problem is raised because recursion is very easy to cause stack overflow , The memory of stack is very small . therefore , At this time, can we divide the interval without using recurrence ？ Actually , We find that recursion is actually equivalent to different intervals passed in each time , So when we use non recursion , Just go into different intervals every time .

So how to realize that the interval of each cycle is different ？

This requires a storage mechanism . Store ？ Review previous basic data structure knowledge , We only bring stacks , queue , Data structures such as heaps . So is it just right for stacks and queues to be used in this ？

Right , When implementing stacks and queues , Using heap memory , Heap memory is very large , Don't worry about overflow . Then use the first in and last out of the stack , First in, first out principle of queue , Each cycle saves the interval , Store after one round , In this way, we can solve our problems .

When it is realized , First, insert the head and tail into the stack or queue , If stack, insert the end first , And then in the head , The queue is just the opposite , Then enter the cycle , First pop up the interval element , Enter a cycle , After the cycle , Follow the above steps in the left and right ranges of the target value .

Note that when inserting in the loop, judge the stack or column conditions , That is, the left and right of the interval must be greater than the left , Otherwise, don't enter . The condition is stack 、 It's good to judge whether there are elements in the queue space .

2. Realization ：

// Non recursive version of quick sort ( The problem of recursion , Too deep , Easy stack overflow )
// Before, we used recursive method to make it control the corresponding interval , Now use the stack to store the interval to be changed 
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, begin);

	// When the element in the stack is empty, stop the loop 
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort(a, left, right);//PartSort Any of the above three methods can be used 

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

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

	}


	//StackDestroy(&st);
}

The above is an experiment with stack , You can also use queues ~

原网站

版权声明
本文为[Qihai]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/186/202207051953263277.html