PHP Bubble Algorithm Detailed Explanation (Recursive Implementation)
- 2021-07-26 07:09:44
- OfStack
Realization
/*
Bubbling algorithm ( Recursive implementation )
*/
function maoPao($array, $index=0)
{
$count = count($array);
if(($count-1) <= $index)
return $array;
for($i=$count-1; $i>$index; $i-- )
{
if($array[$i] < $array[$i-1])
{
$tmp = $array[$i];
$array[$i] = $array[$i-1];
$array[$i-1] = $tmp;
}
}
$index++;
return maoPao($array, $index);
//return maoPao($array, $index++);
}
$arr = array(12,4,3,1,9,5,6,8,7);
var_dump(maoPao($arr));
Results:
Array ( [0] => 1 [1] => 3 [2] => 4 [3] => 5 [4] => 6 [5] => 7 [6] => 8 [7] => 9 [8] => 12 )
Question:
I encountered a problem when trying this implementation, which has not been solved yet.
Here:
$index++;
return maoPao($array, $index);
//return maoPao($array, $index++);
/******************
If you use the 3 OK, not first $index++ , again ruturn You will enter an infinite loop . I output at the beginning of the function $index, It's all 0 That is to say $index++ The argument passed to the recursive function after the $index++ The expected result ( I.e. $index=$index+1).
maoPao($array, $index++) No $index++; return maoPao($array, $index); The short writing of, why don't the two results 1 I hope to get your answers.
******************/
Additional:
Answer:
$index++ And ++$index The difference between the two, $index++ Known as post-increment, ++$index Known as pre-increment, Although the last $index The result is that +1 . But when passing variables, there will be no 1 What kind of place.
$index = 1;
$m = $index++;
echo $index.'<br/>'; // The result is 2
echo $m.'<br/>'; // The result is 1. Because it is a post-increment, Will first put the initial $index=1 Assign $m, And then $index Self-increasing 1;
$index = 1;
$n = ++$index;
echo $index.'<br/>'; // The result is 2
echo $n; // The result is 2. Because it is a pre-increment, Will be executed first $index+1 Operation of, Re-assign a value to $n;
This may not be easy to remember, so be careful when using 1. I just ignored this problem in the above problem, which caused $index to pass a value of 0 indefinitely and cause recursive locking.