JIYIK CN >

Bubble sort is also a simple and intuitive sorting algorithm. The idea is that it repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to swap, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through swapping.

Let's take a look at this bubbling process through a simple diagram.

The starting position is 0, and the two adjacent elements are compared in sequence. If the previous element is greater than the next element, they are swapped.

We can see that the number of bubbling passes is equal to the number of elements in the sequence to be sorted. However, in practice, we can reduce the number of bubbling passes according to the actual situation.

Take the above example, we can see that the sequence is already ordered after the fourth bubbling process. The fifth and sixth bubbling processes did not produce any element swaps. So we can judge that if no element swaps are produced in a bubbling process, we terminate the entire bubbling process. In this way, the final sequence is also ordered.

The reaction in the program is to set a flag at the beginning of each bubbling, which defaults to false. When an exchange occurs, the flag is set to true. After the bubbling process ends, we use this flag to determine whether an exchange occurs. If no exchange occurs, we end the entire bubbling process directly. Otherwise, continue to the next bubbling process.

According to the above picture, let's look at the steps to implement the text of bubble sort

1) Compare adjacent elements. If the first is greater than the second, swap them.
2) Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. When this is done, the last element will be the largest number.
3) Repeat the above steps for all elements except the last one.
4) Keep repeating the above steps for fewer and fewer elements each time, until there are no pairs of numbers left to compare.

Finally, we need to convert the text steps into code implementation

/**
 * 交换函数
 */
function swap(&$arr,$a,$b){
    $t = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $t;
}
function BubbleSort(&$arr){
    $end = count($arr)-1;
    while($end>0){
        for($i=0;$i<$end;$i++){
            if($arr[$i]>$arr[$i+1]){
                swap($arr,$i,$i+1);
            }
        }
        $end--;
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
BubbleSort($arr);
print_r($arr);

The above code goes through all the bubbling processes. Next, we only need to make a simple modification to the BubbleSort function to implement the flag we mentioned above to determine whether an exchange occurs.

function BubbleSort(&$arr){
    $end = count($arr)-1;
    while($end>0){
        $flag = false;  //每次冒泡前 初始化标志位为false
        for($i=0;$i<$end;$i++){
            if($arr[$i]>$arr[$i+1]){
                swap($arr,$i,$i+1);
                $flag = true;  //有交换产生 将标志位置为true
            }
        }
        if(!$flag) break;  //如果没有交换产生 则直接跳出循环
        $end--;
    }
}

In fact, there is no obvious difference between programs with and without flags when the amount of data is small, and the time taken should not be much different. But when the amount of data is large, the difference becomes very obvious. But then again, bubble sort is not the best sorting algorithm. Its efficiency is lower than other sorting algorithms, and its time complexity is O(n²). So in actual situations, if the amount of data is large, we may not necessarily choose bubble sort to implement sorting.

But I personally think that bubble sort and selection sort can be said to be the basis of other sorts, so it is necessary for us to understand bubble sort.

I hope this article is helpful to you.