Home  >  Article  >  Backend Development  >  Quick sort implemented by PHP recursion method

Quick sort implemented by PHP recursion method

墨辰丷
墨辰丷Original
2018-06-13 11:54:063062browse

This article mainly introduces two examples of quick sorting algorithms in PHP. This article directly gives the implementation code, which is implemented using the recursive method and the iterative method respectively. Friends in need can refer to it

Although in PHP such In web application development, we don't emphasize the importance of sorting too much, because PHP itself already comes with powerful sorting functions such as sort(), but in some important occasions, such as certain high-concurrency occasions, I think the sorting algorithm The impact cannot be ignored. So here we introduce recursive sorting and iterative sorting.

Recursive method:

/**
* 递归法实现的快速排序
*/
function quicksort($seq)
{
    $k = $seq[0];
    $x = array();
    $y = array();
    for($i=1; $i< $_size; $i++) {
      if($seq[$i] <= $k) {
        $x[] = $seq[$i];
      } else {
        $y[] = $seq[$i];
      }
    }
    $x = quicksort($x);
    $y = quicksort($y);
    return array_merge($x, array($k), $y);
  } else {
    return $seq;
  }
}

Iterative method:

/**
* 迭代法的快速排序
*/
function quicksortx(&$seq)
{
  $stack = array($seq);
  $sort = array();
  while ($stack) {
    $arr = array_pop($stack);
    if(count($arr) <= 1) {
      if(count($arr) == 1) {
        $sort[] = &$arr[0];
      }
      continue;
    }
    $k = $arr[0];
    $x = array();
    $y = array();
    $_size = count($arr);
    for($i =1 ;$i < $_size; $i++) {
      if($arr[$i] <= $k) {
        $x[] = &$arr[$i];
      } else {
        $y[] = &$arr[$i];
      }
    }
    !empty($y) && array_push($stack, $y);
    array_push($stack, array($arr[0]));
    !empty($x) && array_push($stack, $x);
  }
  return $sort;
}

Use:

/**
*产生一个随机数组
*/
for($i=0;$i<5;$i++){
  $testArr[]=mt_rand(0,100);
}
var_dump($testArr);
var_dump(quicksort($testArr));

var_dump(quicksortx($testArr));

Summary: The above is the entire content of this article, I hope it will be helpful to everyone's study.

Related recommendations:

php method to implement client-side and server-side uploading of images

php code to implement control of file download speed

php uses an array to populate the drop-down list box

The above is the detailed content of Quick sort implemented by PHP recursion method. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn