罗朝辉(飘飘白云)

关注嵌入式操作系统,移动平台,图形开发。-->加微博 ^_^

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  85 随笔 :: 0 文章 :: 169 评论 :: 0 Trackbacks

Algorithms

算法,数据结构相关的东东
     摘要: 前面写了好些排序,红黑树,B 树算法的文章,还剩下查找这一大块没有写,查找相关的算法代码已经实现,但是却没有写查找算法日志的闲情了,只好先在这里放出代码来,以后有空有闲情再补上吧。

算法代码 Google 仓库:点击这里
  阅读全文
posted @ 2011-04-10 12:11 罗朝辉 阅读(735) | 评论 (0)  编辑

     摘要: 红黑树本质是二叉查找树的一种,它的性能高于普通的二叉查找树,即使是在最坏的情况下也能保证时间复杂度为O(lgn)。红黑树在每个结点上增加一个存储位表示结点的颜色(或红或黑,故称红黑树)。通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树可以保证没有一条路径会比其他路径长出两倍,因而是接近平衡的。

红黑树的每个结点至少包含五个域:color,key,left,right 和 parent(一般我们都会在结点中存储额外的数据 data,但前面的五个域是必不可少的),如果某个结点没有子结点或者结节点,则将相应的指针设置为空值(NIL,注意不是 NULL,NIL是一个特定的空结点对象,类似于Obj-C 中 Nil对象)。我们将这些 NIL 当作叶子结点(在实际处理过程中,往往将最底层的孩子结点和根结点的父亲都指向同一个 NIL 结点,以便于处理红黑树代码中的边界条件),而将其它结点当作内结点。
  阅读全文
posted @ 2011-04-03 11:21 罗朝辉 阅读(1689) | 评论 (0)  编辑

     摘要: B 树是一种被设计成专门存储在磁盘上的平衡查找树。因为磁盘的操作速度要大大慢于随机存取存储器,所以在分析B 树的性能时,不仅要看动态集合操作花了多少计算时间,还要看执行了多少次磁盘存储操作。 B 树与红黑树(下一篇介绍)类似,但在降低磁盘I/O 操作次数方面要更好一些。许多数据库系统就使用 B 树或 B 树的变形来存储信息,想象一下一棵每个节点包含 1001 个 key 的高度为 2 的 B 树能容纳多少数据啊,而在内存中我们只存储了一个节点,在需要的时候再从磁盘中读取所需的节点。

  阅读全文
posted @ 2011-03-21 23:10 罗朝辉 阅读(3871) | 评论 (5)  编辑

     摘要: 前面讲了插入排序,交换排序,选择排序,归并排序,下面接着来讲桶排序,基数排序。

桶排序和基数排序均属于分配排序。分配排序的基本思想:排序过程无须比较关键字,而是通过用额外的空间来"分配"和"收集"来实现排序,它们的时间复杂度可达到线性阶:O(n)。简言之就是:用空间换时间,所以性能与基于比较的排序才有数量级的提高!  阅读全文
posted @ 2011-03-18 23:47 罗朝辉 阅读(601) | 评论 (0)  编辑

     摘要: 前面讲了插入排序,交换排序,选择排序,下面接着来讲归并排序。

归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

其基本思想为:设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上:array[low..m],array[m + 1..high],先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中,待合并完成后将 temp 复制回 array[low..high]中,从而完成排序。
  阅读全文
posted @ 2011-03-13 15:19 罗朝辉 阅读(4354) | 评论 (0)  编辑

     摘要: 前面讲了插入,交换排序,下面接着来讲选择排序。  阅读全文
posted @ 2011-03-09 21:37 罗朝辉 阅读(1067) | 评论 (0)  编辑

     摘要: 前面我们讲了插入排序,下面接着来讲交换排序。

交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。
  阅读全文
posted @ 2011-03-04 23:47 罗朝辉 阅读(1189) | 评论 (0)  编辑

     摘要: 排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重,其重要性无需多言。下文将介绍常用的如下排序方法,对它们进行简单的分析和比较,并提供 C/C++ 语言实现。

所谓排序,就是要将一堆记录,使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略,可以分为如上五种:

1、插入排序(直接插入排序、希尔排序);
2、交换排序(冒泡排序、快速排序);
3、选择排序(直接选择排序、堆排序);
4、归并排序;
5、桶排序(桶排序,基数排序);

其中插入排序、交换排序、选择排序、选择排序、归并排序都是基于关键字比较的排序,比较排序的平均时间复杂度好不过 O(nlogn)。
而桶排序是基于映射的排序,其平均时间复杂度可达到 O(n),但桶排序需要额外的空间来存储经过映射的记录。

通常在待排序记录较多的时候,基于映射的排序 O(n) 比基于比较的排序 O(nlogn) 的效率要高得多,这很好理解:用空间换时间。(查找算法其实也是如  阅读全文
posted @ 2011-03-03 22:07 罗朝辉 阅读(1500) | 评论 (0)  编辑

     摘要: 在上一篇文章《Android 上实现水波特效》中对水波波幅的计算是针对每一个像素的,效率比较低,尤其是在手机上运行,相当缓慢。我们可以利用线性插值进行优化,这样可以将计算减少一半(MeshSize 为 2)或减少四分之三(MeshSize 为 4),效率得以大大提升,即使是在手机上也能较为流畅地运行。
  阅读全文
posted @ 2010-09-28 11:49 罗朝辉 阅读(1206) | 评论 (0)  编辑

     摘要: 本文中的水波特效算法部分整理自 GameRes 上的资料,原作者 Imagic。我只是在学习 Android 的过程中,想到这个特效,然后就在Android 上实现出来,并在源算法的基础上添加了雨滴滴落特效,以及划过水面时的涟漪特效。 该程序在模拟器和真机上运行速度都较慢,需要进一步优化或使用 JNI 实现,如果你想到好的优化算法,请联系我:kesalin@gmail.com。  阅读全文
posted @ 2010-09-01 13:19 罗朝辉 阅读(3344) | 评论 (0)  编辑