来源：IT技术思维原创，转载请注明原出处内容提供：苏勇， Google 资深软件工程师
算法学习其实是一种学习和提高思维能力的过程。无论是在面试还是实际的工作和生活中，都会碰见一些从没遇到过的问题
真正需要熟练掌握的排序算法应该是以下几种：
1.基本的排序算法：冒泡排序（Bubble Sort）、插入排序（Insertion Sort）
2.常考的排序算法:归并排序（Merge Sort）、快速排序（Quick Sort）、拓扑排序（Topological Sort）
3.其他排序算法：堆排序（Heap Sort）、桶排序（Bucket Sort)
下文将用10min结合例题和代码针对排序算法进行探讨。
冒泡排序
1、基本思想
给定一个数组，把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。具体的实现方法就是：每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。元素相互比较的过程就是冒泡排序的核心操作。
01例题分析
给定数组 [2, 1, 7, 9, 5, 8]，要求按照从左到右、从小到大的顺序进行排序。
解题思路：可以从左到右依次冒泡，把较大的数往右边挪动即可。具体操作如动图：
数组已经排好序后。可以用算法在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。
2.代码示例
冒泡排序的代码如下：
a.首先我们定义了一个布尔变量hasChange，用来标记每轮遍历中是否发生了交换。
b.在每轮遍历开始的时候，将hasChange设置为false。
c.接下来，进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生。
d.不断地两两交换，直到在这一轮，把最大的数放置到数组的最末端。
3、算法分析
冒泡排序算法的空间和时间复杂度。假设数组的元素个数是n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是O(1)。至于时间复杂度，有以下几种情况：
a.给定的数组按照顺序已经排好
在这种情况下，只需要进行n - 1次的比较，两两交换次数为0，时间复杂度是O(n)，这是最好的情况。
b.给定的数组按照逆序排列
在这种情况下，需要进行n(n - 1) / 2次比较，时间复杂度是O(n^2)，这是最坏的情况。
c.给定的数组杂乱无章
在这种情况下，平均时间复杂度是O(n^2)
由此可见，冒泡排序的时间复杂度是O(n^2)，但它是一种稳定的排序算法，所谓稳定，也就是说如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。
插入排序
1、算法思想
在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。
插入排序的基本思想就是不断地将尚未排好序的数插入到已经排好序的部分。
02例题分析
对数组 [2, 1, 7, 9, 5, 8] 进行插入排序。
解题思路：将数组分成左右两个部分，左边是已经排好序的部分，右边是还没有排好序的部分，刚开始，左边已排好序的部分只有第一个元素2。接下来，我们对右边的元素一个一个进行处理，将它们放到左边。具体操作如下动图：
2、代码示例
a.首先，我们将数组的第一个元素看成是已经排好序的部分，于是我们从第二个元素开始，即i从1开始遍历数组。
b.每次在外围循环开始的时候，把当前i 指向的值用current保存起来，以便将来把它插入到合适的位置。
c.接下来，利用指针j进行内循环，不断地拿它和current值进行比较，如果发现j所指向的值比current值大，那么就把这个数往右移动一位。
d.当内循环结束后，j + 1所指向的位置就是我们要把current值插入的位置了。
最后不断地重复，直到所有的数都排好。
3、算法分析
插入排序算法的空间和时间复杂度分析如下。
假设数组的元素个数是n，由于在整个排序的过程中，直接在给定的数组里面进行元素的两两交换，空间复杂度是O(1)。至于时间复杂度，有以下几种情况：
a.给定的数组按照顺序已经排好
在这种情况下，我们只需要进行n - 1次的比较，两两交换次数为0，时间复杂度是O(n)，这是最好的情况。
b.给定的数组按照逆序排列
在这种情况下，我们需要进行n(n - 1) / 2次比较，时间复杂度是O(n^2)，这是最坏的情况。
c.给定的数组杂乱无章
在这种情况下，平均时间复杂度是O(n^2)
由此可见，和冒泡排序一样，插入排序的时间复杂度是O(n^2)，并且它也是一种稳定的排序算法。
归并排序
1、算法思想
归并排序的核心思想是分治，所谓分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。
可以说，归并排序将分治的思想体现得淋漓尽致。归并排序的思路就是，一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子
数组里面只有一个元素，这个时候才开始排序，排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后
把整个数组的顺序排好。
2、代码示例
让我们看看如何写归并排序的代码，首先看看排序的主体函数：
主体函数非常简洁：
1.首先判断是不是只剩下最后一个元素了。
2.接着从中间将数组分成两个部分。
3.接下来，分别递归地将左右两半排好序。
4.最后将排好序的左右两半合并起来。
接下来看看如何实现归并操作：
归并操作很容易理解。
首先复制一份原来的数组，之所以要这样做，是因为我们不仅要比较左右两半的数据，而且要修改原来的数组，如果不复制原来的数组直接进行修改，那么会导致将来的比较出现错误。
接下来，定义一个k指针表示从什么位置开始修改原来的数组，i指针表示左半边的起始位置，j表示右半边的起始位置。
在接下来的比较中，一共可能会出现四种情况：
1.左半边的数都处理完毕了，只剩下了右半边的数，我们只需要将右半边的数逐个拷贝过去就好。
2.右半边的数都处理完毕了，只剩下了左半边的数，我们只需要将左半边的数逐个拷贝过去就好。
3.右边的数小于左边的数，我们将右边的数拷贝到合适的位置，j指针往前移动一位。
4.左边的数小于右边的数，我们将左边的数拷贝到合适的位置，i指针往前移动一位。
03例题分析
利用归并排序算法对数组[2, 1, 7, 9, 5, 8]进行排序。首先不断地对数组进行切分，直到各个子数组里只包含一个元素。演示如下图：
合并能成功，先决条件必须是两个子数组都已经分别排好序了。
3、算法分析
归并算法是一个不断递归的过程，假设数组的元素个数是n，时间复杂度是T(n)的函数。把这个规模为n的问题分成两个规模分别为n/2的子问题，每个子问题的时间复杂度就是T(n/2)，那么两个子问题的复杂度就是2*T(n/2)，当两个子问题都得到了解决，即两个子数组都排好了序，就需要将它们合并，合并的复杂度是多少呢？很简单，一共有n个元素，每次都要进行最多n-1次的比较，所以合并的复杂度是O(n)，由此我们得到了如下的递归复杂度公式：
T(n) = 2*T(n/2) + O(n)
怎么解这个公式呢？需要不断地把一个规模为n的问题分解成规模为n/2的问题，一直分解到规模大小为1，如果n等于2，我们只需要分一次，如果n等于4，则需要分2次，这里的次数是按照规模大小的变化分类的：
以此类推，对于规模为n的问题，一共要进行log(n)层的大小切分。在每一层里，都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是O(n)，所以整体的复杂度就是O(nlogn)。
对于空间复杂度，由于合并n个元素需要分配一个大小为n的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是O(n)。最后，归并排序也是稳定的排序算法。
归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到。建议大家一定要把这个算法练熟。
快速排序
1、算法思想
快速排序也采用了分治的思想，策略就是：把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
如，现在要把班里的所有同学按照高矮顺序排成一排。老师先随机地挑选了同学A，让所有其他同学和A比高矮，比A矮的都站在A的左边，比A高的都站在A的右边。接下来，老师分别从左边和右边的同学里选择了同学B和C，然后不断地筛选和排列下去。
在分成较小和较大的两个子数组过程中，如何选定一个基准值（也就是同学A、B、C等）尤为关键。下面让我们通过例题来深入理解快速排序算法。
04例题分析
再对数组[2, 1, 7, 9, 5, 8]进行排序，按照快速排序的思想
解题思路：首先把数组筛选成较小和较大的两个子数组，随机从数组里选取一个数作为基准值，比如7好了，于是原始的数组就被分成了如下两个子数组：
这里需要注意的是，快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出来的时候，原始数组里的排列也被改变了。
接下来，在较小的子数组里选2作为基准值，在较大的子数组里选8作为基准值，继续分割子数组。
继续将元素个数大于1的子数组进行划分，得到：
可以看到，当所有子数组里的元素个数都为1的时候，原始数组也被排好序了。
2、代码示例
先是主体函数：
主函数非常简洁：
1.首先判断是否只剩下了一个元素，如果是，就不需要排序了，直接返回。
2.接着，利用partition函数找到一个随机的基准点。这个时候，基准点左边的数一定都小于基准值，而右边的数一定都大于基准值。
3.递归地对基准点左半边和右半边的数进行排序。
接下来看如何实现partition函数获得基准值，并将数组划分好。
1.首先，为了避免最糟糕的情况出现，我们随机地选择一个数作为基准值，将它放置到最右边，也就是hi指针的位置，所以，nums[hi]就是我们的基准值。
2.接着，从左到右不断地拿每个数和基准值比较，如果发现当前的数比基准值小，就将它放到指针i所指向的位置。循环完毕后，i指针之前的数都比基准值小。
3.最后将一开始放置在末尾的基准值放置到指针i的位置，这样一来，i 指针之后的数都比基准值大了。
4.返回指针i，作为基准点的位置。
3、算法分析
在解这道例题的过程中，被选出来的基准值都是当前子数组的中间数，这是快速排序的最佳情况，通过这样的分割，能保证对于一个规模大小为n的问题，能被均匀分解成两个规模大小为n/2的子问题，回顾一下，归并排序也采用了相同的划分方法。如此一来，快速排序在最优情况下的算法时间复杂度就是:
T(n) = 2 * T(n/2) + O(n)
这个O(n)如何得出来的呢？在把规模大小为n的问题分解成n/2的两个子问题时，需要判断是不是和基准值进行了n-1次比较。而这n-1次比较的复杂度就是O(n)。很显然，在最优情况下，快速排序的复杂度也是O(nlogn)。
最坏的情况是如果我们每次在选择基准值的时候，非常不幸运地选择了子数组里的最大或者最小值，也就是说每次都把子数组分成了两个更小的子数组，其中一个的长度为1，另外一个的长度只比原子数组少1。例如，对于数组来说，每次我们挑选的基准值分别是9,
8, 7, 5, 2的时候，我们的划分过程就变成了这样：
这其实和冒泡排序的过程类似了，意味着快速排序在最坏的情况下算法复杂度也变为了O(n^2)。可以通过随机地选取基准值就可以避免出现最坏的情况了。
空间复杂度，和归并排序不同，快速排序在每次递归的过程中，只需要开辟O(1)的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是O(logn)。
拓扑排序
和前面介绍的几种排序不同，拓扑排序应用的场合不再是一个简单的数组，拓扑是一种研究，它研究的是图论里面顶点和顶点连线之间的性质。拓扑排序就是要将这些顶点按照相连的性质进行排序。要能实现拓扑排序，得有几个前提：
1.首先这个图必须是有向图
2.图里面没有环
拓扑排序一般用来理清具有依赖关系的任务。举个最简单的例子，假设有三门课程A、B、C，如果想要学习课程C就必须先把课程B学完，要学习课程B，还得先学习课程A，所以得出课程的学习顺序应该是A -> B -> C。
1、算法思想
首先将问题用一个有向无环图（DAG, Directed Acyclic Graph）进行抽象表达，定义出哪些是图的顶点，顶点之间如何互相关联。接下来，可以利用广度优先搜索或深度优先搜索来进行拓扑排序。
利用广度优先搜索的思想比较直观易懂，下面我们就以一道简单的例题来学习如何对一个有向无环图进行拓扑排序。
05例题分析
有一个学生想要修完5门课程的学分，这5门课程分别用1、2、3、4、5来表示，现在已知学习这些课程有如下的要求：
1.课程2和4依赖于课程1
2.课程3依赖于课程2和4
3.课程4依赖于课程1和2
4.课程5依赖于课程3和4
那么这个学生应该按照怎样的顺序来学习这5门课程呢？
解题思路：可以把5门课程看成是一个图里的5个顶点，用有向线段按照它们的相互关系连起来，这个有向图里没有环，无论从哪个顶点出发，都不会再回到那个顶点。并且，这个图里并没有孤岛的出现，因此，我们可以对它进行拓扑排序，具体事例如动图：
一般来说，一个有向无环图可以有一个或多个拓扑排序的序列。
2、代码示例
在这里我们运用广度优先搜索的方法对这个图的结构进行遍历。在构建这个图的过程中，我们用一个链接矩阵adj来表示这个图的结构，用一个indegree的数组统计每个顶点的入度，由于篇幅有限，我们就不把具体的构建过程写出来了。我们这里重点看如何实现拓扑排序。
1.既然是要做广度优先搜索，我们一开始定义一个队列q。
2.将所有入度为0的顶点加入到队列q里。
3.不断地循环，直到队列为空。
4.在每次循环中，从队列中取出顶点，这个就是按照入度数目排序中最小的那个顶点。
5.然后将跟这个顶点相连的其他顶点的入度减一，如果发现那个顶点的入度变成了0，将其加入到队列的末尾，等待将来的处理。
3、算法分析
对于拓扑排序，统计顶点的入度需要O(n)的时间，接下来每个顶点被遍历一次，同样需要O(n)的时间，所以拓扑排序的时间复杂度是O(n)。
建议你利用深度优先搜索的方法对这道题实现拓扑排序。
结语
在这些排序算法中，归并排序和快速排序是最重要的知识点，除了要好好理解它们的思路，还必须要能写出没有bug的代码才行，因此要在课后多加练习呀。LeeCode（力扣）里面有很多关于拓扑排序的经典题目，强烈建议大家去试试。
网友评论