PHP常用的四种排序方法及二种查找方法

<?php

// 一、冒泡排序，正序排列

$arr = array(5,2,78,8,4,20,9,13,6,3);

// 1、【冒泡排序】正序向前冒泡

function bubble_sort_before($arr){

    $count = count($arr);

    for($i=0; $i<$count; $i++){

        // 这个是前冒泡，每次都将最小的向前移，所以，$i之前的数据就不用再排了

        for($j=$count-2; $j>=$i; $j—-){

            if($arr[$j+1] < $arr[$j]){

                $tmp       = $arr[$j];

                $arr[$j]   = $arr[$j+1];

                $arr[$j+1] = $tmp;

            }

        }

    }

    return $arr;

}

// 2、【冒泡排序】正序向后冒泡

function bubble_sort_after($arr){

    $count = count($arr);

    for($i=0; $i<$count; $i++){

        // 这个是向后冒泡，每次都将最大的向后移，所以，$count-$i之后的数据就不用再排了

        for($j=0; $j<$count-$i-1; $j++){

            if($arr[$j+1] < $arr[$j]){

                $tmp       = $arr[$j];

                $arr[$j]   = $arr[$j+1];

                $arr[$j+1] = $tmp;

            }

        }

    }

    return $arr;

}

// 二、【选择排序】正序选择排序

function select_sort($arr){

    $count    = count($arr);

    for($i=0; $i<$count; $i++){

        $minkey   = $i;  // 假设$i的值为最小值

        $minvalue = $arr[$minkey];

        for($j=$i; $j<$count-1; $j++){

            if($arr[$j+1] < $minvalue){

                $minkey   = $j+1;

                $minvalue = $arr[$j+1];

            }

        }

        // 数据交换【每次获取最小值，然后将最小值的位置与前面开始查询到的位置进行交换】

        $tmp          = $arr[$i];

        $arr[$i]      = $minvalue;  // 最小值赋值

        $arr[$minkey] = $tmp;

    }

    return $arr;

}

// 三、【插入排序】正序插入排序

function insert_sort($arr){

    $count    = count($arr);

    for($i=1; $i<$count; $i++){  // 从1开始查

        $insertvalue = $arr[$i];  // 要插入的值，准备和下标为$indexkey的比较值

        $comparekey  = $i-1; // 被比较值的键

        // 将比较位置之前的所有比$intervalue大的值全部后移一位

        while($comparekey >=0 && $arr[$comparekey] > $insertvalue){  // 倒叙则为小于号

            $arr[$comparekey+1] = $arr[$comparekey];

            $comparekey–;

        }

        // 然后将查询到的值$insertval复制到最开始位移的位置，做好排序

        $arr[$comparekey+1] = $insertvalue;  // 最小值赋值

    }

    return $arr;

}

// 四、【快速排序】正序快速排序，递归方法

function quick_sort($arr){

    $count     = count($arr);

    if($count <= 1){ // 说明已经排完了，不用再接着比较了

        return $arr;

    }

    $left_arr  = $right_arr = array();

    $start_val = $arr[0];

    for($i=1; $i<$count; $i++){

        // 大于初始值的放右边，小于初始值的放左边

        if($arr[$i] > $start_val){

            $right_arr[] = $arr[$i];

        }else{

            $left_arr[]  = $arr[$i];

        }

    }

    // 然后再对两边的数据进行重新排序

    $left_arr  = quick_sort($left_arr);

    $right_arr = quick_sort($right_arr);

   

    // 对三种数据进行合并

    $arr = array_merge($left_arr,array($arr[0]), $right_arr);

    return $arr;

}

// 五、【顺序查找】按照从前往后的顺序进行查找

function find_order($arr, $find=“8”){

    $count    = count($arr);

    $is_find  = false;

    $find_key = ”;

    foreach($arr as $k=>$v){

        if($v == $find){

            $find_key = $k;

            $is_find  = true;

        }

    }

    if($is_find){

        return ‘已找到，位置为：’.$find_key;

    }else{

        return ‘未找到’;

    }

}

// 六、【二分查找】分段查找方法

sort($arr); // 先排序，二分查找函数,它有一个前提，查找的数组必须是有序的

$left_index = 0; $right_index = count($arr)-1;

function find_half($arr, $find=“8”, $left_index, $right_index){

    // 定义中间值

    if($left_index >= $right_index){

        return ‘未查找到’;

    }

    $middle_index = round(($left_index+$right_index)/2);  // 获取中间位置

    // 进行比较

    if($find < $arr[$middle_index]){

        find_half($arr, $left_index, $middle_index-1); // 向左比较

    }elseif($find > $arr[$middle_index]){

        find_half($arr, $middle_index+1, $right_index);  // 向右比较

    }elseif($find == $arr[$middle_index]){

        return ‘已找到，位置为：’.$middle_index;

    }

}