不想当将军的士兵，不是好士兵。不了解算法的程序员也不是好的程序员。
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
