yjiang's cake

排序

冒泡排序

从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒
N 个数字来排队,两两相比小靠前,外层循环 N-1,内层循环 N-1-i

function bobble($arr){
    //获取长度
    $count = count($arr);
    //第一层, 控制轮次
    for($i=0; $i<$count-1; $i++){
        //内循环, 对比当前跟后一个值, 调换大的
        for($k=0; $k<$count-1-$i; $k++){
            if( $arr[$k] > $arr[$k+1]){
                $tmp = $arr[$k+1];
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }

    return $arr;
}

快速排序

选择第一个元素为基准元素, 比基准元素大的放入右边, 比基准元素小的放入左边; 递归左右元素排序后, 合并

function quick($arr){
    //获取数组长度
    $count = count($arr);
    //判断是否需要继续二分
    if( $count <= 1 ) return $arr;

    //定义一个基准值
    $base = $arr[0];

    //定义两个栈用于存放结果
    $left = [];
    $right = [];

    //遍历
    for($i=1; $i<$count; $i++){
        if( $arr[$i] > $base ){
            $right[] = $arr[$i];
        }
        else{
            $left[] = $arr[$i];
        }
    }

    //递归处理left/right
    $left = quick($left);
    $right = quick($right);

    //合并
    return array_merge($left, [$base], $right);
}

选择排序

在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止

function select($arr){
    $count = count($arr);

    //第一层, 控制轮次
    for($i=0; $i<$count-1; $i++){
        //先假设最小值在第一位
        $p = $i;
        for($k=$i+1; $k<$count; $k++){
            //$arr[$p] 是当前已知最小值
            if($arr[$p] > $arr[$k]){
                //比较并记录最小值位置
                $p = $k;
            }
        }

        //最小值保存到$p; 如果位置与当前假设位置不同, 则位置互换
        if( $p != $i ){
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }

    return $arr;
}

插入排序

假设前面的数已经是排好顺序的, 现在要把第n个数插到前面的有序数中, 使得这n个数也是排好顺序的; 如此反复循环,直到全部排好顺序

function insert($arr){
    $count = count($arr);
    for($i=1; $i<$count; $i++){
        $tmp = $arr[$i];
        //内层循环进行比较并插入
        for($k=$i-1;$k>=0;$k--){
            if($tmp < $arr[$k]){
                //发现插入的元素较小, 则将后面元素与前面元素互换
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
            else{
                //如果碰到不需要移动的元素, 不再进行比较
                break;
            }
        }
    }
    return $arr;
}

查找

顺序查找

function order($arr, $find){
    $count = count($arr);
    for($i=0; $i<$count-1; $i++){
        if($find == $arr[$i]){
            return $i;
        }
    }
    return false;
}

二分查找

function binary($arr, $find){
    $mid = floor(count($arr) / 2);
    //取数组中间值, 如果中间值即是查找值, 则返回下标
    if( $find == $arr[$mid] ){
        return $mid;
    }

    //数组从中间位置分割成left / right 两部分
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid+1, $mid);

    //如果查找值小于中间值, 则递归查找left数组
    if( $find < $arr[$mid] ){
        return binary($left, $find);
    }
    //如果查找值大于中间值, 则递归查找right数组
    if( $find > $arr[$mid] ){
        return binary($right, $find);
    }
}

约瑟夫环

顶部出栈, 尾部入栈, 循环遍历

function ysf($n, $m){
    $i = 1;
    while(true){
        if( count($n) <= 1 ){
            return $n;
        }
        $tmp = array_shift($n);
        if( $i != $m){
            array_push($n, $tmp);
            $i++;
            continue;
        }
        $i = 1;
    }
}

$foo = range(1, 10);
print_r(ysf($foo, 11));

猴子分桃

function gg($n){
    for($i=1;$i<=5;$i++){
        if( ($n - 1) % 5 == 0 ){
            $n = ($n - 1) / 5 * 4;
            //echo $n;
            continue;
        }
        return false;
    }
    return true;
}

//从小到大进行试探
$n = 1;
while(true){
    //因为需要被5整除, 所以此处可以改成`$n = $n+5`以降低试探次数
    $n++;
    if( gg($n) ){
        echo $n;exit;
    }
}