php实现归并排序算法(对n个有序数组组成的二维数组有效)

  • 内容
  • 评论
  • 相关

php

“归并排序”是建立在归并操作上的一种有效的“排序算法”,该算法是采用分治法(Divide and Conquer)的一个非常型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个序表合并成一个有序表,称为“二路归并”。

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一序表中剩余的元素复制到r中 从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中二分,接着把左边子区间排序,再把右边子区间排序,最后把左 区间和右区间用一次归并操作合并成有序的区间[s,t]。

说人话就是,对两个有序数组中的各个值按key值从小到大的顺序进行value值比较,当两个数组的key值分别都在各自的数组长度范围内的时候,进行一对一的比较,将比较中较小的value值存放在一个新的数组内。并且该value值对应的key值向前递增1。由于两个数组的各个value值都比较完之后,最后的一组比较中,较大值不能进行下一轮比较,所以将此时该value值放进新数组中,作为新数组中的最大值。下面上代码:
<?php
    function array_all($array_all){
        $i=0;
        $count_array_all=count($array_all);
        //echo $count_array_all;exit;

        if($count_array_all>=2){
            $arr_merge=merge_sort();
            for($i;$i<$count_array_all;$i++){
                $arr_merge=merge_sort($arr_merge,$array_all[$i]);
            }
        }else{
            $arr_merge=$array_all[$i];
        }
        return $arr_merge;
    }

    function merge_sort($arrA=array(), $arrB=array()) {
        $a_i = $b_i = 0;//设置两个起始位置标记
        $lenA = count($arrA);
        $lenB = count($arrB);
        $arrC=array();
        if($lenB==0){
            return $arrA;
        }else if($lenA==0){
            return $arrB;
        }else{
            while($a_i<$lenA && $b_i<$lenB) {
            //当数组A和数组B的指针位置在数组界内时
                if($arrA[$a_i] < $arrB[$b_i]) {
                    $arrC[] = $arrA[$a_i++];
                } else {
                    $arrC[] = $arrB[$b_i++];
                }
            }
            //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
            while($a_i < $lenA) {
                $arrC[] = $arrA[$a_i++];
            }
            //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
            while($b_i < $lenB) {
                $arrC[] = $arrB[$b_i++];
            }
            //merge_sort($arrC,$arrD=array());
            return $arrC;
        }

    }

    // $arr=merge_sort(array(1,3,5),array(2,4,6));
    // stamp($arr);

    function stamp($arr){
        echo "<pre>";
        return print_r($arr);
    }

    // $arr=array(array(1,4,12,23),array(2,6,98),array(9,20,35));
    // stamp(array_all($arr));
?>

评论

1条评论
  1. Gravatar 头像

    g

    Thanks very interesting blog!