Six commonly used sorting algorithms in php

First, insertion sort
Use simple words to describe, for example, $arr = array(4,2,4,6,3,6,1,7,9); Such a set of numbers is sorted sequentially:
Then, First, compare the second element of the array with the first element. If the first element is greater than the second element, then swap the positions of the two. Next, take the third element of the array and compare it with the second element. , compare the first element, and if the third element is smaller, swap it. And so on. This is insertion sort, and its time frequency is: 1+2+...+(n-1)=(n^2)/2. Then its time complexity is O(n^2).
php implementation code is as follows:

<?php
        function insertSort($arr){
              $count = count($arr);
              if($count<2){
                  return $arr; 
              }
              for($i=1;$i<$count;$i++){
                    $tmp = $arr[$i];
                     $j=$i-1;
                     while(j>=0&&$arr[$j]<$arr[$i]){
                         $arr[$i] = $arr[$j];                      
                         $arr[$j] = $tmp;
                         $j--;
                     }
               }
               return $arr; 
         }
?>

Second, selection sorting

If selection sorting is described in language, it can be like this, such as: $arr = array(4,3, 5,2,1);
First, compare the first and all following numbers to find the smallest number, and then swap it with the first array (of course, if it is the first smallest number, then there is no need to swap ), and then loop, that is: compare the second number with the following number, find the smallest number, and then exchange it with the second number, and so on, that is to say, find the smallest remaining value each time. It can be obtained: the first time, the time frequency is n, (the first one is compared with the following n-1, find the smallest one, and then check whether it is the first one, if not, exchange it) in the future , followed by minus one. Its time complexity is also O(n^2);

php implementation code is as follows:

<?php
        function selectSort($arr){
              $count = count($arr);
              if($count<2){
                  return $arr; 
              }
              for($i=0;$i<$count;$i++){
                     $min=$i;
                     for(j=$i+1;$j<$count;$j++){
                         if($arr[$min]>$arr[$j]){
                              $min = $j; //找到最小的那个元素的下标
                         }
                     }
                     if($min!=$i){//如果下标不是$i 则互换。
                            $tmp= $arr[$i];                      
                             $arr[$i] = $arr[$min];
                             $arr[$min] = $tmp;
                       }
               }
               return $arr; 
         }
?>

3. Bubble sorting
In fact, compared with selection sorting, bubble sorting has no obvious difference. Find the smallest one and put it on the far left. Solve the problems in sequence. The difference is that bubble sorting swaps positions more times, while selection sorting finds the subscript of the smallest element and then directly swaps positions with the leftmost element.
The PHP implementation code is as follows:

<?php
        function selectSort($arr){
              $count = count($arr);
              if($count<2){
                  return $arr; 
              }
              for($i=0;$i<$count;$i++){
                     for(j=$i+1;$j<$count;$j++){
                         if($arr[$i]>$arr[$j]){
                              $tmp= $arr[$i];                      
                             $arr[$i] = $arr[$i];
                             $arr[$i] = $tmp;
                         }
                     }
               }
               return $arr; 
         }
?>

Four, quick sort
Quick sort, to describe it in words, select a value $a from the array, and then compare it with the other elements, and put the one larger than $a into the array right. Otherwise, put it in the array left. Then recursively call left and right respectively, that is, subdivide left and right, and finally merge the arrays.
php implements quick sorting:

<?php
        function mySort($arr){
              $count = count($arr);
              if($count<2){
                  return $arr; 
              }
              $key = $arr[0];//选择第一个元素作为比较元素，可选其他
               $left = array();              
               $right = array();
               for($i=1;$i<$count;$i++){
                     if($key>=$arr[$i]){
                         $left[] = $arr[$i];  
                     }else{
                          $right[] = $arr[$i];
                      }
               }
               $left = mySort($left);
               $right = mySort($right);
               $result = array_merge($left,$right);
               return $result; 
         }
?>

5. Merge sort
In fact, merge sort is an idea of ​​splitting and merging. It has something in common with the idea of ​​quick sort, one pile on the left, one pile on the right, and then merged. Sorting is achieved through recursion. What's the difference? The difference between them is also an essential difference in thinking. The split of quick sort selects specific values ​​for size comparison, thus dividing them into left and right. That is, the small pile is placed on the left, and the large pile is placed on the right. Then, the small left is subdivided into left1 and right1. . . . Sorting is done by doing a similar recursion. In other words, if you keep subdividing it, left1 at the end of the recursion is the minimum value.

And merge sorting is to recursively divide the arrays from the left and right geometrically into the minimum granularity of 2 or 1, and then start to compare the sizes, and then merge. The comparison size here is: the son's left element is compared with the son's right element, and then sorted and merged into the father's left or right. Here, until the last two arrays are sorted and merged respectively: the initial left and right, only their respective orders cannot be confirmed, and the order of the entire array cannot be confirmed. The merger still needs to be completed through the final comparison of left and right. Sorting in the truest sense.

<?php
function gbSort($arr){
       if(count($arr)<=1){return $arr;}
       $min = floor(count($arr)/2);//取中间数字进行拆分
       $left = array_slice($arr,0,$min);
       $right = array_slice($arr,$min);
       $left = gbSort($left);  //递归
       $right = gbSort($right);
       return get_merge($left,$right);//调用排序合并函数进行合并
}
function get_merge($left,$right){
        while(count($left) && count($right)){
               $m[] = $left[0]>$right[0] ? array_shift($right) : array_shift($left);
               //进行比较，小的移除，并且放入到数组$m中。
        }
        return arr_merge($m,$left,$right);//进行合并（由于不知道left right 哪个会为空，所以进行统一合并）
}
?>

Six, heap sort
To be continued