A brief discussion on the second part of PHP---the application of classic algorithms (bubble sort and quick sort)_PHP Tutorial

First of all, let’s talk about the idea of ​​bubble sorting. Then many students will ask what is bubble sorting method?

Let me explain below:

The so-called bubble sorting method is to compare two adjacent numbers in sequence, placing the decimal in the front and the large number in the back. That is, in the first pass: first compare the first and second numbers, put the decimal first and the large number last. Then compare the second number and the third number, put the decimal in front and the large number in the back, and continue like this until comparing the last two numbers, put the decimal in front and the large number in the back. This is the end of the first trip, leaving the largest number at the end. In the second pass: still start the comparison from the first pair of numbers (because it may be due to the exchange of the second number and the third number that the first number is no longer smaller than the second number), put the decimal first, and the large number After placing it, the comparison is continued until the second to last number (the first to last position is already the largest). At the end of the second pass, a new maximum number is obtained at the second to last position (in fact, it is the largest number in the entire sequence). The second largest number). Continue like this and repeat the above process until the sorting is finally completed.

Let’s take a look at an example:
There is an array array(23,34,12,56,43,98,89). Let’s use bubble sorting to sort its elements.
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

In the above example, the for loop inside compares all the elements in the array in turn, that is, comparing the first element in the array with the second element, and the second element in the array. Compared to the third element,
And so on, until the penultimate element of the array is compared with the last element, if the previous element is greater than the later element, swap the positions of the previous element with the later element,
Then we think, how to exchange the positions of the two elements in the array,
We can use an intermediate container variable to solve this problem,
That is, put the value of the first variable that needs to be exchanged into the container variable, then assign the value of the second variable that needs to be exchanged to the first variable, and then assign the value in the container variable to the second variable. .

In order to give everyone a deeper understanding, please look at the simulation diagram below:

Step 1: Declare an intermediate container variable $tmp:

Step 2: Assign the value of $arr[$j] to $tmp

Step 3: Assign $arr[$j+1] to $arr[$j]

Step 4: Assign the value of the intermediate variable to $arr[$j+1] to complete the exchange

And so on, until the comparison between the penultimate element and the last element of the array is completed. A total of count($arr)-1 comparisons
At this point, the first sorting of our array has been completed. At this time, the largest number in the array has been placed at the end of the array. In other words, the inner for loop has been executed. www.2cto.com
Next we need to perform the second and third passes... sorting, one pass at a time, and put the largest number at the end of the array. As long as the sorting is completed, there will be a total of count ($arr) times.
Having said this, do you understand the meaning of the outer for loop!
Okay, let’s think about a problem. If the elements in the array are compared in pairs, the maximum number will be discharged for each comparison,
So in the next comparison, should we not perform the comparison with the maximum number queued in the previous time?
In other words, after the first sorting, 98 has been placed at the end of the array. There is no need to compare 98 in the next sorting. This will improve efficiency and save resources,
Therefore we can write:
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($j==count($arr)-1){
continue;
}
if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

In the above code, the number of executions of the inner loop becomes count($arr)-$i,
That is to say, after comparing all the elements in the array in each pass, the next time the sort is performed, the number of sorting will be reduced by one,
That is to say, the comparison of the largest number obtained in the previous comparison is excluded. In this way, the efficiency will be improved a lot,
We can use PHP's built-in function microtime() to execute it once before sorting and once after sorting, and subtract the two times to get the operation time,
Through comparison, it can be concluded that the efficiency of the second sorting method of bubble sorting is higher than that of the first sorting method, but it is not obvious. You can verify it here, so I won’t go into details here.

Next we use quick sort to sort the above array:
$arr = Array(23,34,12,56,43,98,89);
function quick($arr){
$left = array();
$right = array();
if(count($arr)<=1){
return $arr;
}
for($i=1;$i if($arr[0]>$arr[$i]){
$left[] = $arr[$i];
}else{
$right[] = $arr[$i];
}
}
$left = quick($left);
$right = quick($right);
return array_merge($left,array($arr[0]),$right);
}
?>

The so-called quick sorting is to pick any value in the $arr array as the intermediate value, and then compare this value with all other elements in the array. Smaller than this value is placed on the left, and larger than this value is placed on the left of this value. On the right, a sorting is completed at this time. By analogy, the numbers to the left of this value are sorted as above, and the numbers on the right are also sorted as above until all values ​​are compared.

Let’s look at the above code:
First of all, to use the concept of quick sort, you need to use recursion. When it comes to recursion, it is the idea of ​​using a function to call itself, going deeper layer by layer, and finally returning the value obtained.
Let’s take a look. First, we need to customize a function quick() and let this function call itself.
Here we use $arr[0] for the intermediate value. This is chosen arbitrarily and is not required.
In order to make everyone think clearly, we first define two empty arrays, which are equivalent to two cups,
Let $arr[0] be compared with all the values ​​in the array. Values ​​smaller than $arr[0] are placed in the first cup, and values ​​larger than $arr[0] are placed in the second cup. In the program are $left and $right respectively,
We judge that if the given array element has only one element or is empty, the array will be returned by the quick function and the following content will not be executed,
Next, we traverse the array and compare the traversed values ​​with $arr[0]. Values ​​smaller than $arr[0] are stored in the $left array, and values ​​larger than $arr[0] are stored in the $left array. $right array, a sorting is completed at this time,
Next, perform the same operation on the $left array and $right array, that is, call the function itself and pass in the $left array and $right array until the array element of the $left array or $right array is one. Call yourself and return directly,
Finally, merge the left array, $arr[0], and $right array to get the final sorting result.

Correction:
Correct the efficiency problem. When testing the efficiency, an error occurred, which caused the efficiency test to be inaccurate. After being reminded by classmates, we tested again and again, and finally found that the operational efficiency of quick sort when sorting this array is the same as the efficiency of bubble sort. The two are almost the same, but the first one that bubbles is still significantly higher than the second one. This test result can only be used as a reference. To accurately calculate the efficiency of each algorithm, it is necessary to count the number of sorting times within the algorithm. .
Thank you again for your attention and correction of this problem. This is an open platform. Please speak freely, communicate more, and make progress together...



Excerpted from zdrjlamp

http://www.bkjia.com/PHPjc/478287.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/478287.htmlTechArticleFirst of all, let’s talk about the idea of ​​bubble sorting. Then many students will ask what is bubble sorting method? Next I will Let’s explain: The so-called bubble sorting method is to compare two adjacent numbers in sequence and put the decimal...