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