6.堆排序

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。

所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。

堆排序.png

，这就是一个典型的二叉堆。

堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，依次类推，最终得到排序的序列。

补充知识：完全二叉树

二插树.png

二叉树：是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

完全二叉树：是由满二叉树而引出来的，如果我们将一棵满二叉树由上到下，由左至右，每个结点都用数字编号，另外一个二叉树也同样由上到下，由左至右，每个结点都用数字编号，二叉树中的每个结点都可以在满二叉树中一一对应，我们称这个二叉树为完全二叉树。所以一棵满二叉树一定是个完全二叉树，而完全二叉树不是满二叉树。

完全二叉树的数组表示法

二叉树数组.png

A:0 B:1 C:2 B=20+1 C=2(0+1)

B:1 D:3 E:4 D=21+1 E = 2(1+1)

由此可以退出两个重要的推论：

*推论1*：对于位置为K的结点 左子结点=2k+1 右子结点=2(k+1)

验证：C:2 22+1=5 2(k+1)=6

*推论2*：最后一个非叶节点的位置为 (N/2)-1，N为数组长度。

7.堆排序（降序）示例

堆排序1.png

堆的初始化

很明显，这个二叉树不符合最大堆的定义，需要初始化为最大堆，从*最后一个非叶节点*开始，从下到上，从右到左调整
最后一个非叶节点在8/2-1=3的位置，也就是值为9的元素，将它和自己的叶节点进行比较并交换

堆排序2.png 堆排序3.png 堆排序4.png

8.计数排序

计数排序是一个排序时不比较元素大小的排序算法。

计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。

如果一个数组里所有元素都是整数，而且都在0-K以内。那对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

计数排序.png

计数排序（升序）示例

1、初始化一个大小为（5+1）的计数数组（所有元素初始值为0），遍历整个原始数组，将原始数组中每个元素值对应计数数组下标中的元素大小+1

计数排序2.png 计数排序3.png 计数排序4.png

注意点

实际应用中我们会同时找出数组中的max和min，主要是为了尽量节省空间。试想[1003, 1001, 1030, 1050]这样的数据要排序，真的需要建立长度为1050 + 1的数组吗？我们只需要长度为1050 - 1003 + 1= 48的数组（先不考虑额外+1的长度），就能囊括从最小到最大元素之间的所有元素了。

如果待排序数组的元素值跨度很大，比如[99999, 1, 2]，为三个元素排序要使用99999 - 1 + 1的空间，实在是浪费。所以计数排序适用于待排序元素值分布较连续、跨度小的情况。

9.桶排序

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。

基本步骤是：

l 根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；

l 将落在特定范围内的所有元素放入对应的桶中；

l 对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排；

l 按照划分的范围顺序，将桶中的元素依次取出。排序完成。

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

桶排序（降序）示例

桶排序.png

10.基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。比如对于数字2985，从右往左就是先以个位为关键字进行排序，然后是十位、百位、千位，总共需要四轮。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

基数排序（降序）示例

基数排序.png

基数排序有两种方法：

l MSD 从高位开始进行排序

l LSD 从低位开始进行排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

l 基数排序：根据键值的每位数字来分配桶

l 计数排序：每个桶只存储单一键值

l 桶排序：每个桶存储一定范围的数值

外部排序

有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（我们一般的排序都是在内存中做的，所以称之为内部排序，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序，这种归并方法由两个不同的阶段组成：

1、采用适当的内部排序方法对输入文件的每个片段进行排序，将排好序的片段（成为归并段）写到外部存储器中（通常由一个可用的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。

2、利用归并算法，归并第一阶段生成的归并段，直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并，而内存大小只能容纳750个记录，在第一阶段，我们可以每次读取750个记录进行排序，这样可以分六次读取，进行排序，可以得到六个有序的归并段

每个归并段的大小是750个记录，记住，这些归并段已经全部写到临时缓冲区（由一个可用的磁盘充当）内了，这是第一步的排序结果。

完成第二步该怎么做呢？这时候归并算法就有用处了，算法描述如下：

1、将内存空间划分为三份，每份大小250个记录，其中两个用作输入缓冲区，另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并，先从每个归并段中读取250个记录到输入缓冲区，对其归并，归并结果放到输出缓冲区，当输出缓冲区满后，将其写道临时缓冲区内，如果某个输入缓冲区空了，则从相应的归并段中再读取250个记录进行继续归并，反复以上步骤，直至Segment_1和Segment_2全都排好序，形成一个大小为1500的记录，然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

2、对归并好的大小为1500的记录进行如同步骤1一样的操作，进行继续排序，直至最后形成大小为4500的归并段，至此，排序结束。

排序算法总结

排序总结.png

名词解释

算法的稳定性

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。

复杂度

人总是贪婪的，在做一件事的时候，我们总是期望着可以付出最少的时间、精力或者金钱来获得最大的回报，这个类比到算法上也同样适用，那就是花最少的时间和最少的存储做成最棒的解决办法，所以好的算法应该具备时效高和存储低的特点。这里的「时效」是指时间效率，也就是算法的执行时间，对于同一个问题的多种不同解决算法，执行时间越短的算法效率越高，越长的效率越低；「存储」是指算法在执行的时候需要的存储空间，主要是指算法程序运行的时候所占用的内存空间。

从我们日常的经验就可以得知，一般来说，如果处理一件事情，这件事情越大，那么我们处理所花费的时间和精力就越多，在算法中同样也如此，所以我们在讨论算法复杂度时，往往需要考虑这个待处理数据的大小，我们把待处理数据的大小称之为数据的规模大小。讨论一个算法的复杂度，往往也就是寻找程序的运行时间是如何随着问题规模的变化而变化。

而有的时候算法的运行时间还取决于数据本身分布性质而不仅仅是「问题的规模大小」。对于这样的算法，我们把它们的执行情况分为「最优情况」、「最坏情况」和「平均情况」来讨论。

某个特定的数据集能让算法的执行情况极好，这就是最「最好情况」，而另一个不同的数据会让算法的执行情况变得极差，这就是「最坏情况」。不过在大多数情况下，算法的执行情况都介于这两种极端情况之间，也就是「平均情况」。

对于「最优情况」，没有什么大的价值，因为它没有提供什么有用信息，反应的只是最乐观最理想的情况，没有参考价值。「平均情况」是对算法的一个全面评价，因为它完整全面的反映了这个算法的性质，但从另一方面来说，这种衡量并没有什么保证，并不是每个运算都能在这种情况内完成。而对于「最坏情况」，它提供了一种保证，这个保证运行时间将不会再坏了，所以一般我们所算的时间复杂度是最坏情况下的时间复杂度，这和我们平时做事要考虑到最坏的情况是一个道理。。

时间复杂度：

一个算法执行所耗费的时间。

空间复杂度：

对一个算法在运行过程中临时占用存储空间大小的量度。

常见复杂度

在各种不同算法中，若算法中语句执行次数(占用空间)为一个常数，则复杂度为O(1)；

当一个算法的复杂度与以2为底的n的对数成正比时，可表示为O(log n)；当一个算法的复杂度与n成线性比例关系时，可表示为O (n)，依次类推。

由小到大：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

排序算法时间复杂度助记

冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O([图片上传失败...(image-292a33-1608174401909)])（外循环找元素O(n)，内循环找位置O(n)）

快速、归并、希尔、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（外循环找元素O(n)，内循环找位置O(logn)）相关

基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数

快速排序的优势

从平均时间来看，快速排序是效率最高的：

快速排序中平均时间复杂度O(nlog n)，这个公式中隐含的常数因子很小，比归并排序的O(nlog n)中的要小很多，所以大多数情况下，快速排序总是优于合并排序的。

而堆排序的平均时间复杂度也是O(nlog n)，但是堆排序存在着重建堆的过程，它把根节点移除后，把最后的叶子结点拿上来，是为了重建堆，但是，拿上的值是要比它的两个叶子结点要差很多的，它要比较很多次，才能回到合适的位置。堆排序就会有很多的时间耗在堆调整上。

虽然快速排序的最坏情况为排序规模（n）的平方关系，但是这种最坏情况取决于每次选择的基准， 对于这种情况，已经提出了很多优化的方法，比如三取样划分和Dual-Pivot快排。

同时，当排序规模较小时，划分的平衡性容易被打破，而且频繁的方法调用超过了O(nlog n)为O(n2)省出的时间，所以一般排序规模较小时，会改用插入排序或者其他排序算法。