算法

汇总PHP最常见的四种排序算法

作者

PHP最常见的四种排序算法分别是：冒泡排序法，选择排序法、插入排序法和快速排序法。下面我们就分别给出四种排序算法的实现代码，供大家参考。

1.冒泡排序法

<?php
function bubble_sort($array)
{
    $count = count($array);
    if ($count == 0) {
        return false;
    }
    for ($i=0; $i<$count; $i++) {
        for ($k=$count-1; $k>$i; $k--) {
            if ($array[$k] < $array[$k-1]) {
                $tmp = $array[$k];
                $array[$k] = $array[$k-1];
                $array[$k-1] = $tmp;
            }
        }
    }
    return $array;
}

$a = array(2, 5, 1, 3, 4);
$a = bubble_sort($a);
var_dump($a);
?>

 

2.选择排序法

<?php
function select_sort($array)
{
    $len = count($array);
    for($i=0; $i<$len-1; $i++) {
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            if($array[$p] > $array[$j]) {
                $p = $j;
            }
        }
        if($p != $i) {
            $tmp = $array[$p];
            $array[$p] = $array[$i];
            $array[$i] = $tmp;
        }
    }
    
    return $array;
}

$a = array(2, 5, 1, 3, 4);
$a = select_sort($a);
var_dump($a);
?>

 

3.插入排序法

<?php
function insert_sort($array)
{
    $len = count($array);
    for($i=1; $i<$len; $i++) {
        $tmp = $array[$i];
        for($j=$i-1; $j>=0; $j--) {
            if($tmp < $array[$j]) {
                $array[$j+1] = $array[$j];
                $array[$j] = $tmp;
            } else {
                break;
            }
        }
    }
    
    return $array;
}

$a = array(2, 5, 1, 3, 4);
$a = insert_sort($a);
var_dump($a);
?>

 

4.快速排序法

<?php
function quick_sort($array)
{
    $len = count($array);
    if ($len <= 1) {
        return $array;
    }
    
    $base = $array[0];
    
    $left = array();
    $right = array();
    for ($i=1; $i<$len; $i++) {
        if($base > $array[$i]) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    $left = quick_sort($left);
    $right = quick_sort($right);
    
    return array_merge($left, array($base), $right);
}

$a = array(2, 5, 1, 3, 4);
$a = quick_sort($a);
var_dump($a);
?>

 

阳光部落原创，更多内容请访问http://www.sunbloger.com/

一段经典的抽奖算法 for PHP版

作者

首先，我们构造一个奖项数组：

<?php
$prize_arr = array(
    array('id'=>1, 'prize'=>'No.1', 'v'=>1),
    array('id'=>2, 'prize'=>'No.2', 'v'=>3),
    array('id'=>3, 'prize'=>'No.3', 'v'=>6),
    array('id'=>4, 'prize'=>'No.4', 'v'=>10),
    array('id'=>5, 'prize'=>'No.5', 'v'=>20),
    array('id'=>6, 'prize'=>'Sorry', 'v'=>60),
);
?>

上面的数组中，No.1代表1等奖，以此类推，No.5代表5等奖，而Sorry代表没有中奖。v代表概率。

继续，我们看看算法的代码：

<?php
function get_rand($proArr) {
    $result = '';
    //概率数组的总概率精度
    $proSum = array_sum($proArr);
    //概率数组循环
    foreach ($proArr as $key => $proCur) {
        $randNum = mt_rand(1, $proSum);
        if ($randNum <= $proCur) {
            $result = $key;
            break;
        } else {
            $proSum -= $proCur;
        }
    }
    unset($proArr);
    return $result;
}
?>

上面的代码从1等奖开始，根据概率逐一计算每个奖项是否中出，直至最后没有中奖。

究竟这个算法是否准确，我们来模拟一下：

<?php
//通过奖项数组，构造出一个用于抽奖的概率数组
foreach ($prize_arr as $key => $val) {
    $arr[$key] = $val['v'];
}

//模拟1万次抽奖
for ($i=1; $i<=10000; $i++) {
    $prize_key = get_rand($arr);
    if (isset($test[$prize_arr[$prize_key]['prize']])) {
        $test[$prize_arr[$prize_key]['prize']]++;
    } else {
        $test[$prize_arr[$prize_key]['prize']] = 1;
    }
}
print_r($test);
?>

上面代码的模拟结果输出：

Array
(
    [sorry] => 6017
    [No.5] => 2011
    [No.4] => 968
    [No.3] => 587
    [No.2] => 310
    [No.1] => 107
)

通过模拟结果可以看出，这个算法还是很靠谱的。

阳光部落原创，更多内容请访问http://www.sunbloger.com/