冒泡排序

基本思路：两层循环，相邻元素比较，小的上浮 时间复杂度：O(n²)

function bubble_sort($arr){
    for($i = 0; $i < count($arr)-1; $i++){
        for($j = $i+1; $j < count($arr); $j++){
            if($arr[$j] < $arr[$i]){
                $tmp=$arr[$i];
                $arr[$i]=$arr[$j];
                $arr[$j]=$tmp;
            }
        }
    }
    return $arr;
}

插入排序

基本思路：两层循环，每次将最小的上浮至顶 时间复杂度：O(n²)

function insert_sort($arr){
    for($i = 1; $i < count($arr); $i++){
        $tmp=$arr[$i];
        $j=$i-1;
        while ($arr[$j] > $tmp){
            $arr[$j+1]=$arr[$j];
            $arr[$j]=$tmp;
            $j--;
            if($j<0){
                break;
            }
        }
    }
    return $arr;
}

选择排序

基本思路：两层循环，每次选择最小的上浮 时间复杂度：O(n²)

function select_sort($arr){
    for($i = 0; $i < count($arr)-1; $i++){
        $k=$i;
        for($j = $i+1; $j < count($arr); $j++){
            if($arr[$j] < $arr[$k]){
                $k=$j;
            }
            if($k!=$i){
                $tmp=$arr[$i];
                $arr[$i]=$arr[$k];
                $arr[$k]=$tmp;
            }
        }
    }
    return $arr;
}

快速排序

基本思路：递归调用，把小的放左序列，大的放右序列，然后合并 时间复杂度：O(n log n)

function quick_sort($arr){
    if(count($arr) <= 1){
        return $arr;//如果只有一个元素，直接返回
    }
    $mid = $arr[0];//基准值
    $left_arr = $right_arr = [];
    for($i = 1; $i < count($arr); $i++){
        if($arr[$i]<=$mid) {
            $left_arr[] = $arr[$i];
        }else{
            $right_arr[] = $arr[$i];
        }
    }
    //var_dump($left_arr,$mid,$right_arr);
    $left_arr=quick_sort($left_arr);//进行递归；
    $right_arr=quick_sort($right_arr);
    return array_merge($left_arr,[$mid],$right_arr);//将左中右的数组合并成一个数组；
}

排序测试

function getTime($time_model){
    if($time_model=='ms') {
        $mtime=explode(' ',microtime());
        return $mtime[1]+$mtime[0];
    }else if($time_model=='s'){
        return time();
    }else{
        $mtime=explode(' ',microtime());
        return $mtime[1]+$mtime[0];
    }
}
//$class_name 排序函数名 $arr 排序数组 $time 执行次数 $show_per是否显示每次执行时间 $time_model 时间显示单位 毫秒ms
function test_sort($class_name,$arr,$time=3,$show_per=1,$time_model = 'ms'){
    $all_time=0;
    for($i = 1; $i <= $time; $i++){
        $startTime = getTime($time_model);
        $sort_arr=$class_name($arr);
        $endTime = getTime($time_model);
        $costTime = bcsub($endTime,$startTime);
        if($show_per){
            var_dump($class_name." 第 $i 次排序数组count=".count($arr)."运行花费 ".$costTime." s");
        }
        $all_time = bcadd($all_time,$costTime);
    }
    var_dump($class_name." 总运行 $time 次,排序数组count=".count($arr)."平均每次花费 ".bcdiv($all_time,$time)." s");
    //return $sort_arr;
}
function rand_arr($len){
    for ($i = 1; $i <= $len; $i++){
        $arr[]=rand(1,$len);
    }
    return $arr;
}

随机数组排序测试开始

bcscale(3);
$len=5000;
$time=10;
$show_per=1;
$time_model='ms';
var_dump(test_sort('bubble_sort',rand_arr($len),$time,$show_per,$time_model));
var_dump(test_sort('insert_sort',rand_arr($len),$time,$show_per,$time_model));
var_dump(test_sort('select_sort',rand_arr($len),$time,$show_per,$time_model));
var_dump(test_sort('quick_sort',rand_arr($len),$time,$show_per,$time_model));

随机数组排序测试结果

bubble_sort 总运行 10 次,排序数组count=5000平均每次花费 1.644 s
insert_sort 总运行 10 次,排序数组count=5000平均每次花费 0.952 s
select_sort 总运行 10 次,排序数组count=5000平均每次花费 3.116 s
quick_sort 总运行 10 次,排序数组count=5000平均每次花费 0.021 s
有上可见，一般数字数组使用递归快速排序性能高的多

二分查找递归

//二分查找递归 $arr必须为排好序的 返回$value在$arr中查到的index,找不到返回-1
function bin_search($arr, $value, $start = 0, $end = NULL){
    if($end == NULL){
        $end = count($arr)-1;
    }
    $mid = floor(($start+$end)/2);
    //var_dump($start,$mid,$end);
    if($value == $arr[$mid]){
        return $mid;
    }else{
        if($end==$start && $start==$mid){
            return -1;
        }
    }
    if ($value < $arr[$mid]){
        return bin_search($arr,$value,$start,$mid-1);
    }else{
        return bin_search($arr,$value,$mid+1,$end);
    }
}