/**
      * 归并排序实现过程
      * @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 && $j <= $end)
        {
            if ($arr[$i] <= $arr[$j])    //判断两个区间数组各自数据的大小，并归类
                $tmp[$k++] = $arr[$i++];
            else
                $tmp[$k++] = $arr[$j++];
        }

        while($i <= $mid)    //防止第一个区间有一个数据没有归类
            $tmp[$k++] = $arr[$i++];

        while($j <= $end) //防止第二个区间有一个数据没有归类
            $tmp[$k++] = $arr[$j++];

        // 将排序后的元素，全部都整合到数组arr中。
        for ($i = 0; $i < $k; ++$i)
            $arr[$start + $i] = $tmp[$i];
    }
    /**
      * 归并排序(从上往下)
      * @param Array $arr 待排序的数组
      * @param Int $start 数组起始位置
      * @param Int end 数组结束位置
      * @return void
      */
    function merge_sort(Array &$arr,$start=0,$end=0)
    {
        $len = count($arr);
        if($len <= 1 || $start >= $end)
            return $arr;
        $mid = intval(($start + $end) / 2); //分区间
    
        merge_sort($arr,$start,$mid);
        merge_sort($arr,$mid+1,$end);

        merge($arr,$start,$mid,$end);
    }

   //从下往上与此刚好相反

    /**
　　　* （总-判-定-1-2-合）
      * 快速排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      */
    function quick_sort(Array $arr)
    {
        $len = count($arr);
        if($len <= 1)
            return $arr;
        $tmp = $arr[0];
        $left_arr = [];
        $right_arr = [];
        for($i = 1; $i < $len; ++$i)
        {
            if($arr[$i] <= $tmp)
                $left_arr[] = $arr[$i];
            else
                $right_arr[] = $arr[$i];
        }
        //递归分类
        $left_arr = quick_sort($left_arr);
        $right_arr = quick_sort($right_arr);

        return array_merge($left_arr,array($tmp),$right_arr);
    }
    

    /**
      * （总-0-减-比-反）
      * 冒泡排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      */
    function bubble_sort(Array $arr)
    {
        $len = count($arr);
        for($i = 0; $i < $len; ++$i)
        {
            for($j = $len - 1; $j > $i; --$j)
            {
                if($arr[$j] < $arr[$j-1])
                {
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j-1];
                    $arr[$j-1] = $tmp;
                }
            }
        }
        return $arr;
    }

    /**
      * 插入排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      */
    function insert_sort(Array $arr)
    {
        $len = count($arr);
        for($i = 1; $i < $len; ++$i)
        {
            $tmp = $arr[$i];
            $j = $i - 1;
            //把数据插入到合适的位置(交换位置)
            while($j >= 0 && $arr[$j] > $tmp)
            {
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
                --$j;
            }
        }
        return $arr;
    }

    /**
      * 选择排序
      * @param Array $arr 待排序的数组
      * @return Array 排序后的数组
      */
    function select_sort(Array $arr)
    {
        $len = count($arr);
        for($i = 0; $i < $len; ++$i)
        {
            $k = $i;    //标记当前索引
            for($j = $i + 1; $j < $len; ++$j)
            {
                if($arr[$j] < $arr[$k])
                    $k = $j; //获取当前最小值索引
                if($k != $i) //如果最小值得索引发生变化
                {
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$k];
                    $arr[$k] = $tmp;
                }
            }
        }
        return $arr;
    }

    /**
      * （大-判-小-转-中-三）
      * 二分查找
      * @param Array $arr 待查找的数组
      * @param Int $key 要查找的关键字
      * @return Int
      */
    function bin_search(Array $arr,$key)
    {
        $high = count($arr);
        if($high <= 0)
            return 0;
        $low = 0;
        while($low <= $high)
        {     
            //当前查找区间arr[low..high]非空
              $mid=intval(($low + $high) / 2);
            if($arr[$mid] == $key) 
                return $mid; //查找成功返回
            if($arr[$mid] > $key)
                $high = $mid - 1; //继续在arr[low..mid-1]中查找
            else
                $low = $mid + 1; //继续在arr[mid+1..high]中查找
        }
        return 0; //当low>high时表示查找区间为空，查找失败
    }
    $arr = array(1,2,4,6,10,40,50,80,100,110);
    echo bin_search($arr,80);