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

男娘i 2022-04-04 10:08 229阅读 0赞

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

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

![1240][]

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

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

冒泡排序

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

![1240 1][]

选择排序

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

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

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

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

![1240 2][]

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

插入排序

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

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

![1240 3][]

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

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

希尔排序

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

看一下希尔排序是怎么实现的哈：

![1240 4][]

归并排序

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

A            B

1568        2479

![1240 5][]

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

![1240 6][]

快速排序

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

**具体的代码怎么实现呢？**

这样很直观的我们就想到，嘿我弄两个数组，装高个子跟矮个子，然后再concat回来对吧？当然记得把中间那家伙给放进去，别漏了。看下下面：

![1240 7][]

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

![1240 8][]

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

嗯，有了一个了，当然得有无数次，左边那块再继续做这个事，右边的也一样，当右边跟左边再加上中间的数长度刚好为3或小于3的时候不就OK了？

堆排序

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

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

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

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

![1240 9][]

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

![strip][]

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

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

![1240 10][]

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

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

![1240 11][]

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

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

![1240 12][]

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

**③归并排序与希尔排序**

![1240 13][]

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

**④堆排序与归并排序**

![1240 14][]

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

***扩展阅读***

[面试经验分享之数据结构、算法题][Link 1]

[程序员如何快速准备面试中的算法][Link 2]

[写完这个排序算法，为什么面试官让我滚？][Link 3]

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

> ### 微信公众号：javafirst ###
> 
> ### 扫码关注免费获取更多资源  ###
> 
> ![70][]

[1240]: /images/20220404/19d89bac2e864f53933d5a72d64377d8.png
[1240 1]: /images/20220404/8763263dd2e749dbb721b98997e1f4f7.png
[1240 2]: /images/20220404/20fe4e5cfe7e44d5a7ac3301880d2332.png
[1240 3]: /images/20220404/545847c613e94bb2a2c367905886f3fb.png
[1240 4]: /images/20220404/cc88699f22fc4122b04c1b630da7a2fd.png
[1240 5]: /images/20220404/45e37157fc084eb4b98c2d7f65775b23.png
[1240 6]: /images/20220404/416d3130ac964549a9d847e23c14529c.png
[1240 7]: /images/20220404/ac182a5ae4af46acb7272b3d8fc64c29.png
[1240 8]: /images/20220404/3acc659c3db84c6787d4d97cedf95e99.png
[1240 9]: /images/20220404/9ff3ee7f197a452c817b6ed3493301fa.png
[strip]: /images/20220404/2c6cf2d450da4267bfc1d2ae67fbea13.png
[1240 10]: /images/20220404/3021727e36be4e229f9f5737694587d3.png
[1240 11]: /images/20220404/9027c311a0e147bd8339c1e17cfb8c56.png
[1240 12]: /images/20220404/f40843de2ca44a7c9f1a433d9d524ef8.png
[1240 13]: /images/20220404/4632b928fc5a496181578eed81db0d0e.png
[1240 14]: /images/20220404/61d938dfc45f4ec0ba352544decbd62c.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485266&idx=1&sn=2e4be6a7d932596639136c6c35022e25&chksm=fe79568ac90edf9c7ad7927257455bb998921cc97b4ab6507438a5f511b3bd454caae5a78c13&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485783&idx=1&sn=5f5cbec2174bcd5a4cf289863f451ec3&chksm=fe79588fc90ed1996078351fd41e054458540b6670fa3427bb97a6a54bad23ea53532093d359&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485907&idx=3&sn=712bd7418b762b76c70f665c40a7d9b1&chksm=fe79580bc90ed11d6a9e1f9b8500ba75c0d185ce2d784020842a82dd4d47f7ba3911a8badfe2&scene=21#wechat_redirect
[70]: /images/20220404/2d4f948df4284a1aa35ae061ec08c827.png