算法入门篇：简单的排序算法( 二 ) _排序算法

既然有了前人的摸索，后人站们这些的思维又是怎样的呢？
4
希尔排序

比如说我们在说到无论是冒泡还是插入排序，有没有注意到“一个个的往后挪”这样的字眼？为什么要一个个的挪呢？能不能一大段一大段的挪？打个比方，如果排序一个1~100的数组（原序列是100,99,98...1），这个时候100是在第1位，光排完100这个数你就得挪99次，得调用上面的swap方法99次，但比如说把这个一个个挪切换成一半一半的挪，比如第一个数100跟51比较后交换然后99跟52比较，是不是就非常大的迈了一大步？这些迈完后，再把间隔变成25，再来迈，虽说可能迈偏对吧？没事最后做一个步伐为1的修正就好了。而这，就是鼎鼎有名的希尔排序。
看一下希尔排序是怎么实现的哈：

文章插图

5
归并排序

看了以前上面一个个的挪实在太费劲了，我要比较，我不挪，我直接就拿出来，分成小组，每个小组自己先弄成有序的，再汇总，这样这种分而治之思想的实际上就是归并排序。它的核心排序点在哪呢？你分治就分治嘛，怎么分？又怎么治？就是我为神马用这个排序，这个数据通过这个方法过一下就变有序了？核心就在于小组——这个小组的成员最多只有2个，比如说数组的长度是8，就分成了4个2，7就分成3个2跟1个1，多个数我们一眼排不出序来，两个总可以吧？没错，这就是分。那怎么治呢？我们看下下面比如说我现在A，B两个小组已经完成了他们内部的排序（他们的长度都是4）
A B
1568 2479

文章插图

那一起看看它是怎么实现的吧：

文章插图

6
快速排序

这个时候呢，也诞生了另一个思想，个人看来也是一种分类，它是怎样的呢？有点类似于体育课的时候高个子站后面矮个子站前面，教练没办法一开始就一眼看出谁高谁矮对吧？那么多人，肯定是随便逮一个，来以他为基准，排序！！！一声令下，小个的站这家伙的前边，大个的站后边，对吧？而这就是快速排序的核心思想。有点像二分法，不过这个二分法有点不同，它不是按长度，它是按类，你高就占那边，矮就站这边，把整体分成两部分，那矮的那块还能不能再分，那是当然，矮的那块再随便找一个，再分，这样就完成了一个排序的内部过程。（左边小，右边大，那当长度为3的时候不就实现有序了吗？嗯，这就是快排的核心思想）
具体的代码怎么实现呢？
这样很直观的我们就想到，嘿我弄两个数组，装高个子跟矮个子，然后再concat回来对吧？当然记得把中间那家伙给放进去，别漏了。看下下面：

文章插图

嗯，是不是很直观？呵呵，但是要知道，排序，特别是排序数据非常多的时候，最考验的就是性能，而代码中left = [], right = []；还递归，这个内存的开销是非常大的，所以我们不这样，那怎么做呢？

文章插图

上面的虽然没重新创建数组，但是呢？通过交换，比如说大于参考点的放左边，小于的放右边，那我直接等待一下，一个从左边开始扫描，一个从右边，当左边扫描到比参考数大的数时，结束扫描，右边也扫描，当有一个数比参考数小时，就结束扫描，这时候把这两个数交换一下，是不是就实现了小的在前面大的在后面，你说，可他们不一定在参考点两边啊？没错，这个时候继续扫描，等到i和j在某个点相遇的时候，把这个参考点的值跟那个位置的值换一下，不就实现两边一边大一边小嘛。、
嗯，有了一个了，当然得有无数次，左边那块再继续做这个事，右边的也一样，当右边跟左边再加上中间的数长度刚好为3或小于3的时候不就OK了？

7
堆排序

这时候还有一个性能也很不错的排序，用到完全二叉树的方式来的。
它又是怎么想的？卧槽（没文化的我只会这一句= =），不就个排序，非得弄那么多乱七八糟的？嗯，怎么说呢，这是一种思想，先不扯远一起看看具体是怎么样的吧。