This article describes the implementation method of Bubble Sort of PHP sorting algorithm. Share it for your reference, as follows:
Basic idea:
Bubble sorting is a kind of exchange sorting. Its basic idea is to compare the keywords of adjacent records in pairs, and if inverted, exchange them until there are no inverted records.
The simplest sorting implementation:
Let's first look at the sorting methods that are often used before learning various sorting methods (at least I am...):
//The type hint array is used here. Students who are not familiar with or are not used to it can remove it, so it will not affect the calculation results.function MySort(array &$arr){
$length = count($arr);
for($i = 0;$i < $length - 1;$i ++){
for($j = $i + 1;$j < $length;$j ++){
//Put the small keyword in front if($arr[$i] > $arr[$j]){
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);
Strictly speaking, the above code is not a standard bubble sorting, because it does not meet the bubble sorting idea of "compare adjacent records in pairs". It is just a simple exchange sorting. The idea is nothing more than: start with the first keyword, compare each keyword with all the keywords after it, and exchange it to get the minimum value. But this algorithm is very inefficient.
Bubble sorting algorithm:
It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are incorrect. The work of visiting the sequence is repeated until no exchange is needed, that is, the sequence has been sorted.
The origin of this algorithm is that the larger the element in the array will gradually "sink" to the back of the array after sorting again and again, while the smaller the element will gradually "float" to the front of the array, hence the name.
The bubble sorting algorithm works as follows: (From the back to the front)
1. Compare adjacent elements. If the first one is bigger than the second one, exchange them for the two.
2. Do the same work for each pair of adjacent elements, from the beginning of the first pair to the end of the last pair. At this point, the last element should be the largest number.
3. Repeat the above steps for all elements except the last one.
4. Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers that need to be compared.
You may not be able to understand the text description, just read the code:
//Exchange methodfunction swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//Bubbling sortfunction BubbleSort(array &$arr){
$length = count($arr);
for($i = 0;$i < $length - 1;$i ++){
//Floating small elements from behind to front layer by layer for($j = $length - 2;$j >= $i;$j --){
//Compare adjacent records in pairs if($arr[$j] > $arr[$j + 1]){
swap($arr,$j,$j+1);
}
}
}
}
Improvements to bubble sorting algorithm:
《Big Talk Data Structure》It is indeed a good book, and it also introduced us to the improvement of the bubble sorting algorithm. Here I will directly introduce its statement:
Can the above bubble sorting algorithm be optimized? The answer is yes. Just imagine, if the sequence we are to sort is {2,1,3,4,5,6,7,8,9}, that is, except for the first and second keywords that need to be exchanged, everything else is already in normal order. When i = 0, 2 and 1 are exchanged, and the sequence is already ordered, but the algorithm still unyieldingly executes i = 2 to 9 and the j loop in each loop. Although the data is not exchanged, the subsequent large amount of comparisons are still very redundant.
When i = 2, we have compared 9 with 8, 8 with 7, ········································································································································································································································································································································································································································································································· To implement this idea, we need to improve the code and add a flag variable to achieve the improvement of this algorithm:
//Exchange methodfunction swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
/Optimization of bubble sorting(If no element exchange occurs during a loop，Then the entire array is already ordered)
function BubbleSort1(array &$arr){
$length = count($arr);
$flag = TRUE;
for($i = 0;($i < $length - 1) && $flag;$i ++){
$flag = FALSE;
for($j = $length - 2;$j >= $i;$j --){
if($arr[$j] > $arr[$j + 1]){
swap($arr,$j,$j+1);
$flag = TRUE;
}
}
}
}
The key to code changes is to add a judgment on whether the flag is true in the for loop of the i variable. After such improvements, bubble sorting has improved performance, which can avoid meaningless loop judgments in the case of already order.
The total time complexity of the bubble algorithm isO(n^2)。
Bubble sort is a stable sort.
This article is referenced from "Big Talk Data Structure》, only records are made here for easy review in the future, please do not criticize me!
PS: Here is a demonstration tool about sorting for your reference:
Online animation demonstration insert/select/bubble/merge/hill/quick sorting algorithm process tool:
http://tools./aideddesign/paixu_ys
For more information about PHP related content, please check out the topic of this site:Summary of php sorting algorithm》、《PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Summary of usage of php strings》、《Complete collection of PHP array (Array) operation techniques》、《Summary of common traversal algorithms and techniques for PHP"and"Summary of PHP mathematical operation skills》
I hope this article will be helpful to everyone's PHP programming.