Of Stack

Summary of Common Sorting Algorithms Implemented by php

  • 2021-07-18 07:19:33
  • OfStack

This paper summarizes the common php sorting algorithm, which has good reference value when designing the algorithm. Now I share it with you for reference. The details are as follows:

1. Insert sort

Describe it simply in words, such as $arr = array (4, 2, 4, 6, 3, 6, 1, 7, 9); Sort such a set of numbers in sequence:
Then, first, compare the second element of the array with the first element. If the first element is larger than the second element, let the two positions be interchanged. Next, compare the third element of the array with the second and first elements respectively. If the third element is smaller, then interchange. And so on. This is the insertion sort, and its time frequency is: 1 +2 +... + (n-1) = (n ^ 2)/2. Its time complexity is O (n ^ 2).

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

STEP 2 Select a sort

If the sorting is described in language, it can be as follows: $arr = array (4, 3, 5, 2, 1);

First, compare the first and all the following numbers to find the smallest number, then interchange with the first array (of course, if the first is the smallest, then there is no interchange), and then loop, that is, compare the second and the following numbers to find the smallest number, then interchange with the second number, and so on, that is to say, find the smallest remaining value every time. It can be obtained that: for the first time, the time frequency is n, (compare the first one with the following n-1, find the smallest one, and then see if it is the first one, if it is not the first one, exchange it), and then it is minus 1 in turn. Its time complexity is also O (n ^ 2);

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++){
   $min=$i;
   for(j=$i+1;$j<$count;$j++){
  if($arr[$min]>$arr[$j]){
    $min = $j; // Find the subscript of the smallest element 
  }
   }
   if($min!=$i){// If the subscript is not $i  Is interchanged. 
   $tmp= $arr[$i];           
    $arr[$i] = $arr[$min];
    $arr[$min] = $tmp;
    }
    }
    return $arr; 
 }
?>

3. Bubble sort

Bubble sorting is actually compared with selective sorting, and there is no obvious difference. Find the smallest one and put it at the leftmost end. Solve the problem in turn. The difference is that the bubble sort swaps the position more often, while the select sort finds the subscript of the smallest element and then swaps the position directly with the leftmost one.


The implementation code of php 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; 
 }
?>

4. Quick sort

Quick sort, using language to describe the words, from the array to select a value of $a, and then compare with the rest of the elements, than $a into the array right, otherwise, into the array left. Then, left right is called recursively, that is, left right is subdivided, and finally, arrays are merged.

php implements quick sorting: 


<?php
function mySort($arr){

   $count = count($arr);
   if($count<2){
  return $arr; 
   }
   $key = $arr[0];// Select 1 Elements are used as comparison elements, and other elements are optional 
    $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 and sort

In fact, merging and sorting is an idea of splitting and merging. It has something in common with the idea of quick sorting, one pile on the left, one pile on the right, and then merge. Sort by recursion. What's the difference? The difference between them is also the essential difference in thought. The split of quick sorting is to select specific values for size comparison, thus dividing them into left and right. That is, the small ones are stacked in left and the large ones are stacked in right. Then, the small left is subdivided into left1 right1. . . . Sorting is accomplished by similar recursion. That is to say, if 1 is subdivided straight, left1 at the end of recursion is the minimum value.

Merge sorting is from the geometric left and right segmentation, 1 straight recursive segmentation into 2 or 1 of the smallest granularity array, and then start to compare the sizes, and then merge. The comparison size here is: the element of son left is compared with the element of son right, and then sorted and merged into father left or right. Here, the last two arrays are merged until they get their respective sorts: the initial left and right, and only until their respective orders, the order of the whole array cannot be confirmed, or the final left right comparison is needed to merge before the real sorting can be completed. 


<?php
function gbSort($arr){
    if(count($arr)<=1){return $arr;}
    $min = floor(count($arr)/2);// Take the middle number for splitting 
    $left = array_slice($arr,0,$min);
    $right = array_slice($arr,$min);
    $left = gbSort($left); // Recursion 
    $right = gbSort($right);
    return get_merge($left,$right);// Call the sort merge function to merge 
}
function get_merge($left,$right){
    while(count($left) && count($right)){
        $m[] = $left[0]>$right[0] ? array_shift($right) : array_shift($left);
        // Compare, remove small ones, and put them into an array $m Medium. 
    }
    return arr_merge($m,$left,$right);// Merge (because you don't know left right  Which one will be empty, so it will be unified 1 Merge) 
}

?>

6. Heap sorting

In this example, the fixDown function realizes the downward adjustment of a certain node, and the default is that the starting node is 1, which is convenient for calculating the parent-child node relationship

Note:

Parent-child relationship with starting node 1: parent node k, child node 2K, 2k +1 child node j, parent node floor (j/2) floor is rounded down
Parent-child relationship with starting node 0: parent node k, child node 2K +1, 2k +2 child node j, parent node floor ((j-1)/2)

The parameter $k is the adjustment point position, and $lenth is the length of the array, that is, the coordinates from 1 to the last node. 


<?php
function fixDown(&$arr, $k, $lenth)
{
 　　 while(2*$k<=$lenth) { // As long as the current node has children,   You need to continue the loop 
    $j = $k*2;
    if ($j<$lenth && $arr[$j]<$arr[$j+1]) $j++;  //  As long as the child node has a right node and the right node is larger than the left node, switch to the right node operation. 
    if ($arr[$j] < $arr[$k]) break; //  If the child nodes are not as large as the parent node,   Then the adjustment is over. 
    exch($arr[$j], $arr[$k]);
  　　 　   $k = $j;
  }
}

function exch(&$a, &$b) {
  $tmp = $a; $a = $b; $b = $tmp;
}

function headSort(&$arr)
{
  $len = count($arr);
  array_unshift($arr, NULL);
  for($i=$len/2;$i>=1;$i--) {
    fixDown($arr, $i, $len);
  }
  while($len>1) {
    exch($arr[1], $arr[$len]);
    fixDown($arr, 1, --$len);
  }
  array_shift($arr);
}
$arr = array(4,6,4,9,2,3);
headSort($arr);
?>

I hope the example of sorting algorithm described in this paper is helpful to everyone's php program design.

Related articles: