乱序.PNG

上面的同学请保持秩序。。。本章，来研究一下排序算法。
排序算法在大部分情况下并不具备直接商业应用的条件，但是对我们理解排序的本质思想是非常有帮助的，正所谓万变不离其宗。所以关于排序算法，我也更多的是先从举一反三的思考问题的角度去复习。

排序算法大全

排序算法.PNG

排序算法的评估要素

1.稳定性：稳定性与实现方式有很强的相关性，但是如果是按相对最优（教科书）的算法步骤实现，每种算法的稳定性是固定的。
2.时间复杂度：与算法的数学思想强相关。例如二分的思想，递归的思想，遍历的思想
3.空间复杂度：内存与资源的开销，可以针对不同场景提供不同的算法

插入类

直接插入排序

算法思想

每一次遍历，将一个待排序关键字（只要是没有被处理的关键字即可）按照其值的大小插入到已经排好的部分有序序列中，插入方式取决于排序方式（从小到大，则按照从小到大方式插入到有序序列中），直到所有关键字都被插入到有序序列为。
该算法的核心思想：“大事化小，以0为起始”。
该算法比较简单，就不提供图示样例了，脑补一下。

时间复杂度

该算法存在两个步骤：
1--遍历全部关键字，这个是必不可少的
2--插入操作，所以需要对已排序序列做移动，移动次数与原序列的“有序度（原序列与目标序列的初始匹配度）”有关
所以算法复杂度，平均是n（step1）*n（step2），即O(n2)；最坏的情况下，step2每次要移动全部已排序序列，所以会导致最坏复杂度为也是O(n2)；最好的情况下，step2不需要做任何操作，新的关键字插入有序序列的时候，不需要对原有序序列做操作，即最好情况为O(n)。

空间复杂度

插入动作过程中我们需要一个temp用来存储关键字，所以通常空间复杂度为O(1)。如果岗警说，我搞个temp[n]，然后拷贝有序序列。。那我想说，也可以，但是不标准。

稳定性

思考一下，排序前后的序列，对重复的关键字是否会有变化呢？一般可以以举反例的方式来推理。比如有一个序列 3 1 1 5 2 2 9，按照从小到大排序。第二个1在插入的时候，如果插入在第一个1之前，那么这个实现就不稳定排序，但是如果插入在第二个（即最后一个重复关键字）之后就算是稳定的。然而，上述反例是伪证。因为我们不可能知道最后一个重复关键字在哪，如果要遍历，那就不是O(n2)的复杂度了。所以通常的合理实现，应当是选择插入在第一个1前面，所以我认为直接插入排序的实现一定是不稳定，尽管理论上具备稳定的可能性。

折半插入排序

算法思想

这个算法就是对插入排序的一个改良。插入排序在寻找插入位置的时候，往往是从头到尾顺序遍历，这对一个已经有序的序列并不是最优的遍历方案，所以将遍历方案优化为二分法遍历。即所谓折半插入。

算法复杂度

折半插入排序减少了比较元素的次数，约为O(nlogn)，比较的次数取决于表的元素个数n。因此，折半插入排序的时间复杂度仍然为O(n²)，所以当数据量有一定规模的情况下，该算法会表现出远优于直接插入的性能。

希尔排序

算法思想

希尔排序又叫做缩小量排序，其本质还是插入排序，特别之处在于将待排序序列按某种规则分成几个子序列，分别对几个子序列进行直接插入排序。规则的关键在于增量的选择，如果增量为1，就是直接插入排序。说了这么多，来看个实例吧

希尔排序.PNG

时间复杂度

按照希尔的方案选取增量，那么对于n序列长度的排序，最坏情况下为O(n的平方)，当n在某个特定范围时，约为O(n的1.3次方)
关于希尔排序算法复杂度的证明过程比较复杂，待后续有时间再详解。

空间复杂度

与插入排序的逻辑一致，为O(1)

稳定性

由于插入关键字的缘故，希尔排序也是非稳定排序。

交换类

冒泡排序

算法思想

此处略去100字。

时间复杂度

因为要做两个循环才能完成全部冒泡，所以时间复杂度O(n的平方)

空间复杂度

只需要一个temp即可，O(1)；

稳定性

冒泡在交换过程中，如果比较大小相等并不会执行交换（性能考虑），所以冒泡是稳定的。

快速排序

算法思想

快速排序也是交换类排序，他通过“多次划分”实现排序操作。已升序为例，执行流程如下
1）选择1个当前子序列的关键字作为轴，通常从第一个关键字开始
2）将大于关键字的放在右边，小于关键字的放在左边，经过一轮循环后，中轴关键字的左边为一个序列，右边为一个序列
3）当遍历完一轮全部数据后，全部数据将会被分为两组，然后本轮循环结束。假如你没看过教科书的灌输思维，这里应该如何去判定“全部数据完成一次遍历”这个操作呢？
4）分别对左边序列和右边序列执行1、2、3操作，直到子序列为1个元素为止。

快排.PNG

时间复杂度

交换过程采取了二分法，所以遍历次数为log2n，由于始终需要对n个元素进行比较，所以平均复杂度为O(nlog2n)，最坏的情况下，二分子序列的情况需要执行n次（例如一个完全逆序的数组进行排序），则最坏复杂度为O(n的平方)

空间复杂度

直观来看，快排只用了一个temp，所以空间复杂度应该是O(1)，然后快排的实现是递归，递归是需要栈空间开销的，空间复杂度等于递归次数*O(1)，即O(nlog2n)。

稳定性

快排的本质是交换类排序，交换类排序在等于的情况下是不发生交换，所以快排也是稳定排序。

选择类

简单选择排序

算法思想

我认为这是世界上最直观最简单的算法，连小朋友打扑克都会的算法。
找出最小的放在第一位，次小放在第二位，再次放在第三位，依次排序。。还有啥比这更简单的吗

时间复杂度

直接插入排序就两步 1）找到最小，需要轮询 2）放到对应的位置，需要将已有序列统一向后挪动，等于插队，其他人往后站，依然需要轮询已有序列，两遍轮询，时间复杂度O(n的平方)；，，
这里要注意，直接插入排序和直接选择排序的区别，虽然都有插入这个动作，但是前者是移动有序序列，后者是挪动无序序列让出空间。这两者有直接区别，所以阅读代码的时候，不要看到insert就想到一定是插入排序了。

空间复杂度

挪动过程，并不需要新建数组，所以空间复杂度O(1);

稳定性

序列在发生交换的时候，会改变原有相同关键字的顺序，所以选择排序是不稳定的。
例如7，8，7，3，9，7和3交换以后，两个7的相对位置已经发生了变化。

堆排序

（在这个阶段提堆排序会感觉有点跳跃性，直接从一个超级简单的算法到了一个较为复杂的算法，但是没办法。。选择排序只有这两种）

背景知识补齐

因为我在算法这部分并没有考虑再去讨论数据结构了，但是这里这个算法用到了堆，所以再把堆相关的知识拿出来复习一下。
堆是一种基本数据结构，可以将其理解为一个完全二叉树，而这颗二叉树满足：任何一个非叶节点值都不大于(或不小于)其左右孩子节点的值。若父亲大孩子小，称为大顶堆；父亲小孩子大称为小顶堆。由此可见，如果以大顶堆为例，根节点就是该序列最大值。

算法思想

利用堆的特征，将待排序序列构成一个大顶堆，然后移除根节点，将剩余节点再转化成一个大顶堆，一次完成排序操作。
问题1：如何将无序序列转化为大顶堆
问题2：将堆顶元素挪走以后，如何将剩余元素继续做成大顶堆。是重复问题1的解法去递归，还是另有方法。
如果很想深究上述两个问题的答案，建议充分复习一下二叉树和完全二叉树的数据结构。我这里给出上述两个问题的解法。
排序步骤如下：
1）将无序序列转化成一个完全二叉树，如图

堆.PNG

2）对该完全二叉树从第一个非叶节点开始从右至左从下往上堆每个节点进行调整
调整方法：将该节点的值域其孩子节点比较，如果有大于该节点的孩子节点，则从中选出最大的一个与该节点进行交换。该节点如果存在多层的孩子，则需要层层往下执行上述步骤，至到该节点的所有孩子均小于该节点。
3）完成2以后，得到一个大顶堆。将根节点与最小的叶子节点交换（这么做也是为了最小化内存空间占用，和前面的排序思想一样。做算法设计，必须精益求精，做到极致，算法是小杠杆，一点点开销堆整个产业带来的可能就是巨大的成本浪费），这样将整棵树分为有序和无序两部分。对于无序部分，再次执行上述2)步骤。直到无序队列只剩最后一个元素。还是用图来说明这个过程。

1.PNG

2.PNG

时间复杂度

算法复杂度为O(nlog2n)，至于怎么来的，我会在算法基础2.2中实现堆排序的代码，届时用代码来解释上述图中复杂的节点迁移变化的时间开销。
这里有一点需要明确，堆排序如此复杂，为什么还要用它。。可能大家已经意识到，堆排序是一个二叉树遍历问题，二叉树的遍历，最好最坏时间复杂度都是O(nlog2n)，而快排的最坏复杂度是O(n的平方)。所以，当数据量很大但是却只需要找出排名前几的关键字时，堆排序有较为明显的优势。
比如考试成绩排名，需要在20W考生里面找到广东省排名前100的，快排就会比较耗时，堆排序优势明显。

空间复杂度

空间并不随数据量大小的变化而变化，所以空间复杂度为O(1)。

稳定性

在举个例子说明：8 17(a) 26 17(b)，
如果堆顶8先输出，17(b)跑到堆顶，然后堆稳定，继续输出堆顶，即17(b)，于是17(b)出现在了17(a)前面，不稳定。
理论过程描述：
堆的特征是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点。于是，对于一个n 序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆），这3个元素之间的选择不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

归并类

归并排序

算法思想

归并排序是一个分治的过程：先将整个序列分为两半，堆每一办进行归并排序，将得到两个有序序列，然后将两个有序序列合并为一个即可。其实，归并算法的关键点分裂和合并。
来看个图

分裂.PNG

合并.PNG

时间复杂度

归并排序的时间复杂度，用数学归纳来推导一下。
第一趟归并需要执行2(n/2)=n次基本操作（其中2为子序列关键字的个数之和，n/2为要归并的子序列堆的个数，每个子序列对执行一次merge操作，也就是两次(比较+交换)基本操作）
第二趟归并需要执行4(n/4)=n
第三趟归并需要执行8(n/8)=n
第k趟归并需要执行2的k次方(n/2的k次方)=n
……………………
当n/2的k次方 = 1时，即需要归并的两个子序列长度均为原序列的一半时，归并排序结束，此时k=log2n，即总共需要log2n趟排序，时间复杂度为O(nlog2n)

空间复杂度

归并过程中，我们需要转储整个序列，所以空间复杂度为O(n)

稳定性

可以想象，两个项目的元素，在分裂和合并过程中，并不会发生相对位置的变化。所以归并排序是稳定的。

线性时间比较类

怎么突然冒出一个线性时间呢？其实前面的所有排序都是非线性时间比较类排序。
非线性时间比较排序--基于比较的排序，其算法时间复杂度不能突破O（nlogn）。
线性时间比较排序--不基于比较的排序，其算法时间复杂度可以突破O（nlogn）。
至于为什么说线性、非线性，暂时我没有深入去研究了。

基数排序

算法思想

基数排序的核心思想是多关键字排序。
通常有两种实现，一叫做最高位优先，即先按最高位排成若干子序列，再对每个子序列按次高位排序。以扑克牌为例，现按花色排序，再按同一花色的13张排序，改变排序的关键字要素，不停变化，最终使得整个序列有序。另一种交最低位优先，这种方式不必划分子序列，每次排序全体关键字都参加，最低位通过“分配”、“收集”方式，而不是通过比较。比如扑克牌先按数字分配到13个桶里面，然后从第一个桶开始依次收集，再将收集好的牌按花色分配到4个桶中，然后还是从第一个桶开始依次收集。经过量词“分配”、“收集”操作，最终使得序列有序。

基数排序第一轮.PNG

基数排序第二轮.PNG

最后一轮排序我就不画图了，继续递推下去，可以看到整组序列就有序了。整个过程未做比较操作，只是做了分类操作。所以排序不一定只是比较，思维上的突破往往是最难的。

时间复杂度

基排序的复杂度为O(d(n+Rd))， 其中n为序列中的关键字个数，d为关键字的子位数，例如数字125，d就是3，Rd为关键字基（构成关键字的符号，例如关键字为数值时，构成关键字的符号可以选择0-9，即Rd=10）的个数。这个推理过程比较难以记录，我在一本书上找到了一个更加直观的理解记忆方法，如下：
基数排序每一趟都要进行“分配”、“收集”操作，分配需要一次对序列中的每个关键字进行，即需要扫描整个序列，所以有n这一项；“收集”需要一次对每个桶进行，二桶的数量取决于关键字的取值范围，如果放数字的桶有10个，放花色的桶有4个，所以就存在Rd这一项，因此，一趟“分配”、“收集”需要的时间n+Rd。那整个排序需要多少趟呢？有多少个关键字，就有多少趟，即需要d趟。

空间复杂度

每个桶实际上就是一个队列，需要头尾指针，共Rd个桶，所以需要2Rd个指针，即空间复杂度O（Rd）。

适用场景

基数排序适合序列中的关键字比较多，但是组成关键字的取值范围较小，即桶的数量较少的情况下。

桶排序

算法思想

将数组分到有限数量的桶子里，每个桶子再分别排序（有可能再使用别的[排序算法]或是以递归方式继续使用桶排序进行排序）。
桶排序的思路很简单，但是在实际使用中通常需要考虑以下因素：
1）元素到桶的映射规则，需要合理的将n和元素分都m个桶，合理性与业务逻辑强相关。
2）桶内数据排序算法的选择，可以根据相关数据集合的特征，选择排序算法，也可以继续采用桶排序递归。
这个具体的设计过程与原始数据有很强的相关性，而这部分设计正是“你也懂算法，我也懂算法，但是我做的东西就是比你好的原因”。对于原始数据的研究和理解，以及先有计算能力的评估和衡量，是利用好一个算法的关键。

总结

排序算法总结.PNG

下一章将讨论外部排序内容，外部排序又是另外一种风景。