Quick Sort is often adopted because its sorting efficiency is relatively high among several sorting methods that are all O(N*logN). In addition, the idea of quick sort—the divide-and-conquer method—is indeed practical. Therefore, many software companies like to test this in written tests and interviews, including well-known IT companies such as Tencent and Microsoft. Also, quick sort frequently appears in programming-related exams of various sizes, such as the Software Qualification Exam and the postgraduate entrance examination.

=a

Quick sort is a partition-exchange sort proposed by C.R.A.Hoare in 1962. It uses a divide-and-conquer strategy, usually called the divide-and-conquer method (Divide-and-Conquer Method).

The basic idea of this method is:

• 1. First take one number from the sequence as the pivot.
• 2. In the partition process, put all numbers greater than this number to its right, and all numbers less than or equal to it to its left.
• 3. Repeat step 2 for the left and right intervals until each interval has only one number.

Although quick sort is called the divide-and-conquer method, these three words obviously cannot fully summarize all the steps of quick sort. Therefore, I have provided a further explanation of quick sort: pit digging and number filling + divide-and-conquer.

Let's look at an example first. The definition is given below (it's best to summarize the definition in your own words, as this will help with implementing the code).

 

Take an array as an example, and take the first number in the interval as the pivot.

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

Initially, i = 0; j = 9; X = a[i] = 72

Since the number in a

Starting from j, search to the left for a number less than or equal to X. When j=8, the condition is met. Dig out a

 

The array becomes:

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

Repeat the above steps: first search from back to front, then from front to back.

Search to the left starting from j. When j=5, the condition is met. Dig out a

Search to the right starting from i. When i=5, exit because i==j.

At this point, i = j = 5, and a

The array becomes:

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

It can be seen that the numbers before a

 

Let's summarize pit digging and number filling:

• 1. i = L; j = R; dig out the pivot to form the first pit a[i].
• 2. j--, search from back to front for a number smaller than it. After finding it, dig out this number and fill it into the previous pit a[i].
• 3. i++, search from front to back for a number greater than it. After finding it, also dig out this number and fill it into the previous pit a[j].
• 4. Repeat steps 2 and 3 until i==j, then fill the pivot into a[i].

Following this summary, it is easy to implement the code for pit digging and number filling:

int AdjustArray(int s[], int l, int r) //Return the position of the adjusted pivot { int i = l, j = r; int x = s[l]; //s[l], that is, s[i], is the first pit while (i < j) { // Find a number less than x from right to left to fill s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //Fill s[j] into s[i], then s[j] forms a new pit i++; } // Find a number greater than or equal to x from left to right to fill s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //Fill s[i] into s[j], then s[i] forms a new pit j--; } } //When exiting, i equals j. Fill x into this pit. s[i] = x; return i; }

Then write the code for the divide-and-conquer method:

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//First use the pit-digging and number-filling method to adjust s[] quick_sort1(s, l, i - 1); // Recursive call quick_sort1(s, i + 1, r); } }

Such code is obviously not concise enough, so combine and tidy it up:

//Quick sort void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); // Swap the middle number with the first number. See Note 1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) //Find the first number less than x from right to left j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) //Find the first number greater than or equal to x from left to right i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // Recursive call quick_sort(s, i + 1, r); } }

There are many improved versions of quick sort, such as randomly selecting the pivot, or directly using another sorting method when there is less data in the interval to reduce the recursion depth. Interested friends can study it further.

Note 1: Some books use the middle number as the pivot. To implement this, it is very easy—just swap the middle number with the first number.

Author: MoreWindows

Original article: https://blog.csdn.net/morewindows/article/details/6684558