PHP版分治算法之“快速排序”

分治法包含3个步骤:分解、求解与合并。在分解阶段,将数据分解为更小,更容易管理的部分。在求解阶段,对每个分解出的部分进行处理。在合并阶段,将每部分处理的结果进行合并。

分治法的一个例子是“快速排序”,另一个例子是“归并排序”。

快速排序:举人工对一堆支票进行排序,可将未排序的支票分成两堆。其中一堆专门用于放小于或者等于某个编号的支票,而另一堆用来放大于这个编号的支票(一般认为这个编号选取大概是所有支票编号的中间值)。当以这种方式得到两堆支票后,又可以同样的方式将它们分成四堆,不断重复这个过程直到每个堆中只放有一张支票,这时,

所有支票就已经排好序了。

<?php
  /*
  * PHP分治法:包含三个步骤:分解,求解与合并。
  * eg:归并排序 和 快速排序。
  */

  /**
  * 快速排序(PHP版)
  * 分:设定一个分隔值,将数据分成两部分
  * 治:分别在两部分用递归的方式继续使用快速排序的方法
  * 合:对分割部分进行排序,直至完成
  */
  $arr = array(5,7,4,9,3,2,8);
  function quick_sort( $array ){
    if ( count( $array ) <= 1 ){
      return $array;
    }
    //在此随机选取数组第一个元素作为参照值
    $key = $array[0];
    $left_arr = array();
    $right_arr = array();
    for( $i=1; $i< count($array); $i++){
      if ( $array[$i] <= $key ){
                $left_arr[] = $array[$i];
            } else {
                $right_arr[] = $array[$i];
            }
        }
        $left_arr = quick_sort( $left_arr );
        $right_arr = quick_sort( $right_arr );
        //合并
        return array_merge( $left_arr, array($key), $right_arr);
    }
    
    //测试输出
    print_r( quick_sort( $arr ) );
?>

 

参考文章地址:http://blog.sina.com.cn/s/blog_68212b680100tgc9.html

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>