这一章讲一下排序的内容，还是先看一下分类。
文章目录
一、排序的基本概念二、插入排序1. 直接插入排序（1）算法思想：（2）算法性能分析：
2. 折半插入排序（1）算法思想：（2）性能分析：
3. 希尔排序（1）算法思想：（2）性能分析：
三、交换排序1. 冒泡排序（1）算法思想：（2）性能分析：
2. 快速排序（1）算法思想：（2）性能分析：
四、选择排序1. 简单选择排序（1）算法思想：（2）性能分析：
2. 堆排序（1）堆的概念：（2）算法思想：（3）性能分析：
五、归并排序和基数排序1. 归并排序（1）算法思想：（2）性能分析：
2. 基数排序（1）算法思想：（2）性能分析：
六、各种内部排序算法的比较及应用1. 内部排序算法的比较2. 内部排序算法的应用（1）选取排序方法需要考虑的因素（2）小结
七、外部排序1. 外部排序的基本概念2. 外部排序的方法3. 多路平衡归并与败者树4. 置换-选择排序5. 最佳归并树
基本概念
-----|- 稳定性
|- 衡量标准：时间、空间复杂度
|- 直接插入排序
|- 插入排序
------|- 折半插入排序
| |- 希尔排序
|
|- 交换排序
------|- 冒泡排序
内部排序
----| |- 快速排序
|
|- 选择排序
------|- 简单选择排序
| |- 堆排序
|- 归并排序
|- 基数排序
外部排序
-----|- 多路归并排序
一、排序的基本概念
在排序的过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：内部排序和外部排序。一般情况下，内部排序在算法执行过程中都要进行两种操作：比较和移动。（并不是所有排序算法都是基于比较的，基数排序就不是基于比较的。）内部排序算法的性能取决于时间复杂度和空间复杂度，时间复杂度一般是由比较和移动次数来决定的。
二、插入排序
1. 直接插入排序
（1）算法思想：
为了实现对 L[1…n] 的排序，可以将 L(2)…L(n) 依次插入到前面已经排好序的子序列中。初始假定 L[1] 是一个已排好序的子序列， ① 查找出 L(i) 在 L[1…i-1] 中插入的位置 k ； ② 将 L[k…i-1] 中所有元素全部后移一个位置； ③ 将 L(i) 复制到 L(k)； 上述操作执行 n-1 次就能得到一个有序的表。
void InSertSort(ElemType A
[], int n
){
}
（2）算法性能分析：
空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：稳定；适用性：适用于顺序存储和链式存储的线性表；
2. 折半插入排序
（1）算法思想：
直接插入算法是边比较边移动元素；折半插入是将比较和移动分离出来，即先折半查找出元素待插入的位置，然后再统一的移动待插入位置之后的所有元素。
void InSertSort(ElemType A
[], int n
){
}
（2）性能分析：
空间复杂度：O(1)；时间复杂度：O(n^2)；虽然和直接插入相同，但对于数据量较小的排序表，性能较好；稳定性：稳定；适用性：适用有序的表；
3. 希尔排序
又称：缩小增量排序。
（1）算法思想：
先将待排序表分成若干个子表 L[i, i+d, i+2d,…,i+kd] ，分别进行直接插入排序，当整个表中元素已基本有序时，再对全体记录进行一次插入排序。
void ShellSort(ElemType A
[], int n
){
}
（2）性能分析：
空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：不稳定；适用性：适用于线性表为顺序存储；
三、交换排序
1. 冒泡排序
（1）算法思想：
假设待排序表长为 n ，从前往后两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。我们称之为一趟冒泡，结果将最小的元素交换到序列的第一个位置。 下一趟冒泡时，最小元素不再参与，待排序元素减少一个。 每趟冒泡的的结果把序列中最小元素放到了序列的最终位置。
void BubbleSort(ElemType A
[], int n
){
}
（2）性能分析：
空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：稳定；
2. 快速排序
（1）算法思想：
是对冒泡排序算法的一种改进，基本思想是基于分治的。在表中选取一个基准元素pivot，通过一趟排序将待排序表划分为独立的两部分 L[1…k-1] 和 L[k+1…n]，使得 L[1…k-1] 中所有元素小于pivot，L[k+1…n] 中所有元素大于或等于pivot，pivot放在最终位置 k 上。快速排序的关键在于划分操作，算法性能也主要取决于划分操作的好坏。目前常用的方法是：将当前表中的第一个元素作为枢纽值对表进行划分，比枢纽值大的元素向右移动，比枢纽值小的元素向左移动，使得一趟Partition() 操作之后，表中元素被枢纽值一分为二。
void QuickSort(ElemType A
[], int low
, int high
){
}
int Partition(ElemType A
[], int low
, int high
){
}
（2）性能分析：
空间复杂度：O(log2 n)；时间复杂度：O(nlog2 n)；稳定性：不稳定；
四、选择排序
选择排序基本思想：每一趟在后面 n-i+1 个待排序元素中取关键字最小的元素，直到第 n-1 趟做完，待排序元素只剩下一个，就不用了再选了。
1. 简单选择排序
（1）算法思想：
第 i 趟排序即从 L[1…n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 n-1 趟排序就可以使得整个表有序。
void SelectSort(ElemType A
[], int n
){
}
（2）性能分析：
空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：不稳定；
2. 堆排序
（1）堆的概念：
堆排序是一种树形选择排序方法，特点是：在排序过程中，将 L[1…n] 看成是一棵完全二叉树的顺序存储结构。堆的定义：
小顶堆：L(i) <= L(2i) 且 L(i) <= L(2i+1)；大顶堆：L(i) >= L(2i) 且 L(i) >= L(2i+1)； 堆的应用：堆经常被用来实现优先级队列，优先级队列在操作系统的作业调度和其他领域有着广泛的应用。
（2）算法思想：
堆排序的关键是构造初始堆，对初始序列建堆，就是一个反复筛选的过程。
void BuildMaxHeap(ElemType A
[], int len
){
}
void AdjustDown(ElemType A
[], int len
){
}
向下调整的时间与树高度有关，为O(h)。其时间复杂度为O(n)。首先将存放在 L[1…n] 中的 n 个元素建成初始堆。输出堆顶元素后，通常将堆底元素送入堆顶，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩下一个元素为止。
void HeapSort(ElemType A
[], int len
){
}
堆也支持插入和删除操作。 （1）删除：删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需要对此时的根节点进行向下调整操作。 （2）插入：先将新结点放在放在堆的末端，再对新结点执行向上调整操作。
void AdjustUp(ElemType A
[], int k
){
}
（3）性能分析：
空间复杂度：O(1)；时间复杂度：O(nlog2 n)；稳定性：不稳定；
五、归并排序和基数排序
1. 归并排序
（1）算法思想：
假定待排序表中含有 n 个记录，则可以看成是 n 个有序的子表，每个子表长度为1，然后两两归并，如此重复，直到合并成一个表为止。这种排序算法称为 2-路归并排序。
void Merge(ElemType A
[], int low
, int high
, int mid
){
}
递归形式的 2-路归并排序算法是基于分治的，其过程如下： （1）分解：将含有 n 个元素的待排序表分成含 n/2 个元素的子表，采用 2-路归并排序对两个子表递归的进行排序。 （2）合并：合并两个已排序的子表得到排序结果。
void MergeSort(ElemType A
[], int low
, int high
){
}
（2）性能分析：
空间复杂度：O(n)；时间复杂度：O(nlog2 n)；（ 每一趟归并的时间复杂度为O(n) ）稳定性：稳定；
2. 基数排序
（1）算法思想：
基数排序不是基于比较进行的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序的），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先（MSD）和最低位优先（LSD）排序。
（2）性能分析：
空间复杂度：O®；一趟排序需要借助的辅助存储空间为 r （r个队列）。时间复杂度：O(d(n+r))；一趟分配需要O(n)，一趟收集需要O(r )。稳定性：稳定；
六、各种内部排序算法的比较及应用
1. 内部排序算法的比较
对于任意一种基于比较的排序，最少比较次数为（n 为关键字个数）：
算法算法种类时间（最好）时间（平均）时间（最坏）空间复杂度稳定性备注
插入直接插入排序O(n)O(n^2)O(n^2)O(1)稳定最少比较(n-1)次；最多比较n(n-1)/2次；交换冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择简单选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定比较次数O(n^2)；移动次数O(n)；比较次数与序列初始状态无关插入希尔排序O(1)不稳定交换快速排序O(nlog2 n)O(nlog2 n)O(n^2)O(log2 n)不稳定最大递归深度为n，最小递归深度(log2 n)；最坏空间复杂度O(n)选择堆排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)不稳定构建堆时间复杂度O(n)；堆排序时间复杂度最坏O(nlog2 n)；插入删除时间复杂度O(log2 n)；查找效率较低归并2-路归并排序O(nlog2 n)O(nlog2 n)O(nlog2 n)O(n)稳定比较次数与序列初始状态无关，归并趟数O(log2 n)基数基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(r )稳定元素移动次数与序列初始状态无关
在每趟排序过程中，都会有一个元素被放到最终位置上，这样的排序方式有：堆排序、冒泡排序、快速排序。直接插入排序、希尔排序，在最后一趟排序之前，所有元素都可能不在最终位置上。
2. 内部排序算法的应用
（1）选取排序方法需要考虑的因素
① 待排序的元素数目 n ； ② 元素本身信息量大小； ③ 关键字的结构及其分布情况； ④ 稳定性的要求； ⑤ 语言工具条件，存储结构及辅助空间大小。
（2）小结
① 若 n 较小，则可以采用直接插入排序或简单选择排序； ② 若文件初始状态关键字基本有序，则用直接插入或冒泡； ③ 若 n 较大，则应采用快速排序、堆排序、归并排序； ④ 当记录本身信息量较大时，为了避免耗费大量的时间移动记录，可用链表作为存储结构。
七、外部排序
1. 外部排序的基本概念
对大文件进行排序，无法将整个文件拷贝到内存中进行排序。因此要将待排序记录存储在外存上，排序时再把数据一部分一部分的调入内存中进行排序。在排序过程中，需要多次进行内存和外存之间的交换，排序后的结果仍然存在原有文件中。
2. 外部排序的方法
3. 多路平衡归并与败者树
4. 置换-选择排序
5. 最佳归并树
