冒泡排序

简述

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

为什么叫冒泡排序？

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

汉诺塔递归算法

汉诺塔起源

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象为数学问题

如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

解答步骤：

（1）n = 1

• 第1次 1号盘 A—->C sum = 1 次

（2）n = 2

• 第1次 1号盘 A—->B
• 第2次 2号盘 A—->C
• 第3次 1号盘 B—->C sum = 3 次

（3）n = 3

• 第1次 1号盘 A—->C
• 第2次 2号盘 A—->B
• 第3次 1号盘 C—->B
• 第4次 3号盘 A—->C
• 第5次 1号盘 B—->A
• 第6次 2号盘 B—->C
• 第7次 1号盘 A—->C sum = 7 次

不难发现规律：

• 1个圆盘的次数 2的1次方减1
• 2个圆盘的次数 2的2次方减1
• 3个圆盘的次数 2的3次方减1
• 。 。 。 。 。
• n个圆盘的次数 2的n次方减1

最终计算公式：

sum（移动次数）=2^{n} - 1

PHP实现汉诺塔递归运算

简单的用php实现了汉诺塔问题的求解，使用递归调用，但是用php实现要是盘子的个数很多的话，运行起来会很慢的…

汉诺塔主要是有三个塔座X，Y，Z，要求将三个大小不同，依小到大编号为1，2…..n的圆盘从X移动到塔座Z上，要求
（1）：每次只能移动一个圆盘
（2）：圆盘可以插到X，Y，Z中任一塔座上
（3）：任何时候不能将一个较大的圆盘压在较小的圆盘之上

主要是运用了递归的思想，这里使用php做个简单的实现……