时间：2020/4/28
数据结构与算法 | 系列
正文共计6000+字，19张讲解算法图片，14张代码截图，所有代码均可在笔者的（）上获取，或者文末左下角阅读原文可直接跳转 。
阅读文章之前，来思考个问题：为什么排序是学习算法的“入门”呢？简单？
排序有哪些好处？
数据较容易阅读。数据较利于统计和整理。可大幅减少数据查找的时间。……
排序算法分析些什么？
排序算法的执行效率最好、最坏、平均情况下的时间复杂度。以及对应的要排序的原始数据是什么样的，因为有序度不同的数据对执行效率是有影响的。时间复杂度的系数、常数、低阶。时间复杂度反应的是增长趋势，通常忽略系数、常数、低阶，但是对于小数据量，同阶时间复杂度排序算法对比也要把这些考虑进来。基于比较的排序算法，涉及到元素的比较和交换，所以也要考虑比较次数和交换（或移动）次数。排序算法的内存消耗内存的消耗通过空间复杂度来衡量。空间复杂度是的排序算法也称原地排序算法。排序算法的稳定性稳定性是指，序列中存在等值的元素，排序之后，一样的元素之间原来的先后顺序不发生改变。稳定性越好，时、空复杂度效率自然也就越优。
排序算法简单总结 & 目录
冒泡排序（交换排序）
原理： 从第一个元素开始，比较相邻的元素的大小，若大小顺序有误，则对调后再进行下一个元素的比较。特点： 若有n个数，则需要扫描 n-1 次。每次扫描都会确定一个最大的数。
动态图解：
代码实现：
算法分析：最好情况（已经有序）下，只需要进行一次冒泡操作，时间复杂度是；最坏情况（完全倒序）下，需要冒泡n次，时间复杂度是；最差情况下的初始状态有序度（数组中具有有序关系的元素对的个数）是0，需要进行次交换。最优情况初始状态有序度是，不需要进行交换，取中间值来表示平均情况，所以平均复杂度是。相邻元素大小相等时不做交换，所以属于稳定的排序算法。冒泡只涉及相邻数据的交换操作，只需要常量级的临时空间，所以属于原地排序算法。
选择排序
原理：依次选择数列中的一个元素，再从该元素后面的所有元素中找出最小值，和该元素交换位置。特点：交换操作最大为 n-1 比冒泡法少很多。比较操作最大为 n(n-1)/2, 比较次数与关键字的初始状态无关。
动态图解：
代码实现：
算法分析：最优情况（有序）下，搬移一次，常数个数据，只需要遍历有序数据，找到合适的位置插入即可，所以最好时间复杂度是；最差情况（倒序），每次都是在最前面插入，每次要搬移大量数据，所以最坏时间复杂度是；每次插入数据都相当是在数组中插入数据，而数组中插入一个数据的时间复杂度是，所以执行n次的插入操作，平均时间复杂度是 。如数据元素相等，后面出现的元素插入的前面出现的那个元素后面就保证了原有的顺序不变，属于稳定性排序算法。不需要额外的存储空间，空间复杂度是，属于原地排序算法。另，插入只需要1次赋值，冒泡需要3个，所以插入比冒泡更优。
插入排序
原理： 将数组中的元素与已排好的数据进行比较。先排好前面两个数据，再把第三个元素插入到适当的位置，依次类推。插入数据之后，该数据后面的所有数据都往后挪一位。特点： 时间复杂度是, 适用于小数据量的排序。原始记录的键值大部分已经排好序的情况下，插入排序非常有效率。
动态图解：
代码实现：
算法分析：最好、最坏、平均时间复杂度都是。因为选择排序，每次都是从剩余未排序元素中找最小值和前面元素交换，所以不具有稳定性。只需要常数级额外临时空间，属于原地排序算法。以上三种排序算法时间复杂度都比较高，适合小规模数据。算法分析总结表格如下：
希尔排序原理： 将数据首先划分成Y（如，8 div 2，即Y=4，称为划分数），得到4个区块，插入法排好这些区块之后，再缩小间隔，依次类推。特点： 希尔排序就是插入排序的改进版本，优化了插入排序中数据搬移的次数。相当于分组插排，先排组内得到新的数据，再缩小分组继续插入排序。
动态图解：
（此图来源于网络，侵删）
代码例子：
复杂度分析：
因为希尔排序是利用分组插排，分组的时间复杂度和递归的时间复杂度类似，也是O(nlogn)。所以希尔排序的时间复杂度是O(nlogn)。对于递归的时间复杂度参见下文。排序过程中不需要很多额外的存储空间，所以是原地排序算法，即空间复杂度为O(1)。
由于排序过程多次插入排序，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以，希尔排序是不稳定的。
归并排序
原理： 对多个已经排好序的数列通过合并的方式，将其组合成一个大的排好序的数列步骤： ① 将N个长度为1的键值合并成N/2个长度为2的键值组；②将N/2个长度为2的键值组合并成N//4个长度为4的键值组；③依次类推，知道最后合并为一组长度为N的键值组为止。特点： 时间复杂度是O(nlogn)，是一种稳定的，（基于比较）的最佳的排序方法。利用分而治之的思想。归并排序非常适合分类非常大量的输入。
动态图解：
代码例子：
还有一个更巧妙的解法如下：
算法分析：简单说下递归算法的时间复杂度分析，下篇文章再详细介绍：如果定义求解问题a的时间是T(a)，a问题又可分解为b和c问题，求解b、c问题的时间分别是T(b)和T(c)，就有如下的递推关系式：T(a) = T(b) + T(c) + K 。其中，K是将子问题b和c的结果合并成问题a的结果所消耗的时间。时间复杂度由递归算法的复杂度分析可知，a问题分解为子问题b和c，那么有对应时间关系 T(a) = T(b) + T(c) +K。现假设对n个元素进行归并排序所需时间为T(n)，分解两个子数组排序的时间是T(n/2)，而合并两个子数组的时间复杂度是（合并用插入排序，最好情况就是 ），可以得到归并排序的时间复杂度计算公式如下：T(1) = C ; n=1时，只需要常量级的执行时间，用C表示。
T(n)=2*T(n/2) + n ; n>1， 后面的n意思就是合并两个子数组的O(n)时间复杂度。递推公式可以解得 ，当 时，可得到，带入T(n)可解得 。所以归并排序的时间复杂度。归并排序的执行效率和排序的原始数据的有序程度无关，所以最好、最坏、平均时间复杂度都一样。空间复杂度归并排序合并数组的时候需要申请额外的内存空间，任意时刻只会使用一个临时的内存空间，使用完后就释放了，临时空间的大小最大不超过n个数据的大小，所以空间复杂度是O(n)，也就是说归并排序不是原地排序算法。稳定性原数组拆分才前后两个数组，若有相同元素，后面数组中的元素放在前面相同元素之后即可，属于稳定排序算法。
快速排序（分割交换排序法）
原理： 首先假设一个中间值，利用这个中间值把待排序的数据分成两部分。小于中间值的数据放在中间值的左边，其他数据放在中间值的右边。对左右两边的数据做同样处理，以此类推。特点： 目前公认的最快的排序法，也运用了“分而治之”的思想（归并也是）。
方法一： 直接如原理所述，这个方法非常容易理解代码例子：
方法一非常简单，这就是快排的核心思想。不过，上述方法不是最优方法，这就是为啥平时我们看到的快排都需要有“一堆”代码来实现。我在这里详细分析一下这个算法的缺点在哪。
这种实现方法，在每次比较之后都需要额外的内存空间来保存小于pivot和大于pivot的数据，所以空间复杂度就变成了 。因为我们要优化这种方式，让其变成原地排序算法，也就是空间复杂度变为 。这就需要引入“分区”的思想，而这也是快排一个重难点，这是很巧妙的思想，所以这里就讲讲如何利用“分区”的思想实现原地排序。分区思想：假设现在有一个数组A，下标从p到r。先把第一个数A[p]作为pivot（基准/分区点），然后用下标 i 把数组A[p+1,…,r]分成两部分，把前面部分 A[p+1,…,i-1] 姑且称作“已处理部分”其中每个元素都是小于pivot的，后面A[i,…,r]称为“未处理部分”。
那我们现在要做的就是，从未处理部分中取出一个元素 A[j] 和pivot比较，如果小于pivot，则将该元素放到已处理部分的末尾，也就是A[i]的位置。实现这个过程的做法就是交换，即 A[i]与A[j]交换。假设 A[p,…,r]=[5,3,8,2,6]，下面用图示来说明分区的过程。
分区结束之后，就得到左边小于pivot的部分，和右边大于pivot的部分。对左右两边递归，就可以实现完整快速排序。快排实在是太重要了，看不懂上面那个图示的话，再用文字写个流程，结合来理解一下。我真是操碎了心♥啊！！！
方法二： 利用分区思想的排序过程如下图动态图解：
代码例子：
方法二是从一个方向扫描，方法三和方法四是从两个方向扫描，理论上都差不多。前面理解的话，后面不难理解。另外说一句，pivot的选择直接影响到排序效率，一般是随机初始化。
方法三步骤 ： ① 选择第一个元素作为基准元素pivot；②：从右向左找到小于pivot的数，若存在，R[i]和R[j]交换，i++；③ 从左往右扫描，若存在大于pivot的数，则R[i]和R[j]交换，j--；④ 重复②③，直到 i=j ，返回该位置，也就是pivot。⑤ 以pivot为界，把一个数据序列分成两个子数据序列，然后对子序列递归快速排序。（左序列都比pivot小，右序列都比pivot大）代码例子：
方法四步骤： ① 假设键值 作为中间值；② 从左向右找出键值 ,使得 ；③ 从右向左找出键值 , 使得 $K_j代码例子：
算法分析：快排和归并排序都是采用的分治、递归的思想，所以时间复杂度也应该是。但是数据结构排序算法原理-【第3篇 | 数据结构与算法】一举消灭十大常见（常考）排序算法（原理+动图+代码，快速排序和序列的有序度是有关系的，最好时候才能均分。如果序列已经有序（eg.1 2 3 4 5）,选择最后一个元素最为pivot的话，大约需要进行n次分区操作，每次分区操作平均要扫描n/2个元素，时间复杂度就从（最好、平均情况）退化成了（最差情况）数据结构排序算法原理，这种情况概率极小，可以随机选择pivot来避免出现这种情况。分区的时候数据结构排序算法原理，如果把小于pivot的数放在一个数组，大于pivot的数放在另一个数组，这样的思路实现简单，但是就需要很多额外的内存空间。但是可以优化分区的思路，实现一个空间复杂度为O(1)的原地排序算法。基于此，快排比归并排序更常用。分区的过程涉及到元素的交换操作，所以一样的元素的相对位置就有可能发生变化，因此快速排序并不是一个稳定的排序算法。
桶排序法
原理：先将要排序的数据分到几个有序的桶里，对每个桶里的数据分别单独排序。然后把桶里的数据按顺序取出，最后得到的就是排好序的数据。特点：适用于数据容易划分成m个桶，且桶于桶之间有天然的大小顺序，数据范围有小的情况。图解分析：
代码实现：
算法分析：假设有n个数据，均匀分到m个桶中，则每个桶里有k=n/m个元素。每个桶里用快排的话，时间复杂度是，总的时间复杂度就是，即，m越大时，就越小，所以桶排序的时间复杂度接近。因为快排不稳定，所以桶排序也不稳定。
计数排序法
原理：和桶排序相比，计数排序相当于把n个数据放在n个桶里，依次按序读取每个桶里的数据即可。只需要遍历桶里的数据就可以得到排序结果，所以时间复杂度是。特点（适用场景）：数据范围小；非负整数（或者可以转化为非负整数）；各个桶之间的数据分布比较均匀。
动态图解：
代码实现：
上面这个方法中我用到了中的()函数，这算是一个小trick。当然这种思想也是不错的，还有一种比较主流的实现计数排序的方式我下面也介绍一下，因为这种实现思想也很巧妙，值得学习。光用文字不容易讲清楚，所以我会画一些图来辅助理解。实现方式分析：假设现在有一个待排序数组 A[7]=[2,0,3,2,4,3,2]，遍历数组A然后用5个桶（数组B）分别记录下来每个数出现的次数。其中index 对应 原数组中的数据，value对应该数据出现的次数。
从上图中可以看到，index=3出现的次数是value=2次，小于index=3的数出现了4次。因此，index=3的数据在排好序的数组（用C表示）中，对应的下标位置是4和5。如下图所示，最后排好序之后，数据3一定是这么这么存储的。
所以，接下来就是需要思考，该如何把数据存储在相应的位置上。首先，先对数组B按顺序求和，然后数组B就会变成如下所示。也就是说B[k]里存的是小于等于k的数的个数。
其次，从后往前遍历原数组A[7]=[2,0,3,2,4,3,2]。当遍历第一个2时，就从数组B[2]中取出对应的value=4，放到C[3]（第4个元素）中，因为小于等于2的数据有4个。然后B[2]要减少1，即B[2]=3（减1的原因是为了计算后面出现的重复数据）。接下来遍历3时，从数组B[3]中取出6放到C[5]中，然后B[3]要减1，即B[3]=5。完整过程如下图所示，实质就是把数组B中的index变成value，value变成index的一个过程。
代码实现：代码中的 alist，，分别对应上图中的A[]，B[]，C[]。
复杂度分析：计数排序本质上就是桶排序的一种特殊情况，所以复杂度和桶排序是一样的，这里 就不再赘述了。
基数排序法
原理： 根据不同位数上的大小来进行排序。设置0~9十个暂存数组，首先比较序列中每个数的个位数，排出顺序，放到相应数组中。然后按十位数上的大小排序，依次类推。（最低位优先）特点（适用场景）：数据可以分割出独立的“位”来进行比较；位与位直接有递进关系（如十位比个位小）；位的数据范围不能太大，可以用线性排序来解决，否则就不是了（如数字“位”的数据范围是10，字母是26等）。动态图解：
代码例子：
复杂度分析：用桶排序或者计数排序对每一位（eg. 十位或百位）进行排序可以做到，若有k位就是，k一般是常量，所以基数排序的时间复杂度也是。不需要进行元素之间的比较操作，属于一种“分配式排序”，是一种稳定的排序。
堆排序法
原理：堆排序的过程类似于堆的删除操作。第一步，把堆顶元素和下标为n的堆尾元素交换位置；第二步，将前n-1个元素重新堆化；第三步，再把堆顶元素和下标为n-1位置的元素交换，依次迭代。直到最后剩下一个元素为止。特点： 堆排序两个步骤包括建堆和排序，排序的两个步骤是交换和堆化。
动态图解：建堆的图解请参见上篇文章，排序图解如下。
完整实现可参考下图[6]
代码实现：建堆的原理实现在上一篇文章最后已经介绍，这里为了方便理解再把代码写一下方便说明，具体内容参见上篇文章（）当然，你假设已经有一个建好的堆，直接用来排序就好了，排序才是这篇文章的重点。
复杂度分析：关于建堆的复杂度为什么是 ，上篇文章已经详细介绍过，这里就不再赘述了。前面已经说了，堆排序要包含建堆的过程的，因为实际通常不可能直接拿来一个堆做排序。而排序的过程主要是堆化，其时间复杂度是 ，所以堆排序总的时间复杂度是 。排序时只需要申请个别的临时存储空间用来做交换操纵，所以堆排序是原地排序算法。由于堆排序在交换节点的过程中，可能会改变相同数据的原始位置，所以堆排序不是稳定的排序算法。
参考资料：各种排序算法的稳定性排序和不稳定性排序详解：支持中文的算法可视化网站：《图解算法》使用，吴灿民 胡昭民 著，清华大学出版社实现快速排序算法：排序总结：
原创不易，您的“在看”
就是支持我最大的动力！
感谢您一直以来的鼓励！
文章来源:http://mp.weixin.qq.com/s?src=11×tamp=1655546685&ver=3868&signature=CB7Nh04lPlurs4s9iirjPxN4O6XHXSbuUyAlGwcGVyksGakuQVix79XiYBUeoMHJ1d-kWBRVY45AopV178v6MlRrH4taeEzxMuV3dif1fWFAZH*oc4dkPhnPYVY-HV&new=1