IT

PHP算法

  1. 冒泡算法

    public function index()
    {
        // 创建一个 1-100的数组
        $arr = range(1, 100);
    
        // 打乱数组
        shuffle($arr);
    
        // 执行算法
        var_dump($this->bubbling($arr));
    }
    
    public function bubbling($arr)
    {
        // 获取数组长度
        $length = count($arr) - 1;
    
        // 循环对比的轮数
        for ($i = 0; $i < $length; $i++) {
            // 数组元素对比循环
            for ($j = 0; $j < $length - $i; $j++) {
                // 如果前位数比后位数大则把两位数互换
                if ($arr[$j] > $arr[$j + 1]) {
                    $tmp = $arr[$j];
    
                    $arr[$j] = $arr[$j + 1];
    
                    $arr[$j + 1] = $tmp;
                }
            }
        }
    
        return $arr;
    }
  2. 猴子选大王算法
    问题:一堆猴子都有编号,编号是1,2,3 …m ,这群猴子(m个)按照1到m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王

    public function king()
    {
        // 建立随机数组
        $arr = range(1, 10);//示例数组
        // 执行算法
        var_dump('国王是:'.$this->showKing($arr,2));
    }
    
    public function showKing($arr,$count)
    {
        // 从第一位开始算 因数组由0下标开始 但正常数据从1开始
        $i = 1;
    
        while (true)
        {
            // 如果数组剩下一个 则直接返回
            if (count($arr) <= 1) {
                break;
            }
    
            // 取余得整数则为位数匹配,剔除当前位数数据
            if ($i%$count == 0) {
                unset($arr[$i - 1]);
            } else {
                // 如果当前位数不匹配 则把当前位数追加到末尾
                array_push($arr, $arr[$i - 1]);
    
                // 并且删除当前位数
                unset($arr[$i - 1]);
            }
    
            // 位数递增
            $i++;
        }
    
        // 返回最后一个 因为数组只有一个 用end是因为数组的key并不是关联数组
        return end($arr);
    }
  3. 插入排序

    public function index()
    {
        // 创建一个 1-100的数组
        $arr = range(1, 100);
    
        // 打乱数组
        shuffle($arr);
    
        // 执行算法
        var_dump($this->select($arr));
    }
    
    public function select($arr)
    {
        $len = count($arr);
    
        //$i 当前最小值的位置, 需要参与比较的元素
        for ($i = 0; $i < $len - 1; $i++) {
            //先假设最小的值的位置
            $p = $i;
    
            //$j 当前都需要和哪些元素比较,$i 后边的。
            for ($j = $i + 1; $j < $len; $j++) {
                //$arr[$p] 是 当前已知的最小值
                //比较,发现更小的,记录下最小值的位置;并且在下次比较时,应该采用已知的最小值进行比较。
                $p = ($arr[$p] <= $arr[$j]) ? $p : $j;
            }
    
            //已经确定了当前的最小值的位置,保存到$p中。
            //如果发现 最小值的位置与当前假设的位置$i不同,则位置互换即可
            if ($p != $i) {
                $tmp     = $arr[$p];
                $arr[$p] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
        //返回最终结果
        return $arr;
    }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注