算法入门篇：简单的排序算法

作者：dorseyCh
来源：http://www.imooc.com/article/264180

很久之前有过一次面试，被问到一个问题，能不能写一个冒泡排序？说实话，尽管在这之前曾经写过不少比这个更加复杂的处理逻辑，但很悲剧的是我当时真不知道什么是冒泡排序。。。只知道如果让我排序某段混乱序列，能很快搞定就是了，最后的结果显而易见，我被赤裸裸的鄙视了。。。（连个性能最差的冒泡排序思维都不会，要你何用= =），第二天回去，看了啥是排序，真的捶胸了半天，名字叫得那么好听，原来是这个。。。

简单的排序算法基本是下面这几种，其中的话冒泡排序，选择排序，插入排序是性能最差，实际应用基本不用但也是最简单，能提高你算法信心的几个小排序方式。

下面的话，我们一个个来实现，假如我们要让[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]从小到大排列。

既然要排列，我们第一反应肯定是比较，大的放后边小的放前边，对吧，两两进行比较。

1

冒泡排序

先拿第1第2个数比较，谁大谁后面，接着第2个跟第3个，还是谁大谁后面，继续第3第4，第4第5。。。这样进行了一轮之后，你是不是可以很肯定，最后的那个数一定是最大的？接下来混乱的序列就少了一位了对吧？就继续剩下的序列继续上面的一轮。而你仔细想一想这个过程，12， 23， 34，...有没有种演唱会现场一波波人浪冒出来的感觉？嗯，没有错，这就是冒泡，像一块软绵绵的地毯，里面有一颗玻璃珠在滚动，滚着滚着这个地毯就有序了。= =嗯，这就是冒泡排序。下面看看它的代码是怎样。

2

选择排序

上面的是最简单的排序了，人的第一直觉就能产生的一种解决问题的思路。但是呢？思维肯定是不断进步的，不可能一直停滞不前的，为什么呢？人浪排序不是很好吗？额不对，冒泡排序不是还不错嘛？简单直观，但是你要知道，有些人的脑回路不一定如此直观，他们解决问题的思路是这样的：

他觉得，我每次比较后符合要求的都去交换，有些处于中间值的，不是要不断的被交换？不是很浪费时间？我能不能选出这段序列中最大的那个数，然后放到最后边？

答案是肯定的，怎么做呢？既然是序列，代码中是数组，那有一个下标，我先把第一个数据给存起来，这个数不断的从第1项比到最后一项，当谁的值比他大时，他就把他的值存起来，这样一轮过后，它拿到了最大值，这时候就把选出的这个数，仍最后。接下来那个第二大的仍这个最后的前面一项，一直到完成整个序列。这样这种通过不断选出剩余项最大值的方法叫做选择排序。

一起看看它的代码是怎样的吧：

这种选择排序，虽说没有了交换的过程，但又多了赋值的过程，实际上并不比冒泡强哪去，也还是那样，理论上的性能能稍微好那么一丢丢，基本可以忽略不计。

3

插入排序

跟冒泡和选择同一时期的，还有一个插入排序，插入排序的方式更加的简单，你想一个问题，假如你现在手上多了一个空的数组，那你会怎样排序？是不是先把第一个放到空数组后，往后拿过来的数都跟这个新数组的各个数比较，插入到某两个数（只需注意大的在你后面，小的在你前面就OK）之间，但是呢，实际上，新创建一个数组的开销是不算小的，没理由一个简单的算法都要这样做，所以可以这样：

抽出第2个数，这样就变成了前半段（你的新数组），跟后半段（原来的大数组），这样不断的把你后半段的数，插入到前半段，前半段大的就往后挪腾位置给新数插入，对吧？是不是也可以实现你想要的？一起看看这个插入排序是怎样实现的吧。

上面这3种排序，你是不是代码中要有两个for循环，而且是完全的遍历，一步步走的，对吧？一个用于每一轮的比较（这时候只是进行了某一个数的比较，或者说确定了某一个数在整个数组中它所处的位置），一个用于遍历整个数组，把每个成员都拿出来遛一遛。对吧，那就是n²，也就是时间复杂度O(n²)（个人理解，不一定非常准确，但个人认为还是比较好理解的，不至于说得很复杂）

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

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

堆排序

这时候还有一个性能也很不错的排序，用到完全二叉树的方式来的。

它又是怎么想的？卧槽（没文化的我只会这一句= =），不就个排序，非得弄那么多乱七八糟的？嗯，怎么说呢，这是一种思想，先不扯远一起看看具体是怎么样的吧。

堆，有大顶堆跟小顶堆之分，这里就不扯概念了，那个官方讲得很详细嗯也很官方= =，简单理解一下就是一个金字塔，你是帮主，你下面还有左右护法四大天王八大金刚十六罗汉，嗯就这样一直下去，而所谓的大顶堆就是作为帮主的你是住塔顶的，小顶堆呢？则相反，你们帮最小最小的那个小弟就在那。大概是这样哈：

这个就是所谓的大顶堆，生活中是不是太常见了？（理解为主，请忽略图= =）

那它又是怎么做到排序的？

还记得选择排序是怎么排序的？就是选择一个最大数不断的插入到最后的对吧？但是选择最大数的那个过程是通过不断的比较，一个个位置挪动去得到的，那能不能跳着走？跳着扫描。实际上，分成堆只是让我们更好理解。

一起看看代码是怎么样实现的吧：

下面是做的一个简单的性能测试

① 普通插入排序与快速排序的速度对比（数据量20万）：

可以看到在20万随机数（0-10000）的排序中，快排所花的时间不足100个时间单位，而插入排序要超过50000个。普通的O(n²)的性能与最好情况O（nlogn）的快排是完全没法比（数据量越庞大结果越明显）。

② 希尔排序与快速排序对比（数据量2000万）：

由于这两个排序都是极不稳定的，但是从测试的几次结果看，希尔排序的性能会略微优于快排（语言：JAVAscript）

③归并排序与希尔排序

归并排序相对于希尔，快排的不稳定来说，归并排序最好跟最坏的情况均是nlogn，是稳定且快捷的排序算法。利用的正是完全二叉树的思维模式。

④堆排序与归并排序

也是2000万1-10000的随机数排序。