插入排序

先说下插入排序实现过程：

     对要排序的数组，逐个进行处理，与前面的子序列进行比较，让它插入到合适的位置。

时间复杂度：

      某一个模块的函数f()的增长率越小，整个程序执行时间增长率就越小，注意这个里面是指的是函数的增长率就是所说的时间复杂度。它是衡量算法好坏的标准之一，时间复杂度越小，算法的效率越高。 现在的电脑都可以满足小程序所需要的内存，如果遇到比较大的数据群，换台更大点的电脑不实际，优化算法才是最合适的选择。

插入排序的时间复杂度是Ο（n^2）：

        这个很早就知道但是它是怎们来的纳？今天花了点时间，琢磨了一下，不仅仅是翻到了《数据结构与算法》还翻到了《高等数学》，下面是我个人的理解。

插入排序当中，主要通过两个函数f()确定时间复杂度：

  1）要插入进去的关键字与已知子序列之间的比较次数；

  2）比较完成之后的序列中移动次数；

          嗯，可以开始分析了；先分为两种情形：

 1）最幸运：所要排序的数组恰好已经是从小到大的排列起来的，比如（1，2，3，5，6，7，8、、）看看上面两个函数结果，比较次数是（n-1），要移动的次数是0；

 2) 最倒霉： 所要排序的数组整个都是逆序的，也就是说是从大到小排列的，比如（7，6，4，2，1、、、），推出比较次数的函数表达式用到了等差数列前n项和的公式，应该是（n+2）（n-1）/2，那么后面的移动次数根据同样的原理是（n+4）（n-1）/2；

     ok，上面过程当中的最幸运和最倒霉分别对应的是定义时间复杂度时的下限和上限，每次所要排序的数据都是随机的，排序当中的数据出现各种排序方式的概率是相同的，取上面两种情形最小值和最大值的平均，应该是n^2/4,最后对这个表达式求极限，就是插入排序的时间复杂度了。

     贴段自己写的插入排序：

  有点自己的感想：

    java已经提供了很好的排序算法的类，只要引用里面的方法就可以了，还有必要在学习排序算法，分析其中的过程吗？

    这样程序员就会慢慢和搞数学的画上等号，我自己觉得，在这个方面应该就是外面的各种培训机构所不能做到的地方，也就是这个地方是大学生比其他培训机构具有的优势，可以分析程序背后纯数学的简单问题。

如果，您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】 

如果，您希望更容易地发现我的新博客，不妨点击一下左下角的【关注我】 

如果，您对我的博客内容感兴趣，请继续关注我的后续博客，我是【orson】 

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段 声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。 

转载：http://www.cnblogs.com/java-class/archive/2012/12/26/2834717.html