从零开始学算法：3.排序算法

一、背景

大家好，我是tiankonguse。
由于某些原因，经常有人想要学习算法，但是自己之前又没有相关经验，不知道从何做起。我思考了许久，计划写一个系列来分享如何入门学习算法。

上半年的时候就分享了《认识算法》和《了解套路长啥样》，本想接下来按专题进行分享，思考良久却发现对于算法，写文章不太好讲清楚，当面讲或者视频讲效果才是最佳的。
另外大部分算法感觉太简单，广度与深度都不好把握，于是自己内心比较矛盾，纠结了一段时间这个事情就给耽搁了。

现在又到了开学季，算法还是需要重新拾起来，这里以排序算法作为尝试吧。

二、基本知识

排序，顾名思义，就是把一串数据按照特定的排序方式进行排列的一种算法。
排序算法的输出必须满足两个原则：输出序列有序、输出序列是输入序列的一种排列组合。

一般情况下，排序算法是通用的，不管什么数据，按照这个算法都可以得到预期结果。
所以我们往往使用整数序列作为例子来分析排序算法是如何运行的，排序后的结果是整数满足递增。
下面我们就分别来看看常见的排序算法吧。

三、冒泡排序

冒泡排序是一种最容易理解的排序算法。
这个算法的基本思想如下：

1.比较相邻元素，如果第一个比第二个大，就交换他们。
2.对每一个相邻的元素做同样的操作，从第一个到最后一个。做完之后最后一个就是最大值。 3.针对所有元素重复以上步骤，除了最后一个。
4.持续步骤1~3，每次都会少一个数字，直到剩余一个数字为止。

如上图，外层循环每执行一次， [0, i] 之间通过若干次交换，i 位置变成了最大值。
如果你看其他人的冒泡排序，可能会发现 i 是从小到大循环的，其实会发现从大到小会更清晰。
复杂度：由于有两层循环，只不过每次比上次少循环1 次，不过复杂度还是 O(n^2)。

四、选择排序

选择排序和冒泡排序想法很像，都是循环序列，使得当前的序列的最大值处于一端。
先看冒泡排序，依次比较的时候，如果不满足增序，会修改中间状态的值。
而选择排序则是每次挑出最大值的位置，然后只交换一次。

具体思想如下：
1.遍历序列，选出当前序列的最大值，和最后一个交换。 2.不包含最后一个数字的序列重复步骤1。
3.每次数字少一个，直到数字剩一个为止。

复杂度：这个和冒泡算法的复杂度一样，也是O(n^2)。

五、插入排序

插入排序和冒泡也很类似，只不过冒泡每次都是在乱序序列内遍历，而插入排序则是在已排序的序列上扫描。

具体思想如下：
1.取第一个元素，认为已经排序。
2.取下个元素，在已经排序的序列中从后向前扫描。
3.如果该元素大于新元素，将该元素移到下一位。
4.重复步骤3，直到找到已排序的元素小于或等于新元素。
5.将新元素插入到该元素位置后面。
6.重复步骤2~5。

复杂度：依旧是O(n^2)。

六、归并排序

归并排序是分治法的一个经典应用。
基本思想是： 1.将序列平均分为两个子序列。
2.分别递归调用这个排序算法，使得子序列有序。 3.合并两个有序的子序列。

这里复杂度涉及到递归计算，公式是 f(n) = 2 * f(n/2) + n，一般使用递归树来计算。
对于f(n)的复杂度，有合并的O(n)和两个子数组 f(n/2) 得到。
而每个f(n/2) 也都是有合并的O(n/2) 和两个子子数组 f(n/2) 得到。全部展开后如下图，总复杂度就是各个节点的合并复杂度之和，恰好每层的和是 O(n)，共有 log(n) 层，所以总复杂度是 O(n log(n))。

七、快速排序

归并排序是先将序列从中间分两部分分别递归排序，然后再合并在一起。
而快速排序是另一种递归排序，我们来看看。

基本思想：
1.从序列中随机跳一个数字。 2.重新排列序列，将序列按照挑的数字分两部分，前一部分小于这个数字，后一部分大于等于这个数字。 3.步骤2得到的两个子序列分别按照步骤一和步骤二递归运行，直到数字为一个。

快排和归并排序类似，都是分而治之，所以复杂度都是O(n log(n))，不过对于快排，在极端情况会导致复杂度是O(n^2)。

八、堆排序

堆是一种很有用的树形数据结构，
以最大堆为例，堆的父节点必须大于两个子节点，递归推理，我们可以得出堆的顶点就是最大值。由于堆是标准的树，所以对节点的操作复杂度最坏情况是O(log(n))，我们依次从顶点取出最大值即可得到一个有序的序列，最终复杂度是O(n log(n))。
而构造堆也是一个一个节点插入的，所以构造堆的复杂度也是O(n log(n))。

排序的具体思想如下： 1.依次构建最大堆。
2.将堆顶元素与堆的最后一个元素交换，堆的大小减一、维护堆满足堆的特性。 3.重复步骤二，直到堆只剩一个元素。

九、其他排序

排序的方法很多，如计数排序、桶排序、基数排序、希尔排序。
另外排序还涉及到时间复杂度、空间复杂度、是否是稳定排序等，这里就不介绍了。
接下来我想想该分享啥算法，太基础了会感觉太简单，太难了文字又不好讲，确实很纠结。

本文首发于公众号：天空的代码世界，微信号：tiankonguse-code。