PHP sorting algorithm Bubble Sort (Bubble Sort)

This article mainly introduces the implementation method of Bubble Sort of PHP sorting algorithm. It refers to the algorithm in Dahua data structure and analyzes the principle and related implementation techniques of Bubble Sort in detail in the form of examples. It needs Friends can refer to the following

This article describes the implementation method of Bubble Sort (Bubble Sort) of PHP sorting algorithm through examples. Share it with everyone for your reference, the details are as follows:

Basic idea:

Bubble sorting is a kind of exchange sorting, its basic idea Yes: Compare the keywords of adjacent records pairwise, and exchange them if they are in reverse order, until there are no records in reverse 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 sorting idea of ​​"compare adjacent records pairwise", it is just a simple exchange sorting. 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 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);
      }
    }
  }
}

Improvement of Bubble Sort Algorithm:

"Dahua Data Structure" is indeed a good book. It also introduces us to the improvement of Bubble Sort algorithm. Here I will directly quote its statement:

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 flag 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 to add a judgment on whether the flag is true in the for loop of the i variable. After such improvements, the performance of bubble sorting has been improved, which can avoid the situation that is already in order. The judgment of a meaningless cycle.

The total time complexity of the bubble algorithm is

O(n^2).

Bubble sorting is a stable sorting.

This article is referenced from "Dahua Data Structure". It is only recorded here for future reference. Please don't criticize!

Related recommendations:

PHP sorting algorithm Simple Selection Sort (Simple Selection Sort)

PHP sorting algorithm Direct Insertion Sort ( Straight Insertion Sort)

PHP sorting algorithm Hill Sort (Shell Sort)

The above is the detailed content of PHP sorting algorithm Bubble Sort (Bubble Sort). For more information, please follow other related articles on the PHP Chinese website!