算法

算法

快速排序

<?php
// 快速排序
function quickSort($arr) {
        // 基线条件
        $length = count($arr);
        if($length < 2) return $arr;
        // 基准值
        $pivot = $arr[0];
        // 子数组
        $less = [];
        $greater = [];

        for($i=1; $i<$length; $i++) {
                if($pivot > $arr[$i]) {
                        $less[] = $arr[$i];
                } else {
                        $greater[] = $arr[$i];
                }
        }

        // 递归
        $less = quickSort($less);
        $greater = quickSort($greater);

        return array_merge($less, [$pivot], $greater);
}

$list = [5, 3, 7, 2, 9];
$data = quickSort($list);
var_dump($data);

选择排序

<?php
// 选择排序
function selectSort($arr) {
        for($i=0, $length=count($arr); $i<$length-1;$i++) {
                // 定义最小值的索引位置的变量
                $minIndex = $i;
                for($j=$i+1; $j<$length; $j++) {
                        // 判断假定最小值的索引位置的值是否大于该值，
                        // 若大于说明假定最小值的索引位置的变量值需要使用该值的索引位置替换
                        if($arr[$minIndex] > $arr[$j]) {
                                $minIndex = $j;
                        }
                }

                // 判断当前的假定最小值的索引位置的变量值是否和原来的赋值相等，若不等说明需要互换索引位置
                if($minIndex != $i) {
                        $tmp = $arr[$minIndex];
                        $arr[$minIndex] = $arr[$i];
                        $arr[$i] = $tmp;
                }
        }

        return $arr;
}

$arr = [5, 2, 4, 1, 8];
$data = selectSort($arr);
var_dump($data);

二分查找法

<?php
// 二分查找法
// 非递归，普通循环
function binarySearch($arr, $item) {
        $low = 0;
        $high = count($arr) - 1;
        while($low <= $high) {
                $mid = floor( ($low + $high) / 2 );
                if($arr[$mid] == $item) {
                        return $mid;
                } elseif($arr[$mid] < $item) {
                        $low = $mid + 1;
                } else {
                        $high = $mid - 1;
                }
        }
        return -1;
}
// 递归
function binary($arr, $item, $low, $high) {
        if($low <= $high) {
                $mid = floor( ($low + $high) / 2 );
                if($arr[$mid] == $item) {
                        return $mid;
                } elseif($arr[$mid] < $item) {
                        return binary($arr, $item, $mid + 1, $high);
                } else {
                        return binary($arr, $item, $low, $mid - 1);
                }
        } else {
                return -1;
        }
}
$list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
$data = binarySearch($list, 3);
echo $data;
echo "\r\n";
$data1 = binary($list, 3, 0, count($list) - 1);
echo $data1;
echo "\r\n";
?>