Analysis of PHP Quick Sorting Principle and Implementation Method

This article describes the php quick sorting method. Share it for your reference, as follows:

<?php
$n = array('13','14','55','10','54','2','79','106','89','90','22','60','111','77777','-110','-10','123');
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

Quick sorting is an improvement to bubble sorting. Its basic idea is: by sorting it in a lying order, the data to be sorted into two independent parts, all the data in part is smaller than all the data in another part, and then the two parts of the data are quickly sorted according to the method. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

Suppose the array to be sorted is A[1]...A[N], first select one data (usually the first data) as the key data, and then put all the numbers smaller than it in front of it, and all the numbers larger than it in the back of it. This process is called quick sorting. The algorithm for quick sorting is:

1) Set two variables I and J, when the sorting starts I: =1, J: =N;
2) Use the first array element as the key data and assign it to X, that is, X:=A[1];
3) Start searching forward from J, that is, start searching forward from behind (J: = J-1), find the first value smaller than X, and exchange the two;
4) Start from I and search backward, that is, start from front to backward (I: = I+1), find the first value greater than X, and exchange the two;
5) Repeat steps 3 and 4 until I=J;

Quick sorting is to call this process recursively - split the data sequence with 49 as the midpoint, and perform similar quick sorting of the previous and subsequent parts respectively, so as to complete the quick sorting of all data sequences, and finally turn this data sequence into an ordered sequence.

Replenish:Here, the editor recommends a php formatting and beautification typeface tool on this site to help everyone type in code in future PHP programming:

PHP code online formatting and beautification tool:

http://tools./code/phpformat

In addition, since php belongs to the C language style, the following tool can also implement the formatting of php code:

C language style/HTML/CSS/json code formatting and beautification tools:
http://tools./code/ccode_html_css_json

For more information about PHP related content, please check out the topic of this site:Complete collection of PHP array (Array) operation techniques》、《Summary of php sorting algorithm》、《Summary of common traversal algorithms and techniques for PHP》、《PHP data structure and algorithm tutorial》、《Summary of PHP Programming Algorithm》、《Summary of PHP mathematical operation skills》、《Summary of usage of php regular expressions》、《Summary of PHP operations and operator usage》、《Summary of usage of php strings"and"Summary of common database operation techniques for php》

I hope this article will be helpful to everyone's PHP programming.