引:
其实写这个小稿，是因为最近看到了一本很畅销的《Java algorithm&&structrue》的算法教科书，其实教科书都有一个通病，永远都是死板的，从来没有更深一步的改进。就好比， 今天你学会了如何削水果，第二天你又开始学习用菜刀，教科书只会给你说，如何去用，但他从来不会说，其实削水果的技能某些时候可以用在菜刀上。所以照本宣 科的事情屡见不鲜，这是我最讨厌的事情，很多时候，模枋不一定就是真正的掌握。
影响排序的两大重要因素：
1）比较，比较也就是在两都对比中，判断二者大小
2）替换，根据比较的结果进行相应的替换，比如小的排前面，大的排后面，替换这个不同的语言有不同的影响力，
比如C++，众所周知，在一次A=B的语句中，A会把内存地址中的真实值替换成B中内存地址中的真实值，那么这样的话，替换对性能的影响是相当的大的。
但如JAVA，在一次A=B的语句中，JAVA只是单纯的更改的A的引用地址，将其指向B，这种改动影响较小。
所以不同的语言，对算法的选择中其实有一定的区别。但是实际中，我们仍会选择更为优秀且最好的解决方案。
排序算法的分类及简介：（这里都是从小到大排序）
1）冒泡法：
冒泡法是最简单最易懂的排序算法，其实正如他的名字一样，就是冒泡，从第一个开始，依次比较相临数，如果右边小，则 替换两者位置，第一轮结束，那么最大的数就会排在最尾的位置上，接着进行第二轮，那么第二大的数会排在倒数第二位的位置……..当第N-1轮的结 束时，排序完成
那么这个算法的比较次数就是n*(n-1)
替换次数最大是n*(n-1),
当n很大时，就近似为o(n*n),可见他的效率是极其低下的，但是实现过程却相当简单，所以至今也是很流行。
总算法复杂度为o(n*n).
2）选择法：
从冒泡法可以看出，他几乎一次又一次的进行替换，而且第一轮的许多替换行为会被第二轮甚至第三轮的替换行为所覆盖，也就是说，冒泡法做了许多途劳的工作，如果在一次判断过程中，我可以直接定位一次替换，那岂不是很好？
选择法，就是从冒泡法衍生出来的
首先，我通过比较选出最大的数，放在最后一位，然后，我再选出第二大的数，放在倒数第二位，依次类推，那么最终完成排序。
但很遗憾的时，选择法的比较次数仍是n*(n-1)
但是替换次数，却只有n次
总算法复杂度为o(n*n)/2
选择排序法在数据较多时，会明显看到他的优势，至少没有做一些途劳的工作了
3) 插入法：
插入法是这三种算法中最为优秀的算法，复杂程度也要稍高那么一点，他的优势也是明显的，
插入法顾名思义就是在对的位置插入数据，如何插入呢？
以一个数组为例：
a[0],a[1],a[2],a[3],a[4]
| | | | |
3 5 2 4 9
首选我们判断a[0]与a[1],a[0]<a[1],那么他们是有序的
判断a[2],a[2]<a[1]<a[3],那么a[2]移出，a[0],a[1],依次相后移，a[1]则补上a[2]的位置，a[0]补上a[1]的位置，a[2]则跳到a[0]的位置
a[0],a[1],a[2],a[3],a[4]
| | | | |
2 3 5 4 9
这时，a[0],a[1],a[2],则是有序的，判断a[3],a[3]<a[2],a[3]>a[1],那么，a[3]移出，a[2]右移，a[3]到a[2]的位置
a[0],a[1],a[2],a[3],a[4]
| | | | |
2 3 4 5 9
这时，再判断,a[4],由于a[4]>a[3],位置不变，排序完成
这就是插入排序，这个算法最重要的思想就是局部有序性，系统当前遍历的游标所指之前的元素一定是有序的，这样在后面的数据插入将会相当方遍，你能很快的找到位置，然后插入。对于数据中有部分数据是有序的来说，效率将提升到极致。
这个算法主要是一个N次的遍历比较，与不定性的替换与查找，但是总体算法复杂度是o(n*n)/4,而且几乎总是选 择排序算法所耗时间的一半，有心都可以试试，比如1000个数据库进行排序，选择排序法可能会用700ms,但是插入法只有375ms.但我不会上图的， 无图却真的有真相哦~
更深一步的思考
当说到这儿，其实以上都是许多教科书中能找到大致思路，但是关于插入排序难道就只能如此？为何不能再一次的优化喃，刚才我不是说过插入法中有不定性吗？这个不定性是什么？
我们再想想现在有这样的数据
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16]
1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 5
在上述的数组中，我们还剩最后一位没有排，也就是[16]==5，这个元素，那么按照刚才的插入算法，我们会进行从 15~0的比较，依次查找5这个数应该放在哪个位置，那么也就是说我们就会进行12次比较，才会找到[3]与[4]这个位置，才知道5是放在这里的。那这 12次是否有这个必要？？？如果我这个数据是10000个呢，显然这是一个很荒唐的做法了
那么这个地方，我们如果再引入一个高效的算法呢？不是其它就是著名的二分查找法（折半查找）
折半查找就像我们平时的猜数游戏，当范围为0~10时，要猜的数是4,
那么我就先猜5，大了，此时我缩小范围到0~5,
我就会猜2（（0+5）/2取整）,小了，此时范围为2~5
那我再次猜3((2+5)/2取整),小了,此时范围为3~5
很显然，现在只有一个数可以猜，那必定就是正确答案，4.
也就是说整个过程我只用了4次，就猜出答案，而这个可以用一个2的冥次方来说明此原因：
2的3次方为9，也就是说，9个数我只需折半3次，就可以找到答案，而2的4次方是16，也就是说16个数我需折半4次，找到答案，而10>9且10<16,那么我最多只需要4次就找到答案了。
以上是二分查找法的思想和原理，说到这儿，你是否会有点感触了？为何不把二分查找法引入到插入排序法中？？教科书就是教科书，只会增加算法分例，却从不合并算法。
再次回到刚才那个例子
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16]
1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 5
从[0]到[15]这个局部有序的数组里，我们只需4次比较就可以找到5这个数最终的位置（2的4次方等于16，此局部有序数组有16个元素项），这比起先前需要的12次比较来说，效率大大的提高，而当数据以百万级来计算的话，这种效率的提升是惊人的~
—————–
OVER。照本宣科的死搬算法是行不通的