从排序开始

图还没做完，什么时候这行字删了，图就配好了 以及大概还要修改一下的。。。

每种排序的代码会附在文末（现在还没有配哒）在Excel中，你按一下排序按钮，大量的的数据在一瞬间就排列好了；老师让你排一下全班的成绩，你花了几分钟就排出来了。可是，这些排序到底是如何进行的？我们究竟该怎样排序？

冒个泡

要回答这个问题，我们先从一个场景开始：你面前有10个人，请你在不知道他们身高的情况下，将他们从高到矮排序。相信大家都能想到一种最简单的方法：两两比较。从第一个人开始，比较他和他右边的人的高矮。如果他比另一个人矮，就交换他两的位置。显然，用这种方法是一定能排号序的。因为从左到右每排一次，就一定能将最矮的那个人移到队尾。这种方法，我们称之为：冒泡排序。可是，这种方法实在是太慢了。我们假设现在有n个人，他们非要和你作对，先从矮到高站好了。于是，你为了让他们从高到矮排好，你就要比： n+(n-1)+(n-2)+...+2+1次用大家都学过的等差数列求和，易得，要比(1+n)*n/2次排好一个60人的班级，你就要比1830次，2秒比一次，一个小时都比不完。当然，你会说：“这不科学啊，如果他们这么站，我一下就能看出来了啊！” 但是，计算机一次，还真就只能看到两个数字。

插入呢？

那我们不把他们互相比了，我们每次把一个人插进一个已经排好的队列里，行不行？当然可以，这就是插入排序。可惜，你比较非，每一次都选中了剩下的人中最矮的那一个。很不巧的是，你选择了从右到左比来看他插入的位置。于是，排好n个人，你又比了(1+n)*n/2次... 没事，非到极致，也是一种欧。看起来，这个问题无解了？直到你某一天翻开了数学书，看到了求方程近似解的过程——二分。

二分插入

二分是什么？怎么二分呢？假设我们现在已经有一个包含m个人的，排好的队列。现在我们要向里面插入一个人A。于是，我们把已有的队列从中间分开。可以很明显的看到，左边的数据一定小于等于一个数x，右边的数据也一定大于x。于是，我们可以只将A的身高与x进行比较，就可以得知他是在左边还是右边。然后我们再对他所在的那一边进行同样的操作，直到找到他的位置。容易发现，我们每二分一次，他需要比的人数就下降了一半。于是对于A来说，他只需要比⌊log2(m)⌋+1次（⌊ ⌋是向下取整）经过一些简单的计算，我们发现：同样是一个60人的班，排好只需要297次比较。或许还是很多，但已经少了不少了。事实上，数据量越大，二分插入的优势越明显。但我们每插入一个人，就要把一堆人移来移去，感觉好麻烦。而在程序中，一个数组同样不支持直接的插入。那么我们有没有办法优化一下呢？

归并！！！

相信大家都做过流程优化的问题。举个例子：小明做饭要洗菜、煮汤、炒菜，他要怎么做才能最省时间？答案很简单：先洗菜，再同时煮汤、炒菜。而对于上面的排序，我们来分析一下大概的流程：分开->排序->合并，然后重复这一过程。那要怎么优化呢？我们发现，它每一次都要把数据先合并，再分开。假如我们一次就能全部分开，然后合并，是不是就可以少移动几次数据了？我们来尝试一下。要注意的是，前面二分的过程中，我们保证了这样的一点：

左边的队列一定小于等于一个数x，右边的队列也一定大于x。

所以，在这里我们也要尽量保持。实现的方法很简单：先选中中间的个数x，分为两个左、右部分，然后在两边不断重复这一过程。最后当没有办法再分（只有一个人）的时候，开始合并。在合并过程中，我们通过交换人的位置，来保证他们高矮的有序性。由于合并之前的两个部分是有序的，我们只需要从左到右过一遍，即可保证合并后是有序的。于是，他们便排好序了。但感觉这种方法也在移来移去呀，它好在哪里？？？其实，说是“分开”再“合并”，但我们只需要设置一个标记，合并时交换数的位置，然后就可以了。根本不需要真正的去分、合。这种方法的比较次数和二分插入一样，但却少了很多移动的过程。