-
编程思想：如何利用数学模式，来解决对应的需求问题；然后利用代码实现对应的数据模型（逻辑）。
-
算法：使用代码实现对应的数学模型，从而解决对应的业务问题。
递推算法
递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。
- 顺推：通过最简单的条件（已知），然后逐步推演结果
- 逆推：通过结果找到规律，然后推到已知条件
🌰斐波那契数列：1 1 2 3 5 8 13 …，通常需求：请求得指定位置N所对应的值是多少 ?
找规律： 1、 第一个数是1 2、 第二个数也是1 3、 从第三位开始：属于前两个数的和
代码解决思路： 1、 如果数字位置为1和2，结果都是1 2、 从第三个开始，想办法得到前两个的结果，就可以得到
终极解决办法：想办法把要求的位置之前的所有的值都列出来，那么要求的数就可以通过前两个之和计算出来：使用数组存储所有结果即可。
//需求：规律1 1 2 3 5 ...
//求出指定位数对应的值
function my_recursive($des){
//已知条件：第一个和第二个数都为1，第三个开始为前两个之和
if($des==1||$des==2)return 1;
$arr[1]=1;
$arr[2]=1;
for($i=3;$i<=$des;$i++){
$arr[$i]=$arr[$i-1]+$arr[$i-2];
echo '<pre>';
print_r($arr[$i]);
}
//返回最后一个位置的结果
return $arr[$des];
}
print_r('<hr><b>'.my_recursive(15));
🍎
2
3
5
8
13
21
34
55
89
144
233
377
610
----------------------------------
610
递归算法
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。
- 简化问题：找到最优子问题（不能再小）
- 函数自己调用自己
🌰斐波那契数列：1 1 2 3 5 8 13 … 需求：求指定位置的数列的值 ; 规律：第一个和第二个为1，从第三个开始为前两个之后
F(N) = F(N-1) + F(N-2); F(N-1) = F(N-2) + F(N - 3); … F(2) = F(1) = 1;
- 递归思想中：有两个非常重要的点
- 递归点：发现当前问题可以有解决当期问题的函数，去解决规模比当前小一点的问题来解决 F(N) = F(N - 1) + F(N - 2);
- 递归出口：当问题解决的时候，已经到达（必须有）最优子问题，不能再次调用函数
✨如果一个函数递归调用自己而没有递归出口：就是死循环 递归的本质是函数调用函数：一个函数需要开辟一块内存空间，递归会出现同时调用N多个函数（自己）：递归的本质是利用空间换时间
//递归一定有函数
function recursion($n){
//递归出口
if($n == 1 || $n == 2) return 1;
//递归点：求N的值，与求N-1的值一模一样，只是N-1的规模比N小
return recursion($n - 1) + recursion($n - 2);
}
//调用
echo recursion(15);
冒泡排序(最简单)
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
冒泡排序的算法思路：
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。🐖
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
//bubble sort
function bubbleSort(&$arr){
for($i=0,$len=count($arr);$i<=$len-1;$i++){
for($j=0;$j<$len-1;$j++){//👉 优化 for($j=0;$j<$len-1-$i;$j++){
if($arr[$j]>$arr[$j+1]){
$temp=$arr[$j];
$arr[$j]=$arr[$j+1];
$arr[$j+1]=$temp;
}
}
}
return $arr;
}
$arr = array(8,6,2,9,1,5,7);
//执行函数
bubbleSort($arr);
echo '<pre>';
print_r($arr);
🍎
Array
(
[0] => 1
[1] => 2
[2] => 5
[3] => 6
[4] => 7
[5] => 8
[6] => 9
)
🌴内循环挨个比较替换值,外部循环控制替换个数,执行效率低
选择排序
- 比冒泡排序效率较高
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素， 存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
选择排序的算法思路：
1. 假设第一个元素为最小元素，记下下标。
2. 寻找右侧剩余的元素，如果有更小的，重新记下最新的下标。
3. 如果有新的最小的，交换两个元素。
4. 往右重复以上步骤，直到元素本身是最后一个。
$arr = array(1,5,2,9,6,3,4);
//1、 确定要交换多少次：一次只能找到一个最小的，需要找数组长度对应的次数
for($i = 0,$len = count($arr);$i < $len;$i++){
//2、假设当前第一个已经排好序
$min = $i; //当前第一个数是最小的
//3、拿该最小的取比较剩余的其他
for($j = $i + 1;$j < $len;$j++){
//4、比较：比较当前元素与选定的最小的元素
if($arr[$j] < $arr[$min]){
//说明当前指定的$min不合适
$min = $j;
}
}
//5、交换当前选定的值与实际最小的元素值
if($min != $i){
$temp = $arr[$i];
$arr[$i] = $arr[$min];
$arr[$min] = $temp;
}
}
echo '<pre>';
print_r($arr);
🍎
Array
(
[0] => 1
[1] => 2
[2] => 5
[3] => 6
[4] => 7
[5] => 8
[6] => 9
)
🌴相对于冒泡排序效率高,因为内循环只处理找到最小值索引,而没有其他操作;具有不稳定性,如果数组中有重复的值存在,会出现重复值移动的现象,影响效率。
插入排序
插入排序（Insert sort）,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。 插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
插入排序的算法思路：
1. 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
2. 设置开始查找的位置j；
3. 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
4. 将r[0]插入r[j+1]的位置上。
1、 认定第一个元素已经排好序；
2、 取出第二个元素，作为待插入数据；
3、 与已经排好序的数组的最右侧元素开始进行比较
4、 如果后面的小于前面的：说明前面已经排好序的那个数组元素不在对的位置（向后移一个），然后让新的元素填充进去（继续向前比：高级）
5、 重复前面的步骤：直到当前元素插入到对位置；
6、 重复以上步骤，直到所有的数组元素都插入到对的位置。
//todo 2019-10-17 15:30:14 头大...https://www.bilibili.com/video/av12863134/?p=93
🌴稳定的排序方法,适用于少量数据
🌴
🌴