一、排序的基本概念
1、排序的稳定性：对于一组记录，如果其中两条记录R1，R2 相等，若在排序之前 和 排序之后 二者顺序仍然不变，则认为该排序算法是稳定的，否则该排序算法不稳定。
2、排序算法效率的评价指标：
1）执行时间：主要与 两个因素有关：关键字之间的比较次数；记录的移动次数；
2）辅助空间：理想的空间复杂度为O(1)；
二、内部排序
除基数排序 用链式存储以外 ，其它的排序方法 存储结构均用 顺序存储，如下：
1、插入排序
1）直接插入排序(Straight Insertion Sort)：其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的，记录数量增1的有序表。
以下为直接插入排序的伪代码：
2）折半插入排序(Binary Insertion Sort)：在将一个元素 插入 前边的有序序列时，适用折半查找，来寻找该元素的插入位置，这种排序方式称之为 折半排序；
折半排序伪代码：
总结：
1、折半排序 是稳定排序；
2、折半排序 中，与关键字比较的次数为Log2i + 1，移动次数 与 直接插入排序
相同，因此，最好情况下，折半排序 的时间复杂度为O(n)，最坏情况下，折半排序的时间复杂度为O(n2)；
3、折半排序 中，所用辅助空间只有L.r[0]，因此，其空间复杂度为O(1)；
4、折半排序 更适用于 初始记录无序，n较大时的情况；
5、因为要折半查找，所以 折半排序 只适用于 顺序存储形式，不适用于 链式存储形式；
3）希尔排序（Shell’s Sort）：从“减少记录个数” 和 “序列基本有序” 两方面对 直接插入排序 进行了改进。
总结：
1、希尔排序 的时间复杂度 是排序趟数t的函数，比较难计算，但是一些结论指出，其时间复杂度为O(ni)，1<i<2；
2、希尔排序 中用到的辅助空间为L.r[0]，空间复杂度为O(1)；
3、希尔排序 为 不稳定排序；
4、希尔排序 适用于初始记录无序，n较大的情况；
5、希尔排序 只适用于 顺序存储结构，不适用于 链式存储结构；
6、希尔排序中的增量值，应除1以外，没有其他的公因子，并且最后一个增量值为1；
2、交换排序
1）冒泡排序(Bubble Sort)：是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录上浮，使关键字大的记录下沉。
每一趟排序，会是最大的关键字沉到 最后一个记录。
有n个元素的表，需要进行n-1趟冒泡排序。
总结：
0、冒泡排序 为 稳定排序；
1、冒泡排序，最好的情况下，只进行n-1次比较，不进行移位，此时，时间复杂度为O(n)；最坏的情况下，每趟排序进行i-1次比较，3*（i-1）次移位，此时比较总数：sum(i-1),i=n,…,2；移位总数：sum(3*(i-1)),i=n,…,2；此时的时间复杂度为O(n2)；冒泡排序的时间复杂度 较 直接插入排序 还要高一点儿；
2、冒泡排序中只用到一个辅助空间t，因此，空间复杂度为O(1)；
3、冒泡排序也适合于 链式存储结构；
4、冒泡排序 不适用于 初始记录无序，n较大的情况；
2）快速排序(Quick Sort)：在待排序的n个记录中任取一个记录（通常取第一个记录）作为枢纽，设其关键字为pivotkey。经过一趟排序后，把所有关键字<pivotkey的记录交换到前面，把所有关键字>pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢纽放置在分界处的位置。然后，分别对其左、右子表重复上述过程，直至每一子表只有一个记录时，排序完成。
快速排序伪代码：
总结：
0、快速排序 为 不稳定排序；
1、快速排序 最坏的情况下，退化成一个单支树，则共需排n-1趟序，每次排序比较n-i次，则 共需比较 sum(n-i),i=1,…,n-1 = n(n-1)/2 = n2/2，此时时间复杂度O(n2)；最好的情况下，每趟排序都把表一分为2，则共需排log2n趟序，每趟比较n次，此时时间复杂度为O(nlog2n)；
2、快速排序 需要界定上下界，因此，很难用于 链式存储；
3、pivotkey的选取：对 first,last,mid 3个记录的key作比较，取中间值作pivotkey，将其换到第一个记录的位置；
4、快速排序是 所有 内部排序 中 速度最快的一个，适用于 初始记录无序，n较大的情况；
3、选择排序
选择排序的核心思想是：每一次从待排序序列中选出一个最小值， 将其放到有序序列的最后，直到全部排完为止。
1）简单选择排序(Simple Selection Sort)：直接选择排序，每次从n-i个元素中选出最小，然后排到有序序列的最后。
简单选择排序 伪代码：
总结：
1、直接选择排序最好的情况，无需移动记录；最坏的情况下，排序需移动3(n-1)次记录；但是，无论哪种情况，其比较次数均为：sum(n-i),i=n-1,…,1 = n(n-1)/2 = n2/2； 时间复杂度为O(n2)；
2、直接选择排序 只用到一个辅助空间，因此，空间复杂度为O(1)；
3、直接选择排序 移动次数较少，与 直接插入排序 相比，更快速；
4、直接选择排序 也适用于 链式存储结构；
5、上述的直接选择排序方法 为 不稳定排序，这是由于采用 交换记录 的策略造成的，只要改变这个策略，也可以 写出 稳定的 直接选择排序；
总结：
1、树形选择排序 每次选择最小关键字 需比较 log2n 次，因此，选n个最小关键字 需 比较 nlog2n 次，其时间复杂度为O(nlog2n)；
2、树形选择排序 还有很多改进空间：比如：每次选key都要和 无穷大 做比较；需要的辅助空间比较多等；
3）堆排序(Heap Sort)：利用 大(小)根堆 来选择 最大(小)关键字，重复n-1次，依次选出 最大(小) 关键字，即完成排序；
堆排序的关键 在于 创建堆 和 调整堆；
首先，介绍堆的含义，所谓堆 是一个 用 顺序存储 表示的 二叉树 结构，在大(小)根堆中，双亲结点 较lchild和rchild 要大(小)，根节点为 最大(小)关键字。
在 顺序存储中，i的lchild为2i，rchild为2i+1；
下面给出堆排序的伪代码：
总结：
0、堆排序 是 不稳定排序；
1、堆排序 的时间复杂度 主要来源于 创建堆 和 调整堆；
创建堆 的时间复杂度为O(n)；
调整堆 的时间复杂度为Log2n，共需调整n-1次，因此，堆排序的时间复杂度 最坏情况为O(nlog2n)；
2、堆排序 只能用于 顺序存储结构，不能用于链式存储结构；
3、相对于 快速排序 最坏情况下 时间复杂度为O(n2)，堆排序较优，当记录较多时，比较高效；
4、归并排序(Merging Sort)
总结：
0、归并排序 是 稳定排序；
1、假设序列长度为h，一趟归并需要进行 n/2h 次Merge，总共的比较次数为n。归并排序共需要进行log2n （2ih = n ; i = log2(n/h)）趟归并。所以，归并排序的时间复杂度为O(nlog2n)。
2、归并排序 需要与 表等长的 存储空间 作为辅助存储空间，因此，其时间复杂度为O(n);
3、归并排序 可用于 链式存储结构，且不需辅助空间，但仍需递归工作栈的存储空间。
5、基数排序(Radix Sorting)
基数排序是典型的分类排序，不需要比较关键字，他是根据关健值中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。
本节 介绍 链式基数排序。
假设逻辑关键字由 d 个 “关键字”组成，每个关键字可能取rd个值，这里说的 基 即指 rd的取值范围。
总结：
0、是稳定排序；
1、 链式基数排序 时间复杂度分析：
假设有n个记录，每个逻辑关键字有d个关键字，每个关键字可取rd个值，对每个关键字进行一趟分配的时间复杂度为O(n)，进行一次收集的时间复杂度为O(rd)，总共有d个关键字，因此，其总得时间复杂度为O(d(n+rd))；突破了其它 内存排序O(nlog2n)的下限；
2、空间复杂度：所需2rd个辅助队列指针，以及每个数据元素中存储的一个指针，共n个存储空间，所以，空间复杂度为O(n+rd)；
3、可用于 链式结构，也可用于顺序结构？？？
4、基数排序具有严格的要求：需要知道各级关键字的主次关系 和 各级关键字的取值范围；
三、外部排序
外部排序 可以分为两步：1）在内部对各分段进行内部排序，得到各个归并段；2）在外存，对各个归并段进行归并；
外部排序所用时间 = 内部排序时间 + 外存读写时间 + 归并时间；
由此可以看出，外存读写时间 和 归并时间 对于外部排序的时间复杂度 贡献很大；
要想降低 外部排序 的时间，则应想办法 降低 外存读写时间 和 归并时间；
外存读写时间 = 归并趟数 * n条记录读写次数 + 内存排序时的读写次数
由此可以看出，要想降低 外部排序读写时间，则可以降低 ：归并趟数 or 初始归并段的个数；
当初始归并段一定时，归并趟数的降低 可以 通过提高 k-路归并 中 k的值来实现。但是，此时归并时间可能会增加。
原来采用2-路归并时，对u个记录进行归并，则只需比较u-1次即可，但是，如果采用k-路归并，则比较次数变为 (u-1)(k-1)。
乘以归并趟数后，2-路归并和k-路归并 所需 归并时间 分别变为：
log2m * (u-1)；m为初始归并段个数；
logkm * (u-1)(k-1) = (log2m)/(log2k) * (u-1)(k-1)
此时，可以看出，归并时间并不会随k的增加而单纯下降，而是呈：先下降后上升的趋势。若想消除k的影响，则必须消除 (k-1)/(log2k) ，则，使 每次选出最小关键字的比较次数从 k-1降到 log2k 即可。未达到这个目的，我们可以用 “败者树”来 选出最小关键字。
除使用多路归并外，还有一种 降低 归并时间 的 方法是，降低初始归并段 的 个数；
为降低初始归并段的个数，我们可以采用 “置换-选择排序”；
置换-选择 排序 的具体步骤如下：
假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内存工作区为WA，FO和WA的初始状态为空，并设内存工作区的容量可容纳w个记录，则 置换-选择排序的操作过程为：
1、从FI输入w个记录到工作区WA；
2、从WA中选出最小的关键字记录为MINIMAX；
3、将MINIMAX输入到FO中；
4、若FI不为空，则从FI输入下一个记录到WA中；
5、从WA中所有关键字中选出一个比MINIMAX要大的关键字输出到FO，并将这个关键字记为新的MINIMAX。
6、重复3-5步，直到WA中没有比MINIMAX大的关键字，说明第一个归并段输出完毕。
7、重复2-6，直到WA为空，输出不同的归并段。
实验证明，当初始记录随机排列时，所得初始归并段为WA长度的2倍。