一个排序的算法应该从这些方面去理解、复习、巩固：

时间、空间复杂度（最好情况和最坏情况分别是什么、排序趟数受什么影响

算法运行思想（模拟过程、模拟算法运行、阐述其思路和思想、算法运行特点

稳定性、比较/移动/交换次数与初始序列的相关性、属于什么类型排序

一趟排序能不能必然定下一个最终元素

适用性（适用于什么数据结构、适用的原因）、适用应用场景（什么情况适合用）

最后也是要求最高的一点：能够按照其思想不靠默写能写出代码

这一块的整理因为篇幅较大放在整理文档内部，后续若要补充可以去文档内进行补充

直接插入排序、折半插入排序、希尔排序：

习题分析整理：

6：考虑从性质出发而不是直接模拟运行，最贴近有序的情况下比较/插入/移动次最少

7：插入排序都不能保证排序能够定下某个元素的最终位置

9、11：关于希尔的增量，这个增量的定义可能会遗忘，就是I+D（序号加一个增量）

12：基本还是要考虑模拟的，因为每个子序列内部采用的是直接插入（折半实现较复杂

14：一个比较容易混淆的误区点

直接插入查找本身就是ON^2，移动又是ON^2，总体是ON^2

折半插入查找本身优化到ONlogN，但移动依旧是ON^2，总体依旧是ON^2，容易混淆

18：插入排序的趟数均是确定的，不论直接插入、折半插入、希尔排序都是确定趟数的

折半插入、直接插入的比较次数虽然不是固定相同的，但移动次数必然是相同的

19：掉坑里了，和上面9、11的增量叙述一样，个人因为比较喜欢用数增量方式做题

导致就是数出来的是1、2、3、4，然后不假思索直接写了个增量为4上去

实际上增量是4-1=3…好好好，天坑了属于是一个，这个以后一定要去注意的

21：那这道题我怎么又清醒过来了？

冒泡排序、快速排序：

习题分析整理：

3：快排的最基本特征就是每次能够至少定下来一个最终元素位置

并且这个元素把左右划分为大于该元素、小于该元素的两个子区间，特征较为明显

4：算法模拟，一般只会模拟一趟或者两趟然后考察比较、移动次数这类

这种就老实点一步步推理下去就可以了，本身的模拟过程并不难，多练就能熟悉

8：冒泡的一个比较有用的结论：

当只有离群散点，而整体基本有序的情况下，可以考虑用冒泡或者插入排序

每一个离群散点放到有序序列需要的趟数就至少是一趟（除非隔得比较近一趟定两个

这样的话这道题就能秒解，有五个散点，并且没有可能导致一次定两个那么就是五趟了

9：冒泡排序的结尾条件就是某趟排序后没有产生交换（有交换的趟无法确定有序否

也就是即使某趟排序完成后已经有序，也需要多增加一趟才能确定序列已经有序

这个就是这道题设置的坑和陷阱，个人是已经往里面跳进去了，确实是没注意的点

10：性质题，从性质入手，结合模拟解题

最佳的情况就是每次划分均得到一个基本均匀的区间，模拟是肯定需要模拟的

但模拟的话就没有必要一个个元素写出来，只需要清楚下一趟、后面几趟第一个是谁

因为是很容易看出来一个元素能不能均匀划分整个区间的，都能均分即为最快情况

而全部有序或者逆序的情况则是最差的，D选项就是这个情况

11：只需要一次模拟即可，并且这个模拟只需要考虑指针的运行状态不考虑交换情况

因为只计算交换次数和比较次数而已，自然是不需要考虑交换成什么样的

14：补充一些理解上的误差，其实快速排序每趟的比较次数差别不大（每层的比较次数

快排的优越性在于总体比较的层数在大多数情况下能够压缩到logn层

每次选择一个基准对其进行一次位序的确认，不管到底交换几次都需要比较N-1次

最好情况下分为两个子序列，对子序列进行基准位置确认，第二层总体就比较N-3次

第三层就比较N-7次，很容易就能看出规律，计算出总体的比较次数，而这是我忽略的

即：快排也可能会去考察比较次数，因为这个是确实在考纲范围内的内容

其实本质就是对书上递归树的理解不够深刻，如果清楚了递归的执行，自然可算次数

最佳情况、最差情况的次数都应该要能够有手算的能力，这是本道题给出的思路

15：重点在于每一次能够分为几个子序列，而不在于先处理长还是短，考察递归本质

关键在于每层能够减少多少个需要比较的元素，能够减少的越多，比较的次数就越能少

每一次到底先处理长的还是短的并不重要，划分分区到一个尽可能平衡的区间才重要

PS：如果划分尽可能平衡，那么递归过程就顺便构造出了一棵平衡二叉树

不过从形状来说其实应该更贴近“折半查找树”

17、18：统考命题的角度其实更加深一点，但本质也是在考察上述的递归执行过程

不过在快速排序里面，一趟实际上是被称为是递归树的一层，更多还是定义不够明朗吧

不过统考既然已经明确了这样一个定义，后面就按照他的思路走即可

统考的命题定义基于：对尚未确定最终位置的所有元素进行一遍处理称为“一趟”

在快速排序里面，递归树的每一层被视作是快速排序的“一趟”

虽然实际执行过程应该是类似先序遍历，但这是统考命题角度，需要按出题人思路走

那么某一趟能够确定的关键词位数就是2^(X-1)个（X为层数）

到第X趟为止最少确定X个，最多就能确定2^X-1个

某趟比较次数最少N-2^X-1次，最多比较次数为N-X次，这一些算是拓展，不难推导

简单选择排序、堆排序：

习题分析整理：

1：描述上面就是选择排序，那么从堆排序和简单选择里面选，堆排序虽然是选择排序

但和描述上面比较其既可以是大根堆也可以是小根堆，所以最佳还是简单选择

统考这类题是比较多的，二者不定选其一的情况往往是看谁更不靠谱，谁更不太贴近

3：其实这类问题可以用于处理的算法还有很多，只需要保证能得到前面几个最终位置

冒泡排序、简单选择排序、堆排序都是可以在每趟确定前面几个元素位置的

但相对而言堆排序的常量更小，具体的解释可以见后面的综合题，一般了解即可

4：堆是一棵完全二叉树，要和二叉排序树、平衡二叉树、红黑树、哈夫曼树等区分开

此外补充：能够得到最终位置但只能得到一些不按顺序来的排序算法：

快速排序、归并排序

能够得到最终位置且是有序的排序算法：

简单选择排序、冒泡排序、堆排序

9：二叉排序树并不一定是一棵满二叉树，而堆一定是一棵满二叉树

层序遍历只要写一个出来就能判断出不能保证有序，不要“应该”，要举例来证明

11：题目也没有说清楚到底需要不需要调整，看来默认是需要调整的吧

12：先前建立的思考认为是不需要交换的，实际上即使向下调整没有采用交换方式

下面的堆根向上移动的过程本身也可以视作是一次交换，不一定是这个结点交换

14：举例即可，理解不够举例来凑

16、17：关于比较上面，需要具体阐述下问题，代码阅读不够细

代码内的执行过程明显能看出是先比较子，然后再和父比较，这个运行条件很可能考

而不是个人所理解的先和左子比，再和右子比（不过似乎也是可以的）

补充四个比较重要的须知点：

1.调整堆算法的执行流程

2.初始建堆的算法执行流程

3.堆排序的算法执行流程

4.插入、删除元素的运行流程模拟

归并排序、基数排序、计数排序：

习题分析整理：

1：归并排序、基数排序在最终一趟之前都不能确定某个元素的最终位置，一个都不行

3：对基数排序的理解不够深刻、或者不够熟悉

基数排序的时间复杂度是O（d(n+r))，应该要能够理解各个变量的含义

空间复杂度为OR，R为所有位里面数种类数最多的个数（1-3含4个，0-9含10个）

d是数据的最多位数（十位数就是10，需要排序十趟）

n就是需要排序的元素个数，对整个基数排序需要能够模拟运行

4：这里说的是“比较的数量级”，最好、最坏情况仅在于合并的情况上

最坏的合并是N1+N2-1每次，最好的合并是N1每次，而趟数不变为logN次，数量级一样

5：这里也是说了归并的数量级，其实直接说次数也没关系，取整即可

7：典型的举例题，也间接考察了算法思想，两个有序序列的合并，最坏/最好情况

8：算法细节题，需要清楚总体比较的次数是怎么比的，这道题是很不错的题

11：和16的理解问题几乎如出一辙，不论先前排序了几趟排序到底是怎么样的情况

即使本次排序是稳定的（不稳定就更不用说了），也只能保证按这个关键词排序的位

是整体有序的，这一个是思维问题，先前的排序只能保证本次局部按先前规律有序

排序了K1，本次整体是K1有序，排序了K2，本次整体是K2有序

即使第一次排序K1，第二次是稳定排序，排序了K2，整体必然按K2有序，局部按K1有序

13：基数排序的各参数不熟悉，更多是因为没有细看书导致的

15：主要是没有考虑到头插法的方式把升序合并为降序，现在也自然能够有所知晓

把升序合并为降序只需要用头插法即可，把降序合并为升序也可以用头插法实现

把升序/降序合并为升序/降序直接采用尾插法

16：理解问题，基数排序有一个特点就是其一趟结果只是某一位是整体有序的

不论先前到底排序了几趟，在非最终趟的情况下，其只能保证这次排序的这位整体有序

其他先前排序过的位只能保证局部有序，也是个人的理解误差点

内部排序算法的比较：

习题分析总结：

1：需要注意“实数”并不是整数，基数排序只对实数进行排序（基数可以对小数排序

只需要对所有小数都乘上一个幂即可变为整数，这里的实数主要是在声明无理数的情况

3：冒泡、插入最喜欢已经有序的情况，快速最不喜欢已经有序或者逆序的情况

归并排序、基数排序、堆排序基本波澜不惊，简单选择内心也毫无波动

9：首先明确一件事：平衡二叉树、二叉排序树、红黑树、B树、B+树均是为查找服务的

本章里面的堆查找效率极低，因为本质就是一棵排序树根本不是为查找服务的

11：容易错在基数排序的判定上面：基数排序不基于比较/交换，所以绝对不能去选

12：这里说的堆排序可以并行更多含义是“建堆”过程确实是可以并行的

但其父结点到底还是依赖于其两个孩子的并行，所以多少也只能算是“半吊子”并行吧

真正能够并行的应该可以把归并排序、快速排序给算上去，计数排序也是可以的

基数排序也同样可以实现并行化，不过其思想略微复杂一些，需要添加辅助量来操作

13：如果是归并排序两趟，我至少能够看到两个有序的子序列，这是归并排序特点

15：这里再度出现了对“趟”的定义，就是对所有没有确定最终位置的元素进行一趟

所以在这个细节上面，快排、归并排序就尤其需要注意，是全部元素都排才算是一趟的

17：具体有过阐述，这里给出简洁的描述

折半插入如果采用链表，左右确定元素位置去查找后链表均需要遍历确定，数组O1

快速排序其实在每一个定下一个位置的情况下是可以用指针实现的，但需要双向链表

同时因为总体是递归算法，所以总体就会产生大量的指针（尤其并行情况下

堆排序需要访问父子结点，在顺序表中可以O1直接计算，链表里要么用三元表存储

如果用链表，那么整个就变成了一棵链表树，建堆都需要不断遍历到每个非叶

希尔排序每个增量序列只能从头向后遍历，放在链表里面就是一个序列遍历一遍链表

19：简单选择的比较次数必然是N（N-1）/2次，直接插入的比较次数越有序就越少

直接插入的移动次数远没有简单选择少，简单选择基于交换而不基于比较，明显少多了

本书还有最后几个任务：基于理解性的代码书写（可以考虑上机，一般也就一个上午

对书上内容再进行进一步细致性的啃、查漏补缺、把本书内容里面需要重新做的题划出

基于思想的算法改善和拓展（写代码基本是一定要上机自己写一遍才能真正理解

外部排序、计数排序：