[PHP知识库]PHP的四种基本排序整理

1、冒泡排序

function bubbleSort ($arr) {     
if (!is_array($arr)) return false;
    $len = count($arr);     
    if ($len <= 1) return $arr;    //控制需要处理冒泡次数
    for ($i=1; $i<$len; $i++) {        //控制数组需要比较冒泡次数
        for ($k=0; $k < $len-$i; $k++)  {            
        	if ($arr[$k] > $arr[$k+1]) {
                $tmp = $arr[$k];
                $arr[$k] = $arr[$k+1];
                $arr[$k+1] = $tmp;
            }
        }
    }    
    return $arr;
}

2. 二分查找法

/**
 * 二分查找 $arr需排好序
 * @param $arr
 * @param $start
 * @param $end
 * @param $params
 * @return mixed
 */
function erFen($arr, $start, $end, $params){
    $key = intval(($start+$end)/2);
    if($arr[$key] == $params){
        return $key;
    }elseif($arr[$key] < $params){
        return erFen($arr, $key+1,$end,$params);
    }else{
        return erFen($arr, $start,$key-1,$params);
    }
    return false;
}

3. 快速排序

function quickSort($arr)
{
    $count = count($arr);   //统计出数组的长度
    if ($count <= 1) { // 如果个数为空或者1，则原样返回数组
        return $arr;
    }
    $index = $arr[0]; // 把第一个元素作为标记
    $left = [];    //定义一个左空数组
    $right = [];    //定义一个有空数组
    for ($i = 1; $i < $count; $i++) {   //从数组的第二数开始与第一个标记元素作比较
        if ($arr[$i] < $index) {        //如果小于第一个标记元素则放进left数组
            $left[] = $arr[$i];
        } else {                        //如果大于第一个标记元素则放进right数组
            $right[] = $arr[$i];
        }
    }
    $left  = quickSort($left);      //把left数组再看成一个新参数，再递归调用，执行以上的排序
    $right = quickSort($right);     //把right数组再看成一个新参数，再递归调用，执行以上的排序
    return array_merge($left, [$arr[0]], $right);   //最后把每一次的左数组、标记元素、右数组拼接成一个新数组
}
 
$arrtest=[12,43,54,33,23,14,44,53,10,3,56]; //测试数组
$res=quickSort($arrtest);     
var_dump($res);

4. 插入排序

/*
 * 从后向前扫描
 * 该元素已大于已排序$tmp，则该元素下移一个位置
 **/function insertSort($arr){
    $len = count($arr);    
    for ($i=1; $i<$len; $i++) {        //假设当前值
        $tmp = $arr[$i];        //需要插入次数
        for ($j=$i-1; $j>=0; $j--) {            //位置互换
            if ($tmp < $arr[$j]) {
                $arr[$j+1] = $arr[$j];
                $arr[$j]    = $tmp;
            } else {                break;
            }
        }
    }    return $arr;
}

面试常见面试题

1. 遍历目录

/**
 * 遍历目录
 * @param $dir
 * @return array
 */
function b_list($dir){
    $dir .= substr($dir,-1) == '/'?'':'/';
    echo $dir;
    $listArr = [];
    foreach(glob($dir."*") as $v){
        $listArr[] = $v;
        if(is_dir($v)){
            $listArr = array_merge($listArr,b_list($v));
        }
    }
    return $listArr;
}

var_dump(b_list('E:/shen'));die;

2、Php实现一个双向队列

class  Myqueue{
    private $queue = [];
    public function push($params){
       array_push($this->queue, $params);
    }

    public function pop(){
        array_pop($this->queue);
    }

    public function shift(){
        array_shift($this->queue);
    }

    public function unshift($params){
        array_unshift($this->queue, $params);
    }

    public function getQueue(){
        return $this->queue;
    }
}
$obj = new Myqueue();
$obj->push(1);
$obj->push(2);
$obj->push(3);
$obj->push(4);

$obj->pop();
$obj->shift();
$obj->unshift(7);
$obj->unshift(8);
$obj->unshift(9);
var_dump($obj->getQueue());die;

3. 一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n,输出最后那个大王的编号

/**
 * 数猴子 找大王
 * @param $n  总数
 * @param $m  踢数
 * @return mixed
 */
function monkey($n, $m){
    $arr = range(1, $n);
    $i = 0;
    while(count($arr)>1){
        $i+=1;
        $head = array_shift($arr);
        if($i % $m != 0){
            array_push($arr, $head);
        }
    }
    return $arr[0];
}
echo monkey(10, 5);die;

4、 写一个二维数组排序算法函数，能够具有通用性，可以调用php内置函数

/**
 * 自定义二维数组按照某个键值排序
 * @param $arr
 * @param $key
 * @param $order
 * @return array
 */
function myOrder($arr, $key, $order){
    $keyArr = [];
    foreach($arr as $k=>$v){
        $keyArr[$k] = $v[$key];
    }
    if(strcasecmp($order, 'asc') == 0){
        asort($keyArr);
    }

    if(strcasecmp($order, 'desc') == 0){
        arsort($keyArr);
    }
    $newArr = [];
    foreach($keyArr as $k=>$v){
        $newArr[$k] = $arr[$k];
    }
    return $newArr;
}

$arr = [
    [
        'name'=>'shen25',
        'age'=>'25',
    ],
    [
        'name'=>'shen27',
        'age'=>'27',
    ],
    [
        'name'=>'shen24',
        'age'=>'24',
    ],
    [
        'name'=>'shen26',
        'age'=>'26',
    ],
    [
        'name'=>'shen30',
        'age'=>'30',
    ],
];
var_dump(myOrder($arr, 'age', 'desc'));die;

5. 顺序查找元素

/**
 * 顺序查找
 * @param $arr
 * @param $params
 * @return int|string
 */
function findParams($arr, $params){
    foreach($arr as $k=>$v){
        if($v == $params){
            return $k;
        }
    }
    return -1;
}
$arr = [1, 3, 2, 5, 123, 4, 54, 2];
var_dump(findParams($arr, 123));die;

6. 比较两个文件路径的相对

$b = '/a/b/c/d/e.php';
$a = '/a/b/f/g/j/h.php';
function diff($a, $b){
    $aArr = explode('/',$a);
    $bArr = explode('/',$b);
    $bCount = count($bArr);
    $k = 0;
    for($i=0;$i<$bCount;$i++){
        if($aArr[$i] != $bArr[$i]){
            $k = $i;
            break;
        }
    }
    //echo $k;die;
    //var_dump(array_fill(0, $bCount-$k, '..'));die;
    $result = array_merge(array_fill(1, $bCount-$k-1, '..'), array_slice($aArr,$k));
    return implode('/', $result);
}
var_dump(diff($a, $b));die;