Quick sort (diagram +c code)

There are many articles about explaining the principle of quick sort algorithm , There is no explanation here , It's to sort out ideas and methods directly .

Next, we will use image simulation to demonstrate the process of quick sorting step by step , In this way, we will sort out the ideas of rapid sequencing through vision and brain .

Of the following example C The language code will realize the process of image simulation .

One 、 Image simulation Quick sort The process

We choose ten numbers 0~9 As our sort number , And break it up . Then we will arrange them in ascending order . Here's the picture ：

1、 Select base number
First of all, you need to find any benchmark number in this sequence , Here we choose the first number 5 As a reference number .( There are many ways to select a benchmark , This is not the only way ) Here's the picture ：

Next, we will take this benchmark number 5 Move to where it should be .

So where should it stay , In fact, this position needs to meet two conditions ： The left side of the position is less than 5 The number of , The right side of the position is greater than 5 The number of ( Ascending ). We call this position the correct position of the number in the sort , abbreviation “ Right place ”.

Now we know that we should 5 Move to its correct position , Then a problem arises , How to find the right position ？

Here we will introduce the core idea of quick sorting , namely “ Search, compare and exchange at both ends ”. We won't explain this idea from words , The following is directly above . It should be noted that , Through “ Search, compare and exchange at both ends ” lookup “ Right place ” By the way, it will be smaller than the benchmark number 5 And greater than the reference number 5 Number homing .

2、 Point to both ends of the unordered sequence with a pointer
We introduce two pointers at both ends , One points to the left , One points to the right , Use them separately left and right Are identified .（ Two end pointers ）

3、 Find comparison Exchange ( This process is a circular process , The circle number is a repeated step )
①、 Right pointer search comparison
Let's first let the right pointer right Search for ( Because it's ascending ,right To find the first , It will also be mentioned later ) Compare with the reference number 5 Small numbers . If the number under the pointer is not smaller than the reference number , Just keep looking forward .（ Find comparison ）
here right The pointer goes to the number 4 when , And benchmark numbers 5 After comparison , Obviously less than . here right The pointer should stop .

② Left pointer lookup comparison
Next let's left The pointer starts looking for a number greater than the reference number 5 The number of , Go to the number 8 when , And benchmark numbers 5 The comparison is obviously greater than ,left The pointer stops .（ Find comparison ）

③ In exchange for
Now? left Pointers and right The pointer points to a number , Next, take out these two numbers for position exchange .（ In exchange for ）

After exchanging
① Right pointer search comparison
Next let right The pointer looks forward for the base number 5 Small number . Go to the 3 when , And the reference number 5 After comparison, it is less than true , stop .（ lookup ）

② Left pointer lookup comparison
let left The pointer continues to look backwards for ratio 5 Big numbers . Go to the 6 Time and 5 Greater than true after comparison , stop .（ lookup ）
③ In exchange for
At this time, take out the value under the two pointers again for position exchange .（ In exchange for ）


① Right pointer search comparison
Give way to right The pointer looks forward for less than the reference number 5 The number of , Go to the 2 When compared with the benchmark number, it is less than , stop .（ lookup ）

② Left pointer lookup comparison （ lookup ）
Give Way left The pointer continues to look backward for more than the reference number 5 The number of , At this point, we can see that the two pointers coincide , At this time, we will stop moving forward , Because the coincidence of two pointers indicates the reference number 5 Of “ Right place ” We have found .

③ In exchange for
Base number found 5 After the correct position of , It is necessary to move the reference number to the correct position , At this time, it is necessary to exchange the numbers in two positions .（ In exchange for ）

After exchanging .

Here we are “ Search, compare and exchange at both ends ” The first round of is officially over , Did you find out ？ Now the benchmark number 5 The left side of the is less than 5 The number of , And the right side is greater than 5 The number of .

To be sure ： Mentioned above right Pointer first , It will be explained here .

We can see by observing the two images exchanged above , And the reference number 5 Exchange position numbers 2 Is less than the reference number 5 Of , After changing positions, it also happens to make 2 It moved to bi 5 The small one is over there . Let's think about why the two pointers just stop at BI 5 Small 2 It's on it . Of course, we did it deliberately .
because right The pointer is to find the base number 5 Small numbers , When it stops, it must stop at less than 5 Above the number of . And then let left The pointer moves ,left The last stop position of the pointer must be and right When we met , This ensures that the stop position of the two pointers must be smaller than the reference number .
After the last position exchange , The small number is to the left of the benchmark number .
Of course , If you choose the benchmark number in a different way , Ascending and descending are different . First, let right Go or left Walking is different .

After finishing the question of pointer order , Let's continue to summarize some findings after this round

A summary of ideas ：
We can find out “ Search, compare and exchange at both ends ” My thought is to find “ Right place ”,
It can be said that through “ Search, compare and exchange at both ends ” The idea of finding the benchmark number “ Right place ”.

You will also find that based on the benchmark 5 For boundaries , Divided into two (2、0、1、4、3) and (6、8、9、7) Two unordered sequences .

The rest of the work is to repeat the above process for two unordered sequences ：
1、 Select base number
2、 Point to both ends of the unordered sequence with a pointer
3、 Search, compare and exchange at both ends
Don't talk much , Let's continue to demonstrate with image simulation .（ The red line indicates the current round “ Search, compare and exchange at both ends ” end ）

This round of “ Search, compare and exchange at both ends ” We have to take it out alone 5 The sequence on the left is sorted , Let's take a look at the last round “ Search, compare and exchange at both ends ” Comparison after sorting ：


Now let's take it out alone 5 The sequence on the left (2、0、1、4、3) Sort
Select base number
We still choose the first number in the sequence 2 As a benchmark .

Point to both ends of the unordered sequence with a pointer
Be careful , This round of pointer points to a number 5 Left side (2、0、1、4、3) Both ends of the sequence .

Find comparison Exchange
No more detailed description here , Whole process image simulation demonstration .
Need to remember this round right Looking for the basis number 2 Big ,left Looking for the basis number 2 Small ( Because it's ascending ), Exchange after finding both , When the two meet, it means “ Right place ” To find .“ Right place ” Once found, you should return the benchmark number .





After finishing this round of sorting , You'll find out , Base number 2 Divide the boundary into (1、0) and (4、3) Two unordered sequences .

Here we are , We also have (1、0) Sequence ,(4、3) Sequence ,(6、8、9、7) Sequence , as well as 6、8、9、7 After sequence sorting (8、9、7) The sequence is not sorted .
I won't use image simulation one by one , Because every round of thinking is the same , That is, each round of processing is to put the benchmark number of this round on “ Right place ” On . Until all the numbers are put in “ Right place ” On , The sorting is over . So we should focus on understanding the above ideas .
After understanding the above ideas , We design the following code .

Two 、 Program code design （C Language ）

After understanding the idea of quick sorting , It's time to think about how to implement it in code .

Carry out the connection problem of each round ：

Here is an important question ： Questions as follows ▼
▲ I don't know when you are looking at the above image simulation , Did you have a question in your mind , The question is , Every round “ Find compare sort ” After execution , How should the program execute the next round ？ How should each round be well connected with the program ？
On this question , Of course, there are many ideas , The following code uses a recursive method to realize the connection of each round .

Below , There are code descriptions and C Code , You can watch it together , There is a recursive process , You need to know something about recursion .

Code description ：

1、 First , call QkSort Function needs to pass three values ,
▷ “ Array ”,“ Left pointer position ”,“ Right pointer position ”.
2、 With variable tmp As the reference number for storing this cycle .
3、 With variable i As the left pointer , Get the passed value ( Variable left Value )
4、 With variable j As the right pointer , Get the passed value ( Variable right Value )
5、 first floor while The internal structure of the external circulation is ：
▷ There is a right pointer that always looks for something smaller than the base number from back to front
▷ There is a left pointer that looks from front to back for a larger number than the benchmark
▷ There is a for exchanging numbers if sentence
6、while After the outer loop is executed, it is found “ Right place ”
▷“ Benchmark number ” Two exchange position expressions of homing ：
▷arr[left] = arr[i];
▷arr[i] = tmp;
7、 The first recursion
▷QkSort(arr, left, i - 1);
▷ This recursion always solves the left sequence of the two sequences generated after each cycle , Until all left sequences are sorted .
▷ therefore , You can see , The second actual argument is always to pass the left pointer to the formal parameter ,
▷ The third actual parameter is always the subscript of the reference number of the previous wheel -1 Pass it to the formal parameter .
▷ In this way, the complete array is virtually cut into two .
▷ After passing the parameter , The operation scope of the function is just an unordered left sequence .
▷ Here's the picture ：

8、 Second recursion
▷QkSort(arr, i + 1, right);
▷ This recursion needs to wait until the left sequence of each round is sorted , That is, the first recursion is executed only after it is executed .
▷ It solves the right sequence of two sequences generated after each cycle , Until all sequences are sorted .
▷ After the program executes all the second recursion , It also means that all sequences complete sorting , The whole sequence has been ordered , Sort complete .
● explain ： The difficulty of this program lies in the understanding of recursion .

C The language code ：

#include<stdio.h>
// Quick sort function , The formal parameter list is an array , Left pointer position , Right pointer position ,int *arr Equivalent to int arr[]
void QkSort(int *arr, int left, int right){
    
	if (left > right)  // The left pointer position must be greater than the right pointer position 
	{
    
		return;
	}
	// Variable tmp As a benchmark , Here, the reference number is specified as the first number of the sequence , That is, the number pointed by the left pointer 
	int tmp = arr[left];
	int i = left; // Left pointer 
	int j = right;   // Right pointer 
	// Outer loop , Exit until the left pointer and the right pointer are equal , Indicates that the current sequence is sorted according to the current benchmark number 
	while (i != j)
	{
       // Inner loop 1, When finding a number smaller than the benchmark number, exit the cycle , This loop controls the right pointer  
		while (arr[j] >= tmp && j > i)
		{
    
			j--;
		}
		// Inner loop 2, When finding a number larger than the benchmark number, exit the cycle , This loop controls the left pointer 
		while (arr[i] <= tmp && j > i)
		{
    
			i++;
		}
		// After the above two internal cycles , At this time, the left pointer and the right pointer point to 
		// Numbers smaller and larger than the reference number 
		// Next, we need to exchange the data of these two pointers 
		if (j > i)// Before switching, judge whether the right pointer is larger than the left pointer 
		{
    
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}// External circulation tail 
	
	// After executing the loop , Find the sorting position of the benchmark number , The reference number tmp And i Position exchange 
	arr[left] = arr[i];
	arr[i] = tmp;
	//*********************************************
	// The following program is recursive , There may be multiple recursive calls 
	//*********************************************
	// At this time, the array is divided into two parts , The left side of the benchmark is smaller than the benchmark , The right side is larger than the benchmark ,
	// Now recursion , Sort the number to the left of the benchmark , At this point, recursion may have multiple layers 
	QkSort(arr, left, i - 1);
	// At this point , The left side of the benchmark number is all in order , And the right side has not been sorted ,
	// Now recursion , Sort the data on the right of the benchmark , At this time, recursion may have multiple layers 
	QkSort(arr, i + 1, right);
}

int main()
{
    
	int arr[] = {
     0, 4, 3, 5, 65, 2, 64, 68, 34, 94, 53, 74, 13 };
	int len = sizeof(arr)/sizeof(int);
	printf(" Value to be sorted ：");
	for (int i = 0; i <=len-1; i++)
	{
    
		printf("%d ",arr[i]);
	}
	printf("\n");
	printf(" Sorted values ：");
	QkSort(arr,0,len-1);// Call the Quicksort function 
	for (int i = 0; i <=len-1; i++)
	{
    
		printf("%d ", arr[i]);
	}
}

Code run results :