PHP版分治算法之“归并排序”

归并排序:对一堆支票进行排序。首先,将这堆未排序的支票对分成两堆。接着,分别又将两堆支票对半分成两堆,以此类推,重复此过程,直到每一堆支票只包含一张支票。一旦所有的堆都只包含一张支票,就开始将堆两两合并,这样每个合并出来的堆就是两个有序堆的合集,也是有序的,这个合并过程一直持续下去,直到一堆新的支票生成。此时,这堆支票就变成有序的了。

归并排序本质上是将一个无序元素集分割成许多只包含一个元素的集,然后不断地将这些小集合并,直到一个新的大有序数据集生成。

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

  /**
  * 归并排序
  * 分:将数据集等分为两半
  * 治:分别在两个部分用递归的方式继续使用归并排序法
  * 合:将分开的两个部分合并成一个有序的数据集
  */
  //测试数组
  $arr = array(5,7,4,9,3,2,8,6,12);
  function merge_sort( $array ){
    if ( count( $array ) <= 1){
      return $array;
    }
    //计算出中间键值
    $key = (int)(count( $array )/2);
    //将分成的两部分取出 赋值
    $left_arr = array_slice( $array, 0, $key);
    $right_arr = array_slice( $array, $key);
    //递归的调用 归并排序
    $left_arr = merge_sort( $left_arr );
    $right_arr = merge_sort( $right_arr );
    //合并排序
    $i = 0;
    $j = 0;
    $tmp = array();
    while( $i!=(count($left_arr)) && $j!=(count($right_arr)) ){
      if ( $left_arr[$i] < $right_arr[$j] ){
                $tmp[] = $left_arr[$i];
                $i++;
            } else {
                $tmp[] = $right_arr[$j];
                $j++;
            }
        }
        //其中一组先被合并完的情况
        if ( $i==count($left_arr) ){ //将另一组剩余值全部追加的$tmp数组后(即合并数组)
            $tmp = array_merge( $tmp, array_slice($right_arr, $j));
        }
        if ( $j==count($right_arr) ){
            $tmp = array_merge( $tmp, array_slice($left_arr, $i));
        }

        return $tmp;
    }

    //测试输出
    print_r(merge_sort($arr));
    
?>

 

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>