​

�?� 用 PHP 的方式实现的�?�类算法�??集 �?�

English　

每周最少一更，求出�?，求�?待 At least once a week, ask for problems and abuse

简�?�结构

├──Package
│    ├── Sort  排序篇
│    │    ├── BubbleSort.php          冒泡排序
│    │    ├── HeapSort.php            堆排序   大根堆
│    │    ├── MBaseSort.php           基数排序 MSD
│    │    ├── LBaseSort.php           基数排序 LSD
│    │    ├── QuickSort.php           快速排序
│    │    ├── ShuttleSort.php         飞梭排序
│    │    ├── ShellSort.php           希尔排序
│    │    ├── MergeSort.php           归并排序
│    │    ├── InsertSort.php          插入排序
│    │    └── SelectSort.php          选择排序
│    │
│    ├── Query 查找篇
│    │    ├── BinaryQuery.php         二�?�查找
│    │    ├── InseertQuery.php        插入查找
│    │    ├── FibonacciQuery.php      �?波那契查找
│    │    ├── BFSQuery.php            广度�?�?查找
│         ├── Kmp.php                 算法导论-KMP算法
│         ├── DijkstraQuery.php       迪克斯特拉算法
│    │    └── QulickQuery.php         快速查找
│    │     
│    ├── Structure 数据结构
│    │    ├── StackExample.php         堆�?   �?进�?�出 LIFO (Last In First Out)
│    │    ├── LinearChain.php          线性表 单链�?储
│    │    └── LinearOrder.php          线性表 顺序�?储
│    │    └── BinarySearchTree.php     二叉�?�索树  
│    │     
│    ├── Tools 小工具集
│    │    └──  SystemSwitch.php       堆�?实现进�?�转换  
│    │  
│    └── Other 其他
│         ├──  MonkeyKing.php         约瑟夫环
│         ├──  DynamicProgramming.php 动�?规�?�
│         ├──  Fibonacci.php          �?波那契数�?�
│         ├──  StealingApples.php     �?�苹果求余
│         ├──  HanoiGames.php         汉诺塔游�?�
│         ├──  BidirectionalQueue.php 双�?��?��?�
│         ├──  ColorBricks.php        彩色砖块
│         ├──  GetCattle.php          牛年求牛
│         ├──  OnlyNumbers.php        求唯一数
│         ├──  PokerGames.php         洗扑克牌
│         ├──  Interval.php           抽奖区间算法
│         ├──  Maze.php               迷宫寻址算法
│         ├──  AntsClimb.php          蚂�?�?�杆算法
│         ├──  Encryption.php         对称加密算法
│         ├──  ElevatorDispatch.php   编程之美-电梯�?度算法
│         ├──  PointInTriangle.php    �?�量叉集计算点�?��?�在三角形中
│         ├──  TraversalOfBinary.php  二叉树非递归�?�历算法实现
│         ├──  Knapsack.php           贪�?算法之�?�包问�?实现
│         └──  BigSmallReplace.php    Hello World 输出 Olleh Dlrow
│         └──  Solution.php           Facebook面试�?之岛屿周长算法
│         └──  RotationSort.php       Facebook面试�?之顺时�?回旋算法
│         └──  Square.php             Facebook面试�?之�?�断四个点�?��?�组�??正方形算法
│         └──  Prim.php               Prim算法(最小生�??树算法)
│         └──  CartesianProduct.php   笛卡尔积算法
│         └──  Square.php             面试�?之平面任意四点�?��?�组�??一个矩形
│         └──  Judge.php              面试�?之扑克牌中任选五张�?�断�?�不�?�顺�?
│         └──  Factorial.php          面试�?之N的�?��?末尾有多少个0
|         └──  HashTable.php          HashTable
|         └──  RotateSort.php         面试�?之风车旋转排序算法
│     
├──LICENSE
└──README.md

�?�?�什�?？

记录自己�?�解算法，数据结构的过程，尽可�?�的简单全面以及详细，让算法学习�?用�?�活自如，加油(ง •̀_•�?)ง

当然

用 PHP 实现算法并替代�?方�?供的函数�?�愚蠢的事�?� .但这决不代表斟酌算法就�?�件无意义的事 , 每个算法�?��?�一种思�?�的结晶 , 学习�?秀的思�?� , 开拓思维

什�?�?�算法？

直白地说，算法就�?�任何�?�确定义的计算过程，�?接收一些值�?�集�??作为输入，并产生一些值�?�集�??作为输出。这样，算法就�?�将输入转换为输出的一系�?�计算过程。来�?：Thomas H. Cormen, Chales E. Leiserson (2009), 《算法导论第三�?》。

简而言之，�?�们可以说算法就�?�用来解决一个特定任务的一系�?�步骤�?�?�的，不止计算机在使用算法，人类也�?�样如此）。目前，一个有�?的算法应该�?�有三个重�?特性：

• �?必须�?�有�?的：如果你设计的算法永无休止地尝试解决问�?，那�?�?�?�无用的。
• �?必须具备�?�确定义的指令：算法的每一步�?�必须准确定义，在任何场景下指令�?�应当没有歧义。
• �?必须�?�有�?的：一个算法被设计用以解决�?个问�?，那�?�?就应当�?�解决这个问�?，并且仅仅使用纸和笔就�?��?�?�该算法�?�收敛的。

对数

log₁₀100 相当于问"将多少个10相�?的结果为100"，答�?当然�?�2个了 因此log₁₀100=2，即对数�?算�?�幂�?算的逆�?算

�?行时间

以二�?�查找为例，使用�?可节�?多少时间呢？简单查找�?个地检查数字，如果�?�表包�?�100个数字，最多需�?猜100次。 换而言之最多需�?猜测的次数与�?�表长度相�?�，这被称为线性时间(linear time)，而二�?�查找�?�不�?�，如果�?�表包�?�100个�?素 最多需�?7次，如果�?�表包�?�40亿个数字，最多需猜32次，而�?�查找的�?行时间为对数时间 O(log)

大O表示法

大O表示法�?�一种特殊的表示法 ，指出了算法的速度有多快。有个屌用啊，实际上，你经常�?去复�?��?�人的代�?。 在这种�?�况下，知�?�这些算法的速度有快有慢

• 算法的�?行时间以不�?�的速度增加
  • 例如简单查找与二�?�查找的区�?�

• 大O表示法指出了算法有多快，例如�?�表包�?�n个�?素，简单查找需�?检查每个�?素，因此需�?执行n次操作 使用大O表示法这个�?行时间为O(n),二�?�查找需�?执行log_n次操作，使用大O表示为O(log n)
  • 一些常�?的大O�?行时间
• O(log n) ,也叫对数时间，这样的算法包括二�?�算法
• O(n),也叫线性时间，这样的算法包括简单查找。
• O(n * log n) 快速排序
• O(n₂),选择排序
• O(n!) 即�?��?时间
  • 这里�?�重点
• 算法的速度指的并非时间，而�?�操作数的增速
• �?论算法的速度时间时，�?�们说的�?�随着输入的增加，其�?行时间将以什�?样的速度增加
• 算法的�?行时间用大O表示法表示
• O(log n)比O(n)快，当需�?�?�索的�?素越多时，前者比�?�者快的越多

编写解决实际问�?的程序过程

• 如何用数据形式描述问�?，即将问�?抽象为一个数学模型
• 问�?所涉及�?�的数据量的大小及数据之间的关系
• 如何在计算机中储�?数据及体现数据之间的关系
• 处�?�数据时需�?对数据执行的操作
• 编写的程序的性�?��?��?�良好

数据(Data)

• �?�客观事物的符号表示，在计算机科学中指的�?�所有�?�输入�?�计算机中并被计算机程序处�?�的符号的总称。
• 数据�?素(Data Element) :�?�数据的基本单位，在程序中通常作为一个整体来进行�?虑和处�?�。一个数据�?素可由若干个数据项(Data Item)组�??。
• 数据项(Data Item) : �?�数据的不可�?�割的最小单位。数据项�?�对客观事物�?一方面特性的数据描述。
• 数据对象(Data Object) :�?�性质相�?�的数据�?素的集�??，�?�数据的一个�?集。如字符集�??C={�?A’,’B’,’C,…} 。
• 数据结构 :相互之间具有一定�?�系的数据�?素的集�??。
• 数据的逻辑结构 : 数据�?素之间的相互关系称为逻辑结构。
• 数据操作 : 对数据�?进行的�?算
• 数据类型(Data Type):指的�?�一个值的集�??和定义在该值集上的一组操作的总称。

数据的逻辑结构有四种基本类型

• 集�??：结构中数据�?素之间除了“属于�?�一个集�??"外,再也没有其他的关系
• 线性结构：结构中的数据�?素�?在一对一的关系
• 树形结构：结构中的数据�?素�?在一对多的关系
• 网状�?�者图状结构：结构中的数据�?素�?在多对多的关系

数据结构的储�?方式

由数据�?素之间的关系在计算机中有两种不�?�的表示方法——顺序表示和非顺序表示，从�?�导出两种储�?方式，顺序储�?结构和链式储�?结构

• 顺序�?储结构：用数据�?素在�?储器中的相对位置来表示数据�?素之间的逻辑结构(关系)，数据�?素�?放的地址�?�连续的
• 链式�?储结构：在每一个数据�?素中增加一个�?放另一个�?素地址的指�?(pointer)，用该指�?来表示数据�?素之间的逻辑结构(关系)，数据�?素�?放的地址�?��?�连续没有�?求

数据的逻辑结构和物�?�结构�?�密不可�?�的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的�?储结构

算法(Algorithm)

�?�对特定问�?求解方法(步骤)的一种描述，�?�指令的有�?序�?�，其中每一条指令表示一个�?�多个操作。

算法具有以下五个特性

• 有穷性： 一个算法必须总�?�在执行有穷步之�?�结束，且每一步�?�在有穷时间内完�??
• 确定性：算法中每一条指令必须有确�?�的�?�义，不�?在二义性，且算法只有一个入口和一个出口
• 可行性： 一个算法�?��?�行的，即算法描述的操作�?�可以通过已经实现的基本�?算执行有�?次来实现
• 输入： 一个算法有零个�?�多个输入，这些输入取自于�?个特定的对象集�??
• 输出： 一个算法有一个�?�多个输出，这些输出�?��?�输入有着�?些特定关系的量

算法和程序�?�两个不�?�的概念

一个计算机程序�?�对一个算法使用�?种程序设计语言的具体实现。算法必须可�?止意味着不�?�所有的计算机程序�?��?�算法。

评价一个好的算法有以下几个标准

• 正确性(Correctness )： 算法应满足具体问�?的需
• 可读性(Readability)： 算法应容�?�供人�?�读和交�?，可读性好的算法有助于对算法的�?�解和修改
• �?�壮性(Robustness)： 算法应具有容错处�?�，当输入非法�?�错误数据时，算法应�?�适当地作出反应�?�进行处�?�，而不会产生莫�?�其妙的输出结果
• 通用性(Generality)： 算法应具有一�?�性 ，即算法的处�?�结果对于一�?�的数据集�??�?��??立

�?率与�?储量需求： �?率指的�?�算法执行的时间；�?储量需求指算法执行过程中所需�?的最大�?储空间，一�?�地，这两者与问�?的规模有关

算法的时间复杂度

算法中基本操作重复执行的次数�?�问�?规模n的�?个函数，其时间量度记作T(n)=O(f(n))，称作算法的�?近时间复杂度(Asymptotic Time complexity)，简称时间复杂度

算法的空间复杂度

�?�指算法编写�??程序�?�，在计算机中�?行时所需�?储空间大小的度量，记作：S(n)=O(f(n)),其中n为问�?规模

递归和循环的简单比�?：

1. 从程序上看，递归表现为自己�?用自己，循环�?�没有这样的形式。
2. 递归�?�从问�?的最�?目标出发，�?�?将复杂问�?化为简单问�?，并且简单的问�?的解决思路和复杂问�?一样，�?�时�?在基准�?�况，就�?�最�?求得问�?，�?�逆�?�的。而循环�?�从简单问�?出发，一步步的�?�前发展，最�?求得问�?，�?�正�?�的。
3. 任意循环�?��?�可以用递归来表示的，但�?��?�用循环来实现递归�?除了单�?�递归和尾递归），�?�必须引入�?结构进行压�?出�?。
4. 一�?�来说，非递归的�?率�?于递归。而且递归函数�?用�?�有开销的，递归的次数受堆�?大小的�?�?�。

一起进步学习

1. Fork �?�的项目并�?交你的 idea
2. Pull Request
3. Merge

纠错

如果大家发现有什�?不对的地方，可以发起一个issue�?�者pull request,�?�会及时纠正

补充:发起pull request的commit message请参�?文章Commit message 和 Change log 编写指南

致谢

感谢以下朋友的issue�?�pull request：

• hailwood

• zhangxuanru

• ifreesec

• openset

• Neroxiezi

  License

MIT