罗朝辉（飘飘白云）

关注嵌入式操作系统，移动平台，图形开发。-->加微博 ^_^
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  85 随笔 :: 0 文章 :: 169 评论 :: 0 Trackbacks

Algorithms

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

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

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

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

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

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

【排序】排序算法之分配排序
     摘要: 前面讲了插入排序，交换排序，选择排序，归并排序，下面接着来讲桶排序，基数排序。

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

【排序】排序算法之归并排序
     摘要: 前面讲了插入排序，交换排序，选择排序，下面接着来讲归并排序。

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

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

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

【排序】排序算法之交换排序
     摘要: 前面我们讲了插入排序，下面接着来讲交换排序。

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

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

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

1、插入排序（直接插入排序、希尔排序）；
2、交换排序（冒泡排序、快速排序）；
3、选择排序（直接选择排序、堆排序）；
4、归并排序；
5、桶排序（桶排序，基数排序）；

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

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

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

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