Algorithm | 酷壳 - CoolShell

可视化的排序过程

2011年03月18日陈皓评论 54 条评论 40,902 人阅读

下面是一个日本程序员制做的一个可视化的排序过程，包括了各种经典的排序算法，你可以调整速度和需要排序的个数。酷壳以前也介绍过几篇相关的文章一个排序算法比较的网站，一个显示排序过程的Python脚本关于各种排序算法的运行复杂度比较，请参看Wikipedia的排序算法比较。

<br />

(67 人打了分，平均分： 4.76 )

一些有意思的贴子和工具

2011年03月04日陈皓评论 24 条评论 28,045 人阅读

又到了介绍各种杂项的时候了，正如以前的这三篇（这篇，这篇，和这篇）文章一样，本篇文章也给你介绍一些最近出现的一些有趣的东西。希望你能喜欢。

先说找工作吧，电影《该页无法显示》里的那个facebook主页上的招聘网页上是列了一堆问题，你可以去看看，你可以使用c/c++，Erlang，Haskell，Java，Perl，Python，PHP，Ruby来解题，不过只接受Unix/Linux下的版本，不接受Windows的版本。无独有偶，DropBox的招聘网页上也是些算法题，大家可以过去看看，不过需要翻墙。（现在，对于美国互联网企业来说，如果你没有被C2C，说明你根本不存在，如果你没有被墙，说明你还不算成功）

接下来给大家介绍一些文档和教程吧，都是英文的。

Java和C#的完整比较。这是一个相当完整的比较Java和C#语言的网页。很有意思，有助于你了解Java和C#的各种特性和不同。

SQL 性能调优。这个文档覆盖了IBM DB2, MySQL, Oracle,PostgreSQL 和 Microsoft SQL Server。不过这个电子书还没有写完，你可以使用其RSS, twitter 或 Facebook 来跟踪其进度。

Clever Algorithms。这个电子书也是免费的。其主要面向一些AI和面向自然的算法，一共45个。其包括概率随机算法，迭代进化算法，物理算法，可能性算法，蚂蚁蜜蜂式算法，免疫算法，神经算法等。里面大量的高等数学公式对我来说我已经看不懂了。不过，我相信这个电子书非常适合搞理论研究的人，或是需要抄袭一篇论文以顺利毕业的人使用。

HTML5 Audio & Video 处理。这是一组在线的幻灯片，请使用键盘光标键翻页。这是一组带着各种演示的幻灯片，对于你要学习HTML5的声音和视频相关的知识很有帮助。

C 语言的宏。你想知道C语的宏有哪些有些意思的用法吗？这篇文档不会让你失望的。其由浅入深地向你介绍了宏的各种用法。

各种语言的排序算法。你想知道各种语言其默认的排序算法用的是哪种排序算法吗？看看这篇文章吧。

物理模拟F#教程。相信你一定玩过那种游戏，画一个任意形状的石头，其会从天上落下以砸下面的一个东西，这个教程用.NET的F#向大家说明了这种东西怎么去做。（演示程序）

…

阅读全文 Read More

(19 人打了分，平均分： 4.16 )

打印质数的各种算法

2011年02月28日陈皓评论 45 条评论 41,379 人阅读

打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，

实际应用和教学应用有很大的差别。
最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。

#include <iostream>
using namespace std;

bool isPrime(int nr)
{
    for (int d = 2; (d * d) < (nr + 1); ++d){
        if (!(nr % d)){
            return false;
        }
     }
    return true;
}

int main (int argc, char * const argv[])
{
    for (int i = 0; i < 50; ++i){
        if (isPrime(i)){
            cout << i << endl;
        }
    }
}

…

阅读全文 Read More

(14 人打了分，平均分： 3.14 )

一些重要的算法

2010年07月12日陈皓评论 36 条评论 58,606 人阅读

下面是一些比较重要的算法，原文罗列了32个，但我觉得有很多是数论里的，和计算机的不相干，所以没有选取。下面的这些，有的我们经常在用，有的基本不用。有的很常见，有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。（注：本篇文章并非翻译，其中的算法描述大部份摘自Wikipedia，因为维基百科描述的很专业了）

A*搜寻算法
俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
Beam Search
束搜索(beam search) 方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k 个最好的路径,仅从这k 个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20 世纪70 年代中期首先被应用于人工智能领域,1976 年Lowerre 在其称为HARPY的语音识别系统中第一次使用了束搜索方法,他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。
二分取中查找算法
一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。
…

阅读全文 Read More