基础算法示例

二分查找
快速排序
桶排序
鸽巢排序
希尔排序
平衡树
二叉树
红黑树

杨辉三角

查看百度百科解释

名词解释 杨辉三角是二项式系数在三角形中的一种几何排列，1654年欧洲的帕斯卡也发现了这个规律，所以也叫帕斯卡三角形。

杨辉三角规律：
第n行的数字有n项
第n行的数字和为 $2^{n-1}$
每行数字左右对称，由1逐渐增大
每个数字等于上一行的左右两个数字之和。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这是组合数的性质之一，即C(n+1,i) = C(n,i)+C(n,i-1)

代码实现-PHP

<?php
//杨辉三角行数
$row = 10;
//一共 $row 行，每一行的第一个数和每一行的最后一个数为1
for ($i = 0; $i < $row; $i++) {
    $a[$i][0] = 1;
    $a[$i][$i] = 1;
}
// C(n+1,i) = C(n,i)+C(n,i-1)
for ($i = 2; $i < $row; $i++) {
    for ($j = 1; $j < $i; $j++) {
        $a[$i][$j] = $a[$i - 1][$j - 1] + $a[$i - 1][$j];
    }
}
// 打印
for ($i = 0; $i < $row; $i++) {
    for ($j = 0; $j <= $i; $j++) {
        echo $a[$i][$j].'&nbsp;';
    }
    echo "<br/>";
}

金字塔

参考博客效果

    *
   ***
  *****
 *******
*********

代码实现

<?php
$n = 5; //金字塔行数
for ($i = 1; $i <= $n; $i++) {
    //在打印*之前，先打印空格
    for ($k = 1; $k <= $n - $i; $k++) {
        echo " ";
    }
    //内层控制每层*的个数
    for ($j = 1; $j <= 2 * $i - 1; $j++) {
        echo "*";
    }
    echo "<br/>";
}

斐波那契数列

查看百度百科解释

名词解释 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

代码实现-PHP

求解兔子数列,12个月后有多少只兔子

<?php
$k = 12; //十二个月
echo $k1 = 1; //记录上个月兔子数量
echo ",";
$k2 = 0; //记录上上个月兔子数量
$sum = 0; //总和
for ($i = 1; $i < $k; $i++) {
    $sum = $k1 + $k2; //当月的兔子和
    $k2 = $k1; //上个月的兔子赋值给上上个月记录
    echo $k1 = $sum;
    echo ","; //当月的兔子赋值给上个月jilu
}
// echo $sum;
//在for循环里面输出 $k1 是将整个斐波那契额数列输出，最后for循环结束后输出 $sum 是斐波那契数列第十二个数即12个月后有多少个兔子

二分查找

定义

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

要求

满足该算法的要求必须如下两点：

必须采用顺序存储结构。
必须按关键字大小有序排列。

步骤

其实，二分查找也还是比较容易理解的，大概就是一分为二，然后两边比较，保留有效区间，继续一分为二查找，直到找到或者超出区间则结束，所以二分查找的基本步骤是：

1、确定要查找的区间

2、确定要二分时的参照点

3、区间内选取二分点

4、根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间

5、继续在有效区间重复上面的步骤

源码

非递归实现

**展开查看源码**

  /**
  * 二分查找算法
  * @param array $arr 待查找区间
  * @param int $number 查找数
  * @return int        返回找到的键
  */
  function binary_search($arr, $number) {
      // 非数组或者数组为空，直接返回-1
      if (!is_array($arr) || empty($arr)) {
          return -1;
      }
      // 初始变量值
      $len = count($arr);
      $lower = 0;
      $high = $len - 1;
      // 最低点比最高点大就退出
      while ($lower <= $high) {
          // 以中间点作为参照点比较
          $middle = intval(($lower + $high) / 2);
          if ($arr[$middle] > $number) {
              // 查找数比参照点小，舍去右边
              $high = $middle - 1;
          } else if ($arr[$middle] < $number) {
              // 查找数比参照点大，舍去左边
              $lower = $middle + 1;
          } else {
              // 查找数与参照点相等，则找到返回
              return $middle;
          }
      }
      // 未找到，返回-1
      return -1;
  }

非递归实现

**展开查看源码**

  /**
  * @param array $arr 待查找区间
  * @param int $number 查找数
  * @param int $lower 区间最低点
  * @param int $high 区间最高点
  * @return int
  */
  function binary_search_recursion(&$arr, $number, $lower, $high) {
      // 以区间的中间点作为参照点比较
      $middle = intval(($lower + $high) / 2);
      // 最低点比最高点大就退出
      if ($lower > $high) {
          return -1;
      }
      if ($number > $arr[$middle]) {
          // 查找数比参照点大，舍去左边继续查找
          return binary_search_recursion($arr, $number, $middle + 1, $high);
      } elseif ($number < $arr[$middle]) {
          // 查找数比参照点小，舍去右边继续查找
          return binary_search_recursion($arr, $number, $lower, $middle - 1);
      } else {
          return $middle;
      }
  }

算法的使用

需求是在一个排列好的区间（$arr）中，查找一个数（$number）的所在位置，所以，调用算法查找如下：

// 待查找区间
$arr = [1, 3, 7, 9, 11, 57, 63, 99];
// 非递归查找57所在的位置
$find_key = binary_search($arr, 57);
// 递归查找57所在的位置
$find_key_r = binary_search_recursion($arr, 57, 0, count($arr));
// 输出打印
print_r($find_key);
print_r($find_key_r);

时间复杂度分析

在有序数组中如果用暴力的算法去查找，也就是逐个遍历比较，那么时间复杂度是O(n)；但是，用二分查找后，因为每次可以舍去一半查找区间，所以会将时间复杂度减少到O(logn)，算法更优。

杨辉三角​

金字塔​

斐波那契数列​

二分查找​

杨辉三角

金字塔

斐波那契数列

二分查找