PHP implements 6 sorting algorithms

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 respectively. , 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 code

<?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 one with all the following ones, find the smallest number, and then exchange it with the first array (of course, if it is the first smallest, 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 swap it with the second number, and so on, that is to say, find the smallest number every time Find the smallest remaining value. 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 code

<?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;   
         }  
?>

Three, bubble sort

Bubble sort is actually compared with selection sort, and No significant 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.
php implementation code is as follows:

Php code

<?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 language, select a value $a from the array, and then compare it with the rest of the elements, whichever is larger than $a Put it into the array right, otherwise, put it into 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 code

<?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 order cannot be confirmed, and the order of the entire array cannot be confirmed. The merger still needs to be completed through the final left and right comparison. Sorting in the truest sense.

Php code

<?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