Suppose that 10 Quick sort by number ：
61279345108
Let's first simulate the Quicksort process ： first , Take any number in the sequence as the base number , Usually for convenience , Take the first number as the base number .
61279345108
In the initial state , number 6 At the end of the sequence 1 position . Our goal is to 6 Move to a position in the middle of the sequence , Let's say this location is k k k. Now we need to find this k k k
, And in the second place k Bit is the dividing point , The number on the left is all right ≤ 6 \le6 ≤6, The number on the right is all right ≥ 6 \ge6 ≥6. So how do you find this position k k k What about it ?
We need to know , Quick sort is actually an improvement of bubble sort , Bubble sort compares two adjacent numbers at a time , This is obviously a waste of time .
Quicksort starts at both ends ” probe ” Of , First, find a smaller one from right to left 6 The number of , From left to right, find a greater than 6 The number of , And then exchange them . Two variables can be used here i i i and j j j
, Point to the left most and right most of the sequence respectively . We have a nice name for these two variables “ sentry i i i” and “ sentry j j j”. In the beginning, let the sentry i i i
Points to the far left of the sequence , Point to a number 6. Let the sentry j j j Points to the far right of the sequence , Point to a number 8.
61279345108
ij
First of all, sentry j j j We're on the move . Because the base number set here is the leftmost number , So we need to get the sentries j j j Let's go first , This is very important . sentry j j j Step by step to the left （ Namely j
= j − 1 j = j-1j=j−1）, Until you find one less than 6 Stop counting . Next, sentry i i i Move to the right step by step （ Namely i = i + 1 i=i+1 i=i+
1）, Until a number greater than 6 Stop counting . Last sentry j j j Stop at the number 5 before , sentry i i i Stop at the number 7 before .
61279345108
ij Now exchange sentries $i$ And the sentry $j$ The value of the element pointed to . The sequence after the exchange is as follows .
61259347108
ij
That's it , The first exchange is over . Next, the sentry j j j Keep moving to the left （ Another friendly reminder , Every time it has to be a sentry j Let's go first ）. He found out 4 < 6 4<6 4<6, Stop . sentry i i
i And continue to move to the right , He found out 9 > 6 9>6 9>6, Stop . At this point, exchange again , The sequence after the exchange is as follows .
61254397108
ij
The second exchange is over . sentry j j j Keep moving to the left , He found out 3 < 6 3<6 3<6, Stop again . sentry i i i Continue to move to the right , At this time, the sentry i i i And the sentry j j
j We met , sentry i i i And the sentry j j j It's all here 3 before . Explain this time “ probe ” end . We will set the benchmark number 6 and 3 Exchange . The sequence after the exchange is as follows .
31254697108
i,j
This is the first round “ probe ” It's really over . Current benchmark 6 It's back in place , In this case, the benchmark number is used 6 It is the dividing point ,6 The numbers on the left are less than or equal to 6,6 The numbers on the right are greater than or equal to 6. Let's review the process , In fact, the sentry j j
j Our mission is to find the number less than the benchmark , And the sentry i i i Our mission is to find numbers larger than the benchmark , until i i i and j j j Until we meet .
Now we will take the first round “ probe " Sequence after completion , with 6 Split the boundary point into two sequences , The sequence on the left is “3 1 2 5 4”, The sequence on the right is “9 7 10
8”. Next, we need to process these two sequences separately . because 6 The sequences on the left and right are still chaotic . But it doesn't matter , We've got the method , Next, we just need to simulate the method mentioned above 6 The left and right sequences are OK . Now let's deal with it first 6 Let's see the sequence on the left .
312546
Repeat the first round , We should get the following sequence ：
213546
OK, Now? 3 It's back in place . Next, we need to deal with it 3 Sequence on the left ：
213 6
After treatment ,2 It's back in place , sequence “1” There's only one number , And it doesn't need any treatment , therefore “1” Return to the original position .
123 6
For the sequence to the right of the cardinality , Use the same procedure as on the left ; We'll end up with this sequence , as follows .
12345678910
Careful students may have found out , In fact, each round of quick sort is to return the benchmark number of this round , Until all the numbers are in place , The sorting is over . Next, use the graphical method to show the complete process ：
Quick sort is faster , Because compared with bubble sort , Every time you switch, you jump , Set a benchmark for each sort , Place all the numbers less than or equal to the base point to the left of the base point , Put all the numbers greater than or equal to the datum point to the right of the datum point . In this way, each exchange will not be the same as bubble sorting, and can only exchange between adjacent numbers each time , The exchange distance is much larger . So the total number of comparisons and exchanges is less , The speed naturally increased . In the worst case, of course , It is still possible that two adjacent numbers are exchanged . So the worst time complexity of quick sort is the same as bubble sort
O ( n 2 ) O(n^2)O(n2), Its average time complexity is O ( n log 2 n ) O(n\log_2n) O(nlog2n).
The code for quick sort is as follows ：
void Quick_Sort(int *arr, int begin, int end){ if(begin > end) return; int tmp
= arr[begin]; int i = begin; int j = end; while(i != j){ while(arr[j] >= tmp &&
j> i) j--; while(arr[i] <= tmp && j > i) i++; if(j > i){ int t = arr[i]; arr[i]
= arr[j]; arr[j] = t; } } arr[begin] = arr[i]; arr[i] = tmp; Quick_Sort(arr,
begin, i-1); Quick_Sort(arr, i+1, end); }
Technology