不想当将军的士兵，不是好士兵。不了解算法的程序员也不是好的程序员。

                                                                                    by   尼古拉斯---彦祖

首先给上一张，实验环境下，各个排序算法的时间效率对比。

实验环境下的排序结果

一  简单概念

    算法频率度即一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    时间复杂度以大O表示法 常见的有四种：

    O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶

二  快速排序

    取某一位（一般是首位）作为flag. 分治法排序。

    每一趟的下标都是前后同时进行，比flag小的放到左边，比flag大的放到右边。结束条件为前后下标重合。

    一趟排序可以得到以flag为界限的 两个集合。依次递归，结束条件为不可再分。

    换句话说：  现在要给一万个排成一列的士兵 按照大小个排队。  

    首先取第一个士兵的高度为标准，称其为flag，一趟算法的期望运行结果，就是所有比这个士兵低的人在这个士兵前面，所有比这个士兵高的人都在他后面。

    那么，怎么实现这个效果呢？？ 

    找两个将军来，一个站在列首，一个站在列尾。

    列尾的将军，站在第10000个士兵这个位置，看看他比flag高，还是低，如果高那么不管，列尾的将军向前走一步。 走到第9999个士兵处，继续比较，直到走到一个比flag低的士兵位置。比如第9996个士兵比第一个士兵低，那么让 9996和 1 互换位置。     此时的flag的位置变成了9996

    现在列尾的将军先休息，让列首的将军从2这个位置向前走，走到第一个比flag高的位置，比如是第15个。 那就让15 和9996换位置，并且更新flag为15。此时列首将军休息，列尾的将军继续。  以此类推。

直到列首和列尾的将军碰了面，那么本趟快排结束。 

比如此时的位置是6666个士兵处。根据上面的过程推论，此时flag也一定在6666处。两个将军不碰面也正是快速排序的特点

那么本趟排序完成。 整个队列被6666分成了两个A B队列，前面的一定比士兵flag矮小，后面的一定比flag高大。

然后再请四位将军过来对，这AB两个队列进行上述操作。直到队列变成2个人（不可再分割）。以此类推

快排执行效率 快排源码实现

三   选择排序

    与冒泡排序类似，但是区别在于，新建局部变量储存本趟的目标值。

    每次只比较而不交换，直到一趟排序结束之后。才进行转换，提升了部分效率

    还是那一列一万个士兵的队伍。 

    一个将军拿着一个笔记本，

    从第一个开始问，你身高多少？ “1.60”   看来你是最低的，于是他将第一个士兵的名字写到了笔记本上。

    第二个 “你身高多高”    “185”     不管，下一个

    第三个问“你身高多少”“158”        将军，划掉了上一个名字，记上了最新的这个人的名字。

    直到问完整个队伍。  将军看到笔记本上写着  最低的那个人的名字   “提利昂-兰尼斯特”  你站到第一个位置。

    这是一趟排序结束。

     接下来，将军从第二个位置开始问。（第一个已经确定了）以此类推，直到最后一个。

    

选择排序比冒泡排序快很多     选择排序实现

四  插入排序

    4.1 简单插入排序

        简单插入排序的核心思想是认为，所有的事情都是基于一个已有序的序列进行的。

        比如下标从第一个元素开始，认为  第一个元素本身是一个有序序列（这是对的，因为只有一个元素。）

        那么下标转移到第二个元素，将第二个元素 去与左边的有序序列（第一个元素）比较，插入到合适的位置。

        下标继续，逻辑依然如此，直到下标行走到最后的位置。整个序列都有序了。

        他的算法逻辑是这样的， 请来两位将军A,B， 

        首先是告诉A将军，你首先管理的是无序的9999个士兵队列。你只管把他们一个个都推出去给B将军就行了。 你可以认为B将军那里的永远是一个有序队列。

        然后告诉B将军，你手下永远是有序的队列。现在你手下有一个人，当然是有序的，接下来再来新人，都让他们和之前的有序队列比较，找到他们合适的位置。  

        第二个人来的时候，和原先的第一个人比较，如果比之前的人高，那么站在他后面，如果比他矮站在他前面 

        第三个人来的时候，从第一个位置开始找，找到第一个比他高的人，插入进队列。后面的士兵，都后退一步。

        以此类推，直到B将军手下 所有的士兵都到了A将军手下为止。

        所以，你可以简单的理解它为插队排序

    4.2  希尔排序

        希尔排序是基于插入排序的以下两点性质而提出改进方法的：

            1     插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

            2     但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

        希尔排序的意思是现将正序列变成一个基本有序的序列，然后再进行简单插入排序。

        那么如何将一个序列变成基本有序的序列呢。 现在有一个100元素的序列

        第一趟将其拆成50个有序序列。  对这50个有序序列进行简单插入排序

        第二趟将其拆分为25个，每个4元素的序列，对这25个有序序列进行简单插入排序。

        知道最后将其拆分为一个 100元素序列为止。

        希尔排序是在简单插入排序的基础上演进来的，理论的东西，不多赘述。可以这样理解。

        希尔排序的基本思想还是 A ,B两个将军 分别管理一个有序队列和一个无序队列。

        但是差别在于，如果整个队列是接近完全无序的情况下，每次新兵进去 B将军的有序队列，都要进行一次整体的位移。也就是比较的次数为LOG（n2），而且在排序后期，这里的N基本都无限接近一万，这是一个很大的性能消耗。

        而希尔排序，则是先取增量为10，所有的下标向10取余

        先让尾号为0的士兵向前一步， 这样就出现了1000名，位置尾号为0的士兵。 先对这1000名士兵进行插入排序，即便出现插入操作而导致的整体位移，移动成本也比一万名士兵移动好多了。  这样已经有十分之一的士兵有序了

        然后再让尾号为1的士兵向前一步...，尾号为2的士兵向前一步。  以此类推。整体一万个士兵也就基本有序了。

这样我们一趟排序完成，此时我们的增量为10. 接下来我们降低增量为5，

所有士兵的下标向5取余。  我们还是按照刚才的办法，每次对五分之一的士兵，进行插入排序。

虽然两千名士兵整体位移的成本依然很高，但是毕竟比一万小了很多，况且之前已经有过一次十分之一规模的插入排序了。所以发生插入操作的概率不大。

第二趟排序结束。  继续缩小增量。直到为0.。。。。。   

over (真特么的麻烦。。。)

希尔排序执行效果 希尔排序代码实现

五  冒泡排序

    相对原始的方法，对比每一个元素，每趟选出一个最大值出来。时间复杂度为O（n2）

这个算法最简单，也最好理解，和选择排序极为类似。只不过区别不是将军带着笔记本去挨个统计个头了。

而是将军领着当前等待排序的士兵本人，与下一个士兵比个头。  最后跟着将军走到队列尾部的，一定是个头最大的。

    算法实现：

冒泡

附上：源码下载地址：

http://note.youdao.com/noteshare?id=2afb3adfc83d0684ff79deb931c079bb&sub=97381DA724BC4B3DA8EE2D5175176593