形象下九个简单算法

    以下并不一一详解个个算法，主要是前天看了下九个基本算法，一时之间有点记忆不住，可能看了某某算法后不能联想骑具体为哪个算法。但他们并不复杂，只是一次九个，难免会思想会混杂。

   所以，本文章主要以图片为简介（没看过这些算法的不介意用这个去学，毕竟没详细介绍），让人（主要是我自己看的）一看就能联想起个个算法具体思路。这些算法都不难，相信有思路，那么按照思路就能写出代码，只是熟悉的写的快点，漂亮整洁点，不熟悉的写得慢点。

上图：

   

 

待续。。。。

 

 

     知道具体思路怎样也没用，重要在实际应用，那就得看它们的效率问题了。

     引用http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html的分析，如下

    

      性能分析和总结

     先不分析复杂度为Ο(n)的算法，因为速度太快，而且有些条件限制，我们先分析前六种算法，即：冒泡，直接插入，二分插入，直接选择，快速排序和改进型快速排序。

我的分析过程并不复杂，尝试产生一个随机数数组，数值范围是0到7FFF，这正好可以用C++的随机函数rand()产生随机数来填充数组，然后尝试不同长度的数组，同一种长度的数组尝试10次，以此得出平均值，避免过多波动，最后用Excel对结果进行分析，OK，上图了。

      最差的一眼就看出来了，是冒泡，直接插入和直接选择旗鼓相当，但我更偏向于使用直接选择，因为思路简单，需要移动的元素相对较少，况且速度还稍微快一点呢，从图中看，二分插入的速度比直接插入有了较大的提升，但代码稍微长了一点点。

     令人感到比较意外的是快速排序，3万点以内的快速排序所消耗的时间几乎可以忽略不计，速度之快，令人振奋，而改进型快速排序的线跟快速排序重合，因此不画出来。看来要对快速排序进行单独分析，我加大了数组元素的数目，从5万到150万，画出下图：

    

     可以看到，即便到了150万点，两种快速排序也仅需差不多半秒钟就完成了，实在快，改进型快速排序性能确实有微略提高，但并不明显，从图中也能看出来，是不是我设置的最小快速排序元素数目不太合适？但我尝试了好几个值都相差无几。

最后看线性复杂度的排序，速度非常惊人，我从40万测试到1200万，结果如图：

 

 

    

     可见稍微调整下算法，速度可以得到质的飞升，而不是我们以前所认为的那样：再快也不会比冒泡法快多少啊？

我最后制作一张表，比较一下这些排序法：

评论

3 楼 marauder 2011-01-08  

yuhang_java 写道

第一个图：不是执行5次比较移位的操作吗？ 为何是6次呢？

呵呵，对，是5次，当时走火入魔了

2 楼 yuhang_java 2010-12-31  

第一个图：不是执行5次比较移位的操作吗？ 为何是6次呢？

1 楼 yuhang_java 2010-12-31  

asdsad