​

ðŸ?³ 用 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