PHP两种快速排序算法实例


            虽然在PHP这样的web应用开发中，我们不是太强调排序的重要性，因为PHP自身已经带了例如sort()等这样强大的排序函数，但是在一些重要的场合，例如某些高并发的场合，我想排序算法的影响已经不能忽略。所以在此介绍递归排序和迭代排序。

递归法：





/**

* 递归法实现的快速排序

*/

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;

  }

}







迭代法：





/**

* 迭代法的快速排序

*/

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;

}







使用：





/**

*产生一个随机数组

*/

for($i=0;$i<5;$i++){

  $testArr[]=mt_rand(0,100);

}

var_dump($testArr);

var_dump(quicksort($testArr));



var_dump(quicksortx($testArr));