改进的插入排序——二分法插入排序

前两天买了本《算法导论》,昨天刚看插入排序,看到例子,插入排序就类似于摸牌,摸出一张然后再插入到对应的位置。想起前些日子国庆在家玩牌的经历,摸牌时是这么个回事,但是又不同,现实中摸牌我们总是能很快的找到指定的位置,比如拿张5基本就能很快确定中间偏右的位置,因为手中的牌已经是有顺序的了。我想到了二分法也许可以在寻找位置时减少比较。 Continue reading

PHP实现二分法查找

在一个有序表或数组中,查找一个元素是否存在,用二分查找的过程是:首先找出集合中间的那个元素,如果此元素比要查的元素大,就接着在较小的半个区域进行查找;反之,如果此元素比要查找的元素小,就在较大的那半个区域查找。在每个更小的数据集中重复这个查找过程,直到找到要查找的元素或者数据集不能再分割。PHP程序如下 Continue reading

PHP实现“冒泡排序”算法

冒泡排序:依次比较相邻的两个数,将小数放在前面,大数放在后面。在第一趟中,先将1和2个数比较,再将第2和3个数比较,第一趟结束后,最大的数被放到了最后。接下来进行第二趟比较,使得次大的数放到倒数第二位, 经过N-1躺比较(N为数组元素个数),即可排序成功。 Continue reading

PHP版分治算法之“归并排序”

归并排序:对一堆支票进行排序。首先,将这堆未排序的支票对分成两堆。接着,分别又将两堆支票对半分成两堆,以此类推,重复此过程,直到每一堆支票只包含一张支票。一旦所有的堆都只包含一张支票,就开始将堆两两合并,这样每个合并出来的堆就是两个有序堆的合集,也是有序的,这个合并过程一直持续下去,直到一堆新的支票生成。此时,这堆支票就变成有序的了。 Continue reading

PHP版分治算法之“快速排序”

分治法包含3个步骤:分解、求解与合并。在分解阶段,将数据分解为更小,更容易管理的部分。在求解阶段,对每个分解出的部分进行处理。在合并阶段,将每部分处理的结果进行合并。

分治法的一个例子是“快速排序”,另一个例子是“归并排序”。 Continue reading

算法之“插入排序”(PHP与C语言实现)

插入排序:人们摸牌时的方法是一张一张的摸,然后将每张牌插入到其他已经有序的牌中的适当的位置。在计算机的实现中,为了给要插入的元素腾出空间,我们需要将其余所有元素在插入之前都向右移动一位。这种算法就是插入排序。 Continue reading

算法之“选择排序”(PHP与C语言实现)

从本文开始,会陆续记录自己学习的算法,并尽量用PHP语言和C语言表示出来,更好的去理解算法,和实践

选择排序:首先找到数组中最小的那个元素;其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小的元素 那么它就和自己交换);再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换位置,如此往复,直到将整个数组排序(不断的选择剩余元素中的最小元素) Continue reading