Detailed explanation of using PHP bubble sort

This time I will bring you PHPBubble sortdetailed explanation of use, what are the notes when using PHP bubble sort, the following is a practical case, let's take a look.

Basic idea:

Bubble sorting is a kind of exchange sorting. Its basic idea is: the key to comparing adjacent records pairwise Words, if reversed, are exchanged until there are no records in reversed order.

The simplest sorting implementation:

Let’s first take a look at the sorting methods that are often used before learning various sorting methods (at least for me That's it...):

//这里使用了类型提示（type hint） array，不熟悉或者不习惯的同学大可去掉，不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      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 sort, because it does not satisfy the bubble sort idea of ​​"pairwise comparison of adjacent records" , it is just a simple exchange sort. The idea is just that: starting from the first keyword, compare each keyword with all the keywords that follow it, and exchange them to get the minimum value. But this algorithm is very inefficient.

Bubble sort algorithm:

It repeatedly visits the sequence to be sorted, comparing two elements at a time, and if they are in the wrong order Just exchange them. The work of visiting the array is repeated until no more exchanges are needed, which means that the array has been sorted.

The name of this algorithm comes from the fact that larger elements in the array will gradually "sink" to the back of the array after sorting, while smaller elements will gradually "float" to the front of the array, hence the name .

The bubble sort algorithm operates as follows: (from back to front)

1. Compare adjacent elements. If the first one is bigger than the second one, swap them both.
2. Do the same work for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. 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 to compare.

You may not be able to understand it if you read the text description, but look at the code:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

Bubble sorting algorithm improvement:

Can the above bubble sort algorithm still be optimized? The answer is yes. Just imagine, if the sequence we want to sort is {2,1,3,4,5,6,7,8,9}, that is to say, except for the first and second keywords, everything else needs to be exchanged. It's already the normal order. When i = 0, 2 and 1 are exchanged, and the sequence at this time is already in order, but the algorithm still executes i = 2 to 9 and the j loop in each loop, although No data was exchanged, but the extensive comparisons that followed were largely redundant.
When i = 2, we have compared 9 and 8, 8 and 7, ·······, 3 and 2 without any data exchange, which means that this sequence is already in order. It is necessary to continue the subsequent judgment work (no data exchange will occur in the subsequent work, and it is meaningless to do it again). In order to realize this idea, we need to improve the code and add a mark variable flag to realize the improvement of this algorithm:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换，则整个数组已经是有序的了)
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 the code change is the for loop## of the i variable In #, the judgment of whether the flag is true is added. After such improvement, the performance of bubble sorting has been improved, and the meaningless loop judgment can be avoided when the order is already in order.

The total time complexity of the bubble algorithm is

O(n^2).

Bubble sorting is a stable sorting.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

PHP Hill Sorting Case Analysis

PHP Heap Sorting Algorithm Example Analysis

The above is the detailed content of Detailed explanation of using PHP bubble sort. For more information, please follow other related articles on the PHP Chinese website!