Catalog

1.Hoare edition

First step ：

The second step ：

The third step ：

Hoare The illustration ：

Hoare Code ： 

2. Excavation method ：

First step ：

The second step ：        

The third step ：

Diagram of excavation method ：

Excavation code ： 

3. Front and back pointer versions

First step ：

The second step ：

The third step ：

Front and back pointer version diagram ：

Front and back pointer method code ：

Optimize ：

Time complexity ：

The best situation ：

The worst ： 

summary ：

---

If you give us an array , The requirement is that we sort this array , But at the same time, the time complexity is required to be as small as possible . Bubble sorting at this time （ Time complexity O（n^2）） Obviously, I can't count on it , And here's a recognized quick sort method , It was originally made by Hoare On 1962 A binary tree structure of the exchange sort method , Its basic idea is ： In any element sequence to be sorted As a reference value , According to the sorting code, the set to be sorted is divided into two subsequences , All elements in the left subsequence are less than the base value , Right All elements in the subsequence are greater than the base value , Then the leftmost and rightmost subsequences repeat the process , Until all the elements are aligned in their respective positions .

1.Hoare edition

First, let's talk about the general idea ：

First step ：

First find a number as key value （ Usually the leftmost number of the array , It doesn't matter which one to choose here , Fine tune the following code ）, The function is to divide the array into two parts after one sorting ： The left side of the array is less than key Value , To the right of the array is greater than key Value , The boundary is key.（ The actual code is actually saved key The subscript of this number , Facilitate the final exchange ）

The second step ：

In one sort, start from the right side of the array and look to the left one by one , Find a comparison key Small number , Then start from the left of the array and look up one by one to the right , Find a comparison key Large number , After completing the above operations, exchange the two numbers found . Then judge whether the whole array has been traversed , That is, whether the subscripts of the last two numbers exchanged are the same or misplaced . If the traversal is not completed, continue to repeat the above exchange operation , Until the end of the traversal . The final will be key Exchange positions with the number of positions at the end of the last traversal .

At this time, this operation will complete the array about key Value left and right size Division .

The third step ：

After sorting the last time key Find the two arrays around the value again key Value and divide , That is, the so-called function recursion . Until the recursion can't be cut any more . At this time, the array is ordered .

Hoare The illustration ：

Finally, you will find that all of them have become arrays with interval of one , At this time, the whole array is also in order .

Hoare Code ： 

（ Recursive version ）

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

int PartSort1(int* a, int left, int right) // The function returns key The subscript 
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort1(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

2. Excavation method ：

First step ：

First find a pit , Save the value in the pit to key in , At this time, the value in the pit can be overwritten .

The second step ：        

Start from the right side of the array and traverse to the left one by one , Find a comparison key Small number , Then put this value in the pit , Update the pit position to the position of the number just found . Then traverse one by one from left to right , Find a comparison key Large number , Then put this number in the pit , Update the pit position to the position of the number just found . Repeat the above operation , Until the array is traversed . Finally, put key Put it in the last pit .

The third step ：

With key For boundaries , Divide the array into left and right arrays , Then repeat steps 1 and 2 , Until it can no longer be split .

Diagram of excavation method ：

Excavation code ： 

（ Recursive version ）

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[pit] = a[right];
		pit = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pit] = a[left];
		pit = left;
	}
	a[left] = key;
	return left;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort2(a, left, right);
		QuickSort(a, left, keyi - 1);          // Left array 
		QuickSort(a, keyi + 1, right);         // Right array 
	}
}

3. Front and back pointer versions

First step ：

At the beginning ,prev The pointer points to the beginning of the sequence ,cur Pointer to prev Next position of .keyi The pointer points to the beginning of the sequence .

The second step ：

cur Pointer comparison key Small value , If you find it, it's the same as prev The number of the next position exchange position . In the process of searching, if it is the number ratio key Big ,cur The pointer continues to look back ,prev Keep still .cur After completing the traversal , hold key and prev The number pointed to by the pointer is exchanged .

The third step ：

With key The value is the limit , Divide the array into left and right arrays , Then repeat steps 1 and 2 .

Front and back pointer version diagram ：

 

Front and back pointer method code ：

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

int GetMidIndex(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[midi] > a[right])
			return midi;
		else
			return right;
	}
}

int PartSort3(int* a, int left, int right)
{
    // Optimize , Here can speak 
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);


	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && a[cur] != a[++prev])
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	else
	{
		int keyi = PartSort3(a, left, right);
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}
}

Optimize ：

Let's first look at how to calculate the time complexity of this algorithm

Time complexity ：

The best situation ：

Every time the key Values are the median of the array ！

The worst ： 

Every time the key Values are maximum or minimum ！

Then we should try to avoid the worst .

Here you can control key It's worth choosing , Suppose we choose three numbers at random before sorting , Take the median of the three numbers as key value , The worst case can be avoided to some extent ！ Combined with the code written before , Swap the found median with the leftmost number , You can complete the optimization without changing the previous code ！

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
// Take the number in the middle of the three numbers 
int GetMidIndex(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[midi] < a[right])
			return midi;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[left] < a[right])
			return left;
		else if (a[midi] > a[right])
			return midi;
		else
			return right;
	}
}

summary ：

The above are the three implementation methods of fast scheduling , In fact, generally speaking, the essence is the same , Move the small number to the left of the array , Move large numbers to the right of the array . The code here is recursive , To sort the array again and again .

Readers with questions can ask questions in the comment area , At the same time, you are also welcome to make more corrections .