<?php 

/**
 * 冒泡排序
 * @param  [type] $arr [description]
 * @return [type]      [description]
 */
function bubbleSort($arr)
{
    $len = count($arr);
    if($len<=1)
    {
        return $arr;
    }
    for ($i=0;$i<$len;$i++)
    {
        for ($j=1;$j<$len-$i;$j++)
        {
            if($arr[$j-1]>$arr[$j])
            {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j-1];
                $arr[$j-1] = $tmp;
            }
        }
    }
    return $arr;

}
//选择
function selectSort($arr)
{
    $len = count($arr);
    for($i=0;$i<$len;$i++)
    {
        for($j = $i+1;$j<$len;$j++)
        {
            if($arr[$i]>$arr[$j])
            {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
    }
}
//插入
function insertSort($arr)
{
    $len = count($arr);
    for($i=1; $i<$len; $i++)
    {
        for ($j = $i-1;$j>=0;$j--)
        {
            if($arr[$i]>$arr[$j])
            {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
    }
    return $arr;
}
//快速
function quickSort($arr)
{
    $len = count($arr);
    if($len <=1 )
    {
        return $arr;
    }
    $base = $arr[0];
    $left_arr = [];
    $right_arr = [];
    for($i=1;$i<$len;$i++)
    {
        if($base>$arr[$i])
        {
            $left_arr[] = $arr[$i];
        }
        else
        {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = $this->quick_sort($left_arr);
    $right_arr = $this->quickSort($right_arr);

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

function halfSearch($arr, $search_val)
{
    $low = 0;
    $high = count($arr)-1;
    while($low <= $high)
    {
        if($arr[ceil(($low+$high)/2)] < $search_val)
        {
            $low = ceil(($low+$high)/2)+1;
        }
        elseif($arr[ceil(($low+$high)/2)] > $search_val)
        {
            $high = ceil(($low+$high)/2)-1;
        }
        else
        {
            return $arr[ceil(($low+$high)/2)];
        }
    }
    return false;
}

function strMatch($str, $par)
{
    for($i=0;$i<strlen($str);$i++)
    {
        $match =$i;
        $j = 0;
        while($i<strlen($str) && $j<strlen($par) && $par[$j] == $str[$match])
        {
            $match++;
            $j++;
        }
        if($j == strlen($par)) return $match - $j;
    }
    return false;
}