2015-04-24 刘太华
游戏服务端碰撞检测 最近看了一些游戏碰撞检测相关的一些内容,然后开始读了一些我们游戏里关于碰撞检测的代码,我们游戏里现在的碰撞检测按我暂时阅读完的代码, 应该分为2块,相对来说我们基本的碰撞检测算法是比较简单的, 后面也记录一下网上看到的关于分离轴多边形的碰撞检测。 继续阅读 »
2016-08-20 crane-yuan
最近在研究算法,发现其实算法也并不是特别难,只要抓住算法的核心思想,再静下心来,都可以自己实现的。在计算机领域,有一些常见的而且又经常使用的算法,这些算法我们应该掌握,比如常见的排序算法;还有一些算法就是特定领域中经常使用的算法了,这些算法我们只有必须使用时再去学习使用就行了,比如图像处理中的快速傅里叶变换算法。 算法定义 让我们来看看算法的定义吧。(以下定义摘自中文维基百科) 在数学和计算机科学/算学之中,算法/演算法/算则法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。 算法中的指令描述的是一个计算,当其运 继续阅读 »
2014-01-12 W.Y.
算法原理 快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。 利用分治法可将快速排序的分为三步: 在数据集之中,选择一个元素作为"基准"(pivot)。 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。 对 继续阅读 »
2014-01-14 W.Y.
算法原理 先上一张堆排序动画演示图片: 1. 不得不说说二叉树 要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点;深度为 k 的二叉树至多有 2k - 1 个结点;对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。 树和二叉树的三个主要差别: - 树的结 继续阅读 »
2014-01-15 W.Y.
算法原理 希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: - 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 - 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 算法思路: 1. 先取一个正整数 d1(d1 < n),把全部记 继续阅读 »
2016-09-02 crane-yuan
定义 希尔排序(英语:Shell sort),也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 more 算法步骤 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。 选择步长 按照选择的步长对序列进 继续阅读 »
2014-01-13 W.Y.
算法原理 选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理如下,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的序列进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。 more 实例分析 以数组 arr = [8, 5, 2, 6, 9, 3, 1, 继续阅读 »
2014-01-15 W.Y.
算法原理 归并排序(Merge Sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 归并操作(Merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。 算法思路: 1. 把 n 个记录看成 n 个长度为 l 的有序子表 2. 进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表 3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。 m 继续阅读 »
2016-05-22 MoreFreeze
学习了下LevelDB的实现原理,发现G厂大神Jeff Dean果然牛B,实现也很巧妙。 参考链接是这里 继续阅读 »
2014-01-12 W.Y.
在学习排序算法的时候,经常要用到随机数组,于是就写了一个生成随机数组的方法。算法来自网络,只是修改成了 JavaScript 版本。 基本原理是洗牌算法,首先从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。 具体代码如下: javascript /** * * 生成从 1 到 length 之间的随机数组 * * @length 随机数组的长度,如果未传递该参数,那么 length 为默认值 9 * */ function randomArray(length) { var i, inde 继续阅读 »