欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

php常用的排序算法与二分法查找,php算法二分法_PHP教程

程序员文章站 2024-04-04 18:13:05
...

php常用的排序算法与二分法查找,php算法二分法

一 : 归并排序

将两个的有序数列合并成一个有序数列,我们称之为"归并"。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现,归并排序包括"从上往下"和"从下往上"2种方式。


1. 从下往上的归并排序:将待排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;得到若干个长度为2的有序数列,再将这些数列两两合并;得到若干个长度为4的有序数列,再将它们两两合并;直接合并成一个数列为止。这样就得到了我们想要的排序结果

2. 从上往下的归并排序:它与"从下往上"在排序上是反方向的。它基本包括3步:
① 分解 -- 将当前区间一分为二,即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

    /**
      * 归并排序实现过程
      * @param Array $arr 待排序的区间数组
      * @param Int $start 第一个区间数组的起始位置
      * @param Int $mid 第一个区间数组的结束位置,第二个区间数组的起始位置
      * @param Int $end 第二个区间数组的结束位置
      * @return void
      */
    function merge(Array &$arr,$start,$mid,$end)
    {
        $i = $start;
        $j = $mid + 1;
        $k = 0; 

        while($i $mid