• 数据结构篇为本人考研时所写笔记，包括知识点和编程思想两大板块，笔记内容依据王道数据结构考研书所写，但比书本上知识更加生动形象，愿本篇章能对您有所帮助

8、内部排序

（一）排序基本概念

1. 考试常考：看到某特定序列选择最优算法（通常用排除法写，且通常进行极端状况的对比，只要优于就选）算法

4. 堆排序题目问数组状态时答是画图编程

5. 名词概念：数组

①　文件：由一组记录组成，记录有若干数据项组成数据结构

②　关键字：惟一标识记录的数据项工具

5. 稳定性：

①　通过排序后，能使关键字形态的元素保持原顺序中的相对位置不变性能

②　不稳定性：反之指针

③　注意：算法是否具备稳定性并不能衡量一个算法的优劣，它主要是对算法的性质描述code

④　答题时说明不稳定性只需举出一组关键字序列便可blog

⑤　两个稳定的算法一块儿用程序仍是稳定的排序

6. 排序分类：

①　内部排序：数据元素是否彻底在内存中（通常要算法执行过程当中都进行比较和移动操做，但好比基数排序就不基于比较）

②　外部排序：反之

7. 内部排序算法性能取绝与算法的时间复杂度（时间性能，时间效率）和空间复杂度（空间性能，空间效率）

8. 对同一线性表使用不一样的排序算法排序，获得的排序结果可能不一样

9. 对任意n个关键字排序的次数至少为向上取整（log_2(n!)）

10. 进行基数排序时记得从个位数开始比，不要习惯性的比较数字的第一个数字

11. 筛选法建堆，它能够在线性时间复杂度下完成建堆。以最大堆为例介绍具体操做过程：

①　首先将N个数据元素存入一个一维数组，并把这个数组视做一棵彻底二叉树。

②　从二叉树的最后一个非叶结点（数组n/2开始）开始用从上向下过滤的方法调整以该非叶结点为根节点的二叉树为最大堆。

③　对前面的结点依次执行2）的操做直到根结点执行完成为止。此时这棵二叉树就调整为了一个最大堆

④　构建堆是边插边排

⑤　建堆时比较次数不超过4n次

12. 从小根堆调整到大根堆是从最下面最右边的一棵子树开始调整，反之亦然

（二）各排序算法的比较

1. 通常基于三个因素进行比较：

①　时空复杂度

②　算法稳定性

③　算法的过程特征（算法的复杂程度）

1）效率比较

1. 归并排序可视为本章算法中占用辅助空间最多的排序算法

2）应用比较

1. 选取排序方法须要考虑的因素：

①　待排序的元素数目n

②　元素自己信息量的大小

③　关键字的结构及其分布状况

④　稳定性的要求

⑤　语言工具的条件

⑥　存储结构

⑦　辅助空间的大小

2. 应用比较：

①　若n较小(<1000)，可采用直接插入排序或简单选择排序或冒泡。因为直接插入排序所需的记录移动次数较简单选择排序的多，于是当记录自己信息量较大时，用简单选择排序较好

（1) 一般状况下，直接插入排序每趟插入都须要依次向后挪位，而简单选择排序只需与找到的最小位置交换位置，后者移动次数少不少

②　若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜

③　若n中等大小（<=1000）,希尔排序是很好的选择

④　若n较大（>1000）,则应采用时间复杂度为O(nlog_2(n))的排序方法:快速排序、堆排序，归并排序

（1) 若要求排序稳定且时间复杂度为O(nlog_2(n))，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，一般能够将它和直接插入排序结合在一块儿使用。先利用直接插入排序求得较长的有序子文件，而后两两归并

（2) 若n很大，记录的关键字位数较少且能够分解时，采用基数排序较好（只适用于有明显结构特征的关键字，且基数排序不能对float等类型实数进行排序，故若题目要求关键字为实数则不能选择基数排序）

⑤　在基于比较的排序方法中,每次比较两个关键字的大小以后，仅出现两种可能的转移所以能够用一棵二叉树来描述比较断定过程，由此能够证实:当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少须要O(nlogn)的时间

⑥　当记录自己信息量较大时，为避免耗费大量时间移动记录，可用链表做为存储结构，如插入、归并、基数排序，但快排和堆排序在链表上难实现，可提取关键字创建索引表后对索引表排序

⑦　有的语言没有提供指针及递归，这时归并、快速、基数排序算法复杂

⑧　只需获得前k小元素的顺序排列可采用的排序算法有冒泡排序，堆排序和简单选择排序

3. 混合使用不一样排序算法是一种广泛的算法改进方法