冒泡排序函数python_所有最常见最经典的算法题，看完让你怀疑人生！

算法是我们学习的一大弱项，今天我整理了一份PHP经典算法题库，不怕怀疑人生，跟着学就对了！

1. 一群猴子排成一个圆圈，并标上 1, 2, ..., n 的编号。然后从第一只猴子开始数，数到第 m 只猴子，把它踢出圆圈，从它后面开始数，数到第 m 只猴子，再把它踢出圆圈……，一直这样下去，直到只剩下一只猴子。那只猴子就叫做国王。编写程序模拟这个过程，输入 m 和 n，输出最后一位国王的编号。

function king($n, $m){
    $monkeys = range(1, $n);         //创建1到n数组
    $i=0;
    while (count($monkeys)>1) {     //循环条件为猴子数量大于1
        if(($i+1)%$m==0) {     //$i为数组下标;$i+1为猴子标号
            unset($monkeys[$i]);  //余数等于0表示正好第m个，删除，用unset删除保持下标关系
        } else {
            array_push($monkeys,$monkeys[$i]);     //如果余数不等于0，则把数组下标为$i的放最后，形成一个圆形结构
            unset($monkeys[$i]);
        }
            $i++;//$i 循环+1，不断把猴子删除，或 push到数组 
    }
    return current($monkeys);  //猴子数量等于1时输出猴子标号，得出猴王
}
echo king(6,3);

2.有一头母牛，4岁能产一头母牛，每年产一头母牛，她产下的所有母牛都是一样的，15岁绝育，不能再生育，20岁死亡，请问n年后一共有多少头母牛？

function niu($y){
    static $num= 1;                    //定义静态变量;初始化牛的数量为1
    for ($i=1; $i <=$y ; $i++) {    
        if($i>=4 && $i<15){         //每年递增来算，4岁开始+1，15岁不能生育
        $num++;
            niu($y-$i);               //递归方法计算小牛$num，小牛生长年数为$y-$i
        }else if($i==20){          
        $num--;                             //20岁死亡减一
        }
    return $num;
}

3.帕斯卡三角形

/* 默认输出十行，用T(值)的形式可改变输出行数 */
class T{
  private $num;
  public function __construct($var=10) {
    if ($var<3) die("值太小啦！");
    $this->num=$var;
  }
  public function display(){
    $n=$this->num;
    $arr=array();
  //$arr=array_fill(0,$n+1,array_fill(0,$n+1,0));
    $arr[1]=array_fill(0,3,0);
    $arr[1][1]=1;
    echo str_pad(" ",$n*12," ");
    printf("%3d",$arr[1][1]);
    echo "
";
    for($i=2;$i<=$n;$i++){
      $arr[$i]=array_fill(0,($i+2),0);
      for($j=1;$j<=$i;$j++){
        if($j==1)
          echo str_pad(" ",($n+1-$i)*12," ");
        printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);
        echo "  ";
      }
      echo"
";
    }
  }
}
$yh=new T('3'); //$yh=new T(数量);
$yh->display();
?>

4.冒泡排序

function maopao($arr){
    $len = count($arr); 
    for($k=0;$k<=$len;$k++)
    {
        for($j=$len-1;$j>$k;$j--){
          if($arr[$j]<$arr[$j-1]){
            $temp = $arr[$j];
            $arr[$j] = $arr[$j-1];
            $arr[$j-1] = $temp;
          }
        }
    }
    return $arr;
}

5.快速排序

function quickSort($arr) {
    //先判断是否需要继续进行
    $length = count($arr);
    if($length <= 1) {
        return $arr;
    }
    //选择第一个元素作为基准
    $base_num = $arr[0];
    //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
    //初始化两个数组
    $left_array = array();  //小于基准的
    $right_array = array();  //大于基准的
    for($i=1; $i<$length; $i++) {
        if($base_num > $arr[$i]) {
            //放入左边数组
            $left_array[] = $arr[$i];
        } else {
            //放入右边
            $right_array[] = $arr[$i];
        }
    }
    //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
    $left_array = quickSort($left_array);
    $right_array = quickSort($right_array);
    //合并

    return array_merge($left_array, array($base_num), $right_array);
}

6.二分查找算法（半查找算法）

function binsearch($x,$a){
    $c=count($a);
    $lower=0;
    $high=$c-1;
    while($lower<=$high){
        $middle=intval(($lower+$high)/2);
        if($a[$middle]>$x){
            $high=$middle-1;
        } elseif($a[$middle]<$x){
            $lower=$middle+1;
        } else{
            return $middle;
        }
    }
    return false;
}

7.PHP奇怪的算法

function test(){
 $a=1;
 $b=&$a;
 echo (++$a)+(++$a);
}
test();

PHP 7 以下版本返回 6，而 PHP 7 返回 5，这确实很奇怪。我的底层算法很差，所以我认为是 PHP 7 以下版本的 BUG。

8.字符集：输入一个字符串，找出该字符串所含的字符集，并按顺序排序（英文）

function set($str){
    //转化为数组
    $arr = str_split($str);
    //去除重复
    $arr = array_flip(array_flip($arr));
    //排序
    sort($arr);
    //返回字符串
    return implode('', $arr);
}

9.遍历某个文件下的所有文件及子文件夹

function AllFile($dir){
    if($dh = opendir($dir)){
        while (($file = readdir($dh)) !== false){
            if($file !='..' && $file !='.'){
                if(is_dir($dir.'/'.$file)){
                    AllFile($dir.'/'.$file);  //如果判断还是文件，则递归
                }else{  
                    echo $file;            //输出文件名
                }
            }
        } 
    }
}

10. 从标准 URL 中提取文件扩展名

function getExt($url)
  {
    $arr = parse_url($url);
    $file = basename($arr['path']);// basename函数返回路径中的文件名部分
    $ext = explode('.', $file);
    return $ext[count($ext)-1];

  }

11. 一个人想爬一段有 n 级台阶的楼梯，每次他只能走 1 级或 2 级台阶，请问他有多少种爬上所有台阶的方法？比如总共有 3 级台阶，他可以先走 1 级台阶再走 2 级台阶，或者先走 2 级台阶再走 1 级台阶，或者走 1 级台阶 3 次，一共有 3 种方法。

function jieti($num){    //实际上是斐波那契数列
    return $num<2?1:jieti($num-1)+jieti($num-2);
}

12.请写一段PHP代码，保证多个进程能同时成功写入同一个文件

    $fp = fopen("lock.txt","w+");
    if (flock($fp,LOCK_EX)) {
        //获得写锁，写数据
        fwrite($fp, "write something");

        // 解除锁定
        flock($fp, LOCK_UN);
    } else {
        echo "file is locking...";
    }
    fclose($fp);
?>

13. 无限分类

function tree($arr,$pid=0,$level=0){
    static $list = array();
    foreach ($arr as $v) {
        //如果是顶级分类，则将其存到$list中，并以此节点为根节点，遍历其子节点
        if ($v['pid'] == $pid) {
            $v['level'] = $level;
            $list[] = $v;
            tree($arr,$v['id'],$level+1);
        }
    }
    return $list;
}

14. 获取上个月的第一天和最后一天

//获取上个月第一天
    date('Y-m-01',strtotime('-1 month'));

    //获取上个月最后一天
    date('Y-m-t',strtotime('-1 month'));

15.随机输入一个数字，查询对应的数据区间

//把区间换成数组写法，用二分法查找区间
function binsearch($x,$a){  
    $c=count($a);  
    $lower=0;  
    $high=$c-1;  
    while($lower<=$high){  
        $middle=intval(($lower+$high)/2);  
        if($a[$middle]>=$x){  
            $high=$middle-1;
        }elseif($a[$middle]<=$x ){  
            $lower=$middle+1;
        }   
    }

    return '在区间'.$a[$high].'到'.$a[$lower];  
}

$array  = ['1','50','100','150','200','250','300'];
$a = '120';
echo binsearch($a,$array);

16. 现在有一个字符串，你需要对这个字符串进行 n 次操作，每次操作都会给出两个数字：(p, l) 表示从当前字符串中下标为 p 的字符开始，长度为 l 的子字符串。你需要将这个子字符串左右翻转，然后直接插入到子字符串的原始位置之后。最终的字符串是什么？字符串的下标从 0 开始。你可以从示例中获取更多信息。

每个测试用例只包含一组数据。每组数据的第一行是原始字符串，长度不超过 10 个字符且只包含大小写字符和数字。接下来会有一个数字 n，表示有 n 个操作，接下来会有 n 行，每行两个整数，表示每个操作的 (p, l)。

保证输入操作合法，并且最终字符串长度不超过1000。

class TestKeenSting{
    private $str;

    public function __construct($str)
    {
        $this->str = $str;
    }

    public function run($orders)
    {
        foreach($orders as $item)
        {
            $this->execute($item[0],$item[1]);
        }
        return $this->str;
    }

    private function execute($pos,$length)
   {
        $len = strlen($this->str);
        if(($length-$pos) > $len)
            exit(1);
        else
            $tmp_str = substr($this->str,$pos,$length);
        $s1 = substr($this->str,0,$pos+$length);
        $s2 = substr($this->str,$pos+$length);
        $dest_str = $this->str_reverse($tmp_str);
        $this->str = $s1.$dest_str.$s2;
    }

   private function str_reverse($str)
    {
        $len = strlen($str);
      if($len%2 == 0)
            $times = $len/2;
        else
            $times = ($len-1)/2;

      for($i=0;$i<$times;$i++)
        {
            $t = $str[$len-1-$i];
            $str[$len-1-$i] = $str[$i];
            $str[$i] = $t;
        }

        return $str;
   }


}


$a = new TestKeenSting('ab');
$re = $a->run([[0,2],[1,3]]);
echo $re;

17. 作为一名出道歌手，你终于要发行自己的第一张专辑了。你计划收录n首歌曲，每首歌曲时长s秒。每首歌曲必须收录在一张CD中。每张CD的容量为L秒，你必须保证同一张CD上相邻两首歌曲之间至少有1秒的间隔。为了避邪，你决定任何一张CD上的歌曲数都不能被13整除。那么你需要多少张CD才能发行这张专辑呢？

每组测试用例仅包含一组数据，每组数据第一行是三个正整数n,s,L，保证n≤100，s≤L≤10000

class TestKeenSting{
    private $song_num;
    private $song_size;
    private $cd_size;

    public function __construct($n,$s,$l)
    {
        if($n>100 || $s>$l)
            exit('input error!');
        $this->song_num = $n;
        $this->song_size = $s;
        $this->cd_size = $l;
    }


    public function run()
    {
        $cd_container = $this->calculate_single_cd();
        return ceil($this->song_num/$cd_container);
    }

    private function calculate_single_cd()
    {
        //假设一张cd可以放n个 song_length+1
        $n = floor($this->cd_size / ($this->song_size + 1));
        //对剩余空间做判断
        $gap = $this->cd_size - $n * ($this->song_size + 1);
        if($gap == $this->song_size)//剩余空间是否刚好可以放一首歌
            if($n!=12)//已经放了12首歌,不要这最后的一首
                $n += 1;
        else
            if($n == 13) //如果之前就已经可以放13首,放弃一首
                $n = 12;
        return $n;
    }



}


$a = new TestKeenSting(7,2,6);
$re = $a->run();
echo $re;

18 使用 PHP 实现双向队列

    class Deque{
    private $queue=array();
    public function addFirst($item){
        return array_unshift($this->queue,$item);
    }

    public function addLast($item){
        return array_push($this->queue,$item);
    }
    public function removeFirst(){
        return array_shift($this->queue);
    }

    public function removeLast(){
        return array_pop($this->queue);
    }
}
?>

19 请使用冒泡排序法对以下一组数据进行排序：10 2 36 14 10 25 23 85 99 45。

    // 冒泡排序
    function bubble_sort(&$arr){
        for ($i=0,$len=count($arr); $i < $len; $i++) {
            for ($j=1; $j < $len-$i; $j++) {
                if ($arr[$j-1] > $arr[$j]) {
                    $temp = $arr[$j-1];
                    $arr[$j-1] = $arr[$j];
                    $arr[$j] = $temp;
                }
            }
        }
    }

    // 测试
    $arr = array(10,2,36,14,10,25,23,85,99,45);
    bubble_sort($arr);
    print_r($arr);
?>

20. 编写一个排序算法（写出代码）并解释如何优化它。

    //快速排序
    function partition(&$arr,$low,$high){
        $pivotkey = $arr[$low];
        while($low<$high){
            while($low < $high && $arr[$high] >= $pivotkey){
                $high--;
            }
            $temp = $arr[$low];
            $arr[$low] = $arr[$high];
            $arr[$high] = $temp;
            while($low < $high && $arr[$low] <= $pivotkey){
                $low++;
            }
            $temp=$arr[$low];
            $arr[$low]=$arr[$high];
            $arr[$high]=$temp;
        }
        return$low;
    }


function quick_sort(&$arr,$low,$high){
    if($low < $high){
        $pivot = partition($arr,$low,$high);
        quick_sort($arr,$low,$pivot-1);
        quick_sort($arr,$pivot+1,$high);
    }
}
?>

21 改组算法

    $card_num = 54;//牌数
    function wash_card($card_num){
        $cards = $tmp = array();
        for($i = 0;$i < $card_num;$i++){
            $tmp[$i] = $i;
        }

        for($i = 0;$i < $card_num;$i++){
            $index = rand(0,$card_num-$i-1);
            $cards[$i] = $tmp[$index];
            unset($tmp[$index]);
            $tmp = array_values($tmp);
        }
        return $cards;
    }
    // 测试：
    print_r(wash_card($card_num));
?>

【程序一】题目：经典问题：有一对兔子，从出生第三个月开始，每个月产下一对兔子，第四个月之后，每个月又产下一对兔子，如果兔子都没有死，那么每个月一共有多少只兔子？

1、程序分析：兔子的图案是序列1,1,2,3,5,8,13,21....

2表示第三个数字是前两个数字的总和，这是经典的斐波那契数列。

    function actionFblist($n)
    {
        // 1,1,2,3,5,8,13
    // $n 为第n个月
        $arr = [1,1];
        if($n < 2)
            return false;


        for ($i=2;$i<=$n+1;$i++)
        {
            $arr[$i] = $arr[$i-1] + $arr[$i-2];
        }
        var_dump($arr);
        echo $arr[$n+1];
    }

【程序2】 题目：判断101-200之间有多少个素数，并输出所有素数。

1.程序分析：判断素数的方法：用一个数分别除以2和sqrt（这个数）。如果能被整除，

说明这个数不是质数，否则就是质数。

public function actionIsPrimeNumber()
{
    $arr = [];
    for ($i=101;$i<=200;$i++)
    {
        $flag = true;
        for ($j = 2;$j<=sqrt($i);$j++)
        {
            if($i % $j == 0)
            {
                $flag = false;
            }
        }

        if($flag == true)
            $arr[] = $i;
    }
    var_dump($arr);
}

【程序3】 题目：打印出所有的“水仙花数”。“水仙花数”是指一个三位数，其立方数等于其本身。例如，153 是一个“水仙花数”，因为 153=1 的立方 + 5 的立方 + 3 的立方。

1、程序分析：用for循环控制100~999之间的数字，并将每个数分解为个位、十位、百位。

public function actionWaterFlower()
{
    $re = [];
    for($i = 100;$i<= 999;$i++)
    {
        $hundred = floor($i / 100 );     // 获取百位数字
        $ten = floor(($i %100 ) / 10 );  // 获取十位数字
        $one = floor($i % 100 % 10);     // 获取各位数字

        if((pow($hundred,3)  + pow($ten,3) + pow($one,3) ) == $i )
        {
            $re[] = $i;
        }
    }
    var_dump($re);

}

【程序4】标题：使用嵌套条件运算符完成此问题：学业成绩>=90分的学生用A表示，学业成绩在60-89分之间的学生用B表示，学业成绩低于60分的学生用C表示。

1.程序分析：(a> b)?a:b 这是条件运算符的一个基本例子。

public function actionGetScore()
{
    $score = 90;
    if($score <0 || $score > 100)
        return false;

    $re = $score >= 90 ? 'A' : ($score >= 60 ?  'B' :'C');
    var_dump($re);
}

【程序5】 问题：求s=a+aa+aaa+aaaa+aa...a的值，其中a为数字。如2+22+222+2222+22222（有5个数字需要相加），几个数字的相加由键盘控制。

1.程序分析：关键是循环计算每一项的值。

2.您可以使用 PHP 函数

  public function actionRepeatN()
    {
        $a = 8;
        $n = 8;
        $sum = 0;

        for ($i = 0;$i<$n;$i++)
        {
            $num = 0;
            for ($j = 0;$j<=$i;$j++)
            {
                $num += $a* pow(10,$j);
            }
            $sum += $num;
        }
        var_dump($sum);
    }

【程序6】问题：一个整数，加100后是一个完全平方数，加168后又是一个完全平方数，这个整数是多少？

1、程序分析：判断10万以内，先把数字加100然后取平方根，再把数字加268然后取平方根，如果平方根后的结果满足以下条件，就是结果，请看详细分析：

一开始我不知道如何判断一个数是否是完全平方数，但是根据PHP的基本函数sqrt、pow可以间接判断。

如果将平方根四舍五入后再平方为原始数字，那么该数字就是完全平方数。

public function actionWhitchNum()
{
    for ($i=1;$i<=100000;$i++)
    {
        if(pow((int)sqrt($i+100),2) == ($i+100) &&pow((int)sqrt($i+168),2) == ($i+168) )
        {
            echo $i;
        }
    }
    echo 'ok';
}

【程序7】 问题：输入某一年月日，判断今天是一年中的哪一天？

1、程序分析：以3月5日为例，我们要先把前两个月的月份相加，然后再加上5天，也就是一年中的天数。特殊情况，如果是闰年，输入的月份大于3，就需要考虑多加一天。刚看到这道题的时候，以为有简单的办法，没想到没有别的办法，只好用这种方法了。

public function actionToday()
{
    $today = '2018-03-05'; // 格式固定
    $days = explode('-',$today);
    $year = $days[0];
    $month = (int)$days[1];
    $day = (int)$days[2];

    // 判断是否为闰年
    $flag = false;
    if($year%400==0||($year%4==0&&$year%100!=0))
    {
        $flag = true;
    }

    // 对月份进行判断 1,3,5,7,8,10,12 为31天
    // 4,6,9,11 为30天
    // 2月份闰年为29天,否则为28天
    switch ($month)
    {
        case 1:
            $sum = 0;break;
        case 2:
            $sum = 31;break;
        case 3:
            $sum = 59;break;
        case 4:
            $sum=90;break;
        case 5:
            $sum=120;break;
        case 6:
            $sum=151;break;
        case 7:
            $sum=181;break;
        case 8:
            $sum=212;break;
        case 9:
            $sum=243;break;
        case 10:
            $sum=273;break;
        case 11:
            $sum=304;break;
        case 12:
            $sum=334;break;
        default:
            break;
    }

    $sum = $sum + $day;
    if($flag && $month>2)
        $sum = $sum + 1;

    var_dump($sum);

}

【程序8】 标题：输入三个整数x,y,z，从小到大输出。

1.程序分析：我们尝试将最小的数字放在x上。首先，将x与y进行比较。如果x> y，则交换x和y的值。然后比较x与z。如果x> z，则交换x和z的值。这将使x最小化。

排序这里不作为考察点，排序可以用冒泡，快速，插入等排序算法，这里用了三种变量交换的方式，感觉这个才是重点。

public function actionSortX()
{
    $x = 6;
    $y = 53;
    $z = 6;
    if($x>$y) // $y<$x
    {
        $x = $x+$y;
        $y = $x-$y;
        $x = $x-$y;
    }
    if($x>$z)
    {
        $tmp = $x;
        $x = $z;
        $z = $tmp;
    }

    if($y>$z)
    {
        $tmp = $y . '-' .$z;
        $tmp = explode('-',$tmp);
        $y = $tmp[1];
        $z = $tmp[0];
    }
    echo $x,',',$y,',',$z;
}

【程序9】 标题：输出9*9的公式。

1.程序分析： 考虑行和列，一共有9行9列，i控制行，j控制列。

public function actionMultiplicationTable()
{
    for ($i=1;$i<=9;$i++)
    {
        for ($j=1;$j<=$i;$j++)
        {
            echo $j . '*' .$i .'=' . $i*$j;
            echo ' ';
        }
        echo "
";
    }
}

【程序10】 问题：有一个分数数列：2/1，3/2，5/3，8/5，13/8，21/13......，求这个数列前20项的和。

1、程序分析：请掌握分子和分母的变化规律。

public function actionAddFraction()
{
    $sum = 0;
    $numerator = [2,3];
    $denominator = [1,2];
    // 根据规律获得所有的分子和分母
    for ($i=2;$i<20;$i++)
    {
        $numerator[$i] = $numerator[$i-2] + $numerator[$i-1];
        $denominator[$i] = $denominator[$i-2] + $denominator[$i-1];
    }
    // 获得分数的前n项和
    for ($i=0;$i<20;$i++)
    {
        $sum += $numerator[$i] / $denominator[$i];
    }
    var_dump($sum);
}

【程序11】 问题：求1+2!+3!+…+20!的和。

1.程序分析：该程序只是将加法变成了乘法。

public function actionAddFactorial()
{
    $n = 20;
    $sum = 0;
    for ($i=1;$i<=$n;$i++)
    {
        $num = 1;
        for ($j=1;$j<=$i;$j++)
        {
            $num = $j*$num;
        }
        $sum += $num;
    }
    var_dump($sum);
}

【程序12】 标题：利用递归找出5！。

1.程序分析： 递归公式：fn=fn_1*4!

public function numFactorial($n)
{
    if($n>1)
        return $sum = $n * $this->numFactorial($n-1);   // 需要注意这点,若是写成函数要替换成函数形式
    else
        return $n;
}
public function actionNumFactorial()
{
    $n =4;
    $sum =  $this->numFactorial($n);                   // 调用上面的阶乘方法(函数)
}

【程序13】 问题：有5个人坐在一起，第5个人几岁？他说他比第4个人大2岁。当问第4个人几岁的时候，他说他比第3个人大2岁。当问第3个人时，他说他比第2个人大2岁。当问第2个人时，他说他比第1个人大2岁。最后，当问第1个人时，他说他10岁。第5个人几岁？

1.程序分析：采用递归的方法，递归分为回推和递归两个阶段。要知道第五个人的年龄，就需要知道第四个人的年龄，以此类推，推到第一个人（10岁），然后再回推。

public function myAge($n)
{
    if($n == 1)
        return $age = 10;
    else
        return 2 + $this->myAge($n-1);
}

public function actionMyAge1()
{
    $n = 5;
    echo $this->myAge($n);
}

[程序14] 标题：给定一个不超过5位数字的正整数，要求完成以下任务：1.找出它有多少位数字，2.按相反的顺序打印出这些数字。

public function actionIntLength()
{
    $num = 1232345;
    $num = (string) $num;
    $length = strlen($num);
    $numstring = '';
    for ($i=$length-1;$i>=0;$i--)
    {
        $numstring .= $num[$i];
    }
    echo $numstring;
}

【程序15】 问题：判断一个5位数是否是回文数。即12321是回文数，个位数字与万位数字相同，十位数字与千位数字相同。

public function actionIsPalindromeNumber()
{
    $num = 12321;
    $num = (string) $num;
    if($num[0] == $num[4] && $num[1] == $num[3])
        var_dump('Is Palindrome Number');
    else
        echo 'false';
}

/*
 * 找到所有的5位的回文数
 * */
public function actionAllPalindromeNumber()
{
    $result = [];
    for ($i=10000;$i<99999;$i++)
    {
        $i = (string) $i;
        if($i[0] == $i[4] && $i[1] == $i[3])
            $result[] = $i;
    }
    var_dump($result);
}

文章参考：

以上就是本文的全部内容，希望对大家的学习有所帮助，下面是一些免费课程的整理分享，长按二维码即可获取你想要的课程。

让学习成为一种习惯

长按二维码获取

经验 | 方法 | 访谈 | 文章