Quick sort implemented by PHP recursion method-PHP Tutorial-php.cn

Quick sort implemented by PHP recursion method

墨辰丷

Release： 2023-03-31 22:26:01

Original

3104 people have browsed it

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

Copy after login

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

Copy after login

Use:

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

var_dump(quicksortx($testArr));

Copy after login

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!