一、排序的基本概念
1、排序的稳定性：对于一组记录，如果其中两条记录R1，R2 相等，若在排序之前 和 排序之后 二者顺序仍然不变，则认为该排序算法是稳定的，否则该排序算法不稳定。
2、排序算法效率的评价指标：
1）执行时间：主要与 两个因素有关：关键字之间的比较次数；记录的移动次数；
2）辅助空间：理想的空间复杂度为O(1)；
二、内部排序
除基数排序 用链式存储以外 ，其它的排序方法 存储结构均用 顺序存储，如下：
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType Key;
InfoType otherinfo;
}RedType; //记录元素 存储形式
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList; //表 存储形式
1、插入排序
1）直接插入排序(Straight Insertion Sort)
：其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的，记录数量增1的有序表。
以下为直接插入排序的伪代码：
//本直接插入排序中 采用 顺序存储的形式
void InsertSort(SqList &L){
for(i=2;i<=L.length;++i){ //L.r[0]不存储
if(L.r[i].key < L.r[i-1].key){
L.r[0] = L.r[i]; //最小存储在L.r[0]中
L.r[i] = L.r[i-1]; //由于r[i]较r[i-1]小，因此，将r[i-1]后移
}
for(j=i-2;L.r[0].key < L.r[j].key;--j){ //如果i较前边有序序列中元素小，则将有序序列中的元素一直后移
L.r[j+1] = L.r[j];
}
L.r[j+1] = L.r[0]; //当r[0]>=r[j]时，跳出循环，并将r[0]存储在r[j+1]的位置
}
}
总结：
1、直接插入排序为 稳定排序；
2、直接插入排序需要进行n-1趟排序，最好情况下，每趟排序进行1次比较，不移动，则总共需比较n-1次，此时的时间复杂度为O(n)。最坏情况下，每趟排序需要比较i次，移动i+1次，则总共需要比较sum(i),i=2,..,n =(n+2)(n-1)/2 = n^2^/2，总共需要移动sum(i+1),i=2,...n = (n+4)(n-1)/2 = n^2^/2，此时时间复杂度为O(n^2^)；
3、直接插入排序中，仅占用了一个辅助空间L.r[0]，因此，空间复杂度为O(1)；
4、直接插入排序 即适用于 顺序存储形式， 也适用于 链式存储形式；
5、当初始记录无序，且n较大时，不适合适用 直接插入排序；
2）折半插入排序(Binary Insertion Sort)
：在将一个元素 插入 前边的有序序列时，适用折半查找，来寻找该元素的插入位置，这种排序方式称之为 折半排序；
折半排序伪代码：
void BInsertSort(SqList &L){
for(i=2;i<=L.length;++i){
low = 1;
high = i-1;
while(low <= high){
mid = (low+high)/2;
if(L.r[i].key <= L.r[mid].key){ //等号的位置可以随便放？
high = mid-1;
} //如果元素i比mid小，则继续向前推进，查看i是否比其他元素更小
else{
low = mid+1;
}
} //返回的low为i应该在的位置
L.r[0] = L.r[i]; //存放元素i
for(j=L.length;j>low;--j){ //将 大于i的元素后移
L.r[j] = L.r[j-1];
}
L.r[j] = L.r[0]; //存放元素i
}
}
总结：
1、折半排序 是稳定排序；
2、折半排序 中，与关键字比较的次数为Log2i + 1，移动次数 与 直接插入排序
相同，因此，最好情况下，折半排序 的时间复杂度为O(n)，最坏情况下，折半排序的时间复杂度为O(n
2
)；
3、折半排序 中，所用辅助空间只有L.r[0]，因此，其空间复杂度为O(1)；
4、折半排序 更适用于 初始记录无序，n较大时的情况；
5、因为要折半查找，所以 折半排序 只适用于 顺序存储形式，不适用于 链式存储形式；
3）希尔排序（Shell’s Sort）
：从“减少记录个数” 和 “序列基本有序” 两方面对 直接插入排序 进行了改进。
以下为希尔排序的一个实例：
每趟选取不同的增量dk，对序列进行直接插入排序：
希尔排序伪代码：
//一趟希尔排序
void SellInsert(SqList &L,int dk){ //以增量dk进行 直接插入排序
for(i=dk+1;i<=L.length;++i){
if(L.r[i].key < L.r[i-dk].key){
L.r[0] = L.r[i];
L.r[i= = L.r[i-dk];
}
for(j=i-2dk;j>0 && L.r[0] < L.r[j];--j){
L.r[j+dk] = L.r[j];
}
L.r[j+dk] = L.r[0];
}
}
//希尔排序
void ShellSort(SqList &L,int dt[],int t){ //进行t趟希尔排序
for(k=0;k<t;++k){
ShellInsert(L,dt[k]);
}
}
总结：
1、希尔排序 的时间复杂度 是排序趟数t的函数，比较难计算，但是一些结论指出，其时间复杂度为O(n
i
)，1<i<2；
2、希尔排序 中用到的辅助空间为L.r[0]，空间复杂度为O(1)；
3、希尔排序 为 不稳定排序；
4、希尔排序 适用于初始记录无序，n较大的情况；
5、希尔排序 只适用于 顺序存储结构，不适用于 链式存储结构；
6、希尔排序中的增量值，应除1以外，没有其他的公因子，并且最后一个增量值为1；
2、交换排序
1）冒泡排序(Bubble Sort)
：是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录上浮，使关键字大的记录下沉。
每一趟排序，会是最大的关键字沉到 最后一个记录。
有n个元素的表，需要进行n-1趟冒泡排序。
冒泡排序伪代码：
void BubbleSort(SqList &L){
m = L.length - 1;
flag = 1;
while(m>0 && flag){
flag = 0; //flag=1，说明进行了冒泡排序
for(i=1;i<=m;++i){
if(L.r[i].key > L.r[i+1].key){ //如果为逆序，交换
t = L.r[i];
L.r[i] = L.r[i+1];
L.r[i+1] = t;
flag = 1;
}
} //每一趟排序会使 最大关键字 沉到最后一个记录
--m;
}
}
总结：
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(n
2
)；冒泡排序的时间复杂度 较 直接插入排序 还要高一点儿；
2、冒泡排序中只用到一个辅助空间t，因此，空间复杂度为O(1)；
3、冒泡排序也适合于 链式存储结构；
4、冒泡排序 不适用于 初始记录无序，n较大的情况；
2）快速排序(Quick Sort)
：在待排序的n个记录中任取一个记录（通常取第一个记录）作为枢纽，设其关键字为pivotkey。经过一趟排序后，把所有关键字<pivotkey的记录交换到前面，把所有关键字>pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢纽放置在分界处的位置。然后，分别对其左、右子表重复上述过程，直至每一子表只有一个记录时，排序完成。
快速排序伪代码：
//调整一次pivotkey的位置
int Partition(SqList &L,int low,int high){
pivotkey = L.r[low].key;
L.r[0] = L.r[low];
while(low < high){
while(low<high && L.r[0].key < L.r[high].key){--high;} //如果pivotKey较元素小，则一直向前挪
L.r[low] = L.r[high]; //把小于r[0]的high元素赋给low
while(low<high && L.r[0].key > L.r[low].key){++low;} //如果pivotkey较元素大，则一直向后挪
L.r[high] = L.r[low];
}
L.r[low] = L.r[0]; //将pivotkey插入正确的位置
return low; //返回pivotkey所在的位置
}
void QSort(SqList &L,int low,int high){
if(low < high){
i = Partition(L,low,high);
QSort(L,low,i-1);
QSort(L,i+1,high);
}
} //完成快排
void QuickSort(SqList &L){
QSort(L,1,L.length);
}
总结：
0、快速排序 为 不稳定排序；
1、快速排序 最坏的情况下，退化成一个单支树，则共需排n-1趟序，每次排序比较n-i次，则 共需比较 sum(n-i),i=1,…,n-1 = n(n-1)/2 = n
2
/2，此时时间复杂度O(n
2
)；最好的情况下，每趟排序都把表一分为2，则共需排log2n趟序，每趟比较n次，此时时间复杂度为O(nlog2n)；
2、快速排序 需要界定上下界，因此，很难用于 链式存储；
3、pivotkey的选取：对 first,last,mid 3个记录的key作比较，取中间值作pivotkey，将其换到第一个记录的位置；
4、快速排序是 所有 内部排序 中 速度最快的一个，适用于 初始记录无序，n较大的情况；
3、选择排序
选择排序的核心思想是：每一次从待排序序列中选出一个最小值， 将其放到有序序列的最后，直到全部排完为止。
1）简单选择排序(Simple Selection Sort)
：直接选择排序，每次从n-i个元素中选出最小，然后排到有序序列的最后。
简单选择排序 伪代码：
//好别扭的一种实现方法
void SelectSort(SqList &L){
for(i=1;i<L.length;++i){
for(j=i;j<=L.length;++i){
if(L.r[j].key < L.r[j+1].key){
L.r[0] = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = L.r[0];
} //把最小值保存到L.r[last]；
}
L.r[0] = L.r[i];
L.r[i] = L.r[L.length]; //把最小值 排到有序列表 最后一个位置
L.r[L.length] = L.r[0];
}
}
//another way
void SelectSort(SqList &L){
for(i=1;i<L.length;++i){
k=i;
for(j=i+1;j<=L.length;++i){
if(L.r[j].key < L.r[k].key){k = j;}
}
if(k != i){
t=L.r[i];
L.r[i] = L.r[k];
L.r[k] = t;
}
}
}
总结：
1、直接选择排序最好的情况，无需移动记录；最坏的情况下，排序需移动3(n-1)次记录；但是，无论哪种情况，其比较次数均为：sum(n-i),i=n-1,…,1 = n(n-1)/2 = n
2
/2； 时间复杂度为O(n
2
)；
2、直接选择排序 只用到一个辅助空间，因此，空间复杂度为O(1)；
3、直接选择排序 移动次数较少，与 直接插入排序 相比，更快速；
4、直接选择排序 也适用于 链式存储结构；
5、上述的直接选择排序方法 为 不稳定排序，这是由于采用 交换记录 的策略造成的，只要改变这个策略，也可以 写出 稳定的 直接选择排序；
2）树形选择排序(Tree Selection Sort)
：
树形选择排序 又叫 锦标赛排序，其核心思想是：
step1：将n个记录作为叶子结点，从每两个叶子节点中 选出最小值，传到他们的 双亲结点，在从 双亲结点层 两两结点 选出最小值 向上一层传递，直到传到根节点，根节点值 即为最小 关键字值。
step2：当选出最小关键字以后，将叶子节点中，该最小关键字值 改为 无穷大，然后 重复step1中 寻找 最小关键字 的操作，即得到 第二小关键字值。
step3：如此反复，直到得出全部的最小关键字值，即 完成排序。
具体排序过程如下图所示：
总结：
1、树形选择排序 每次选择最小关键字 需比较 log2n 次，因此，选n个最小关键字 需 比较 nlog2n 次，其时间复杂度为O(nlog2n)；
2、树形选择排序 还有很多改进空间：比如：每次选key都要和 无穷大 做比较；需要的辅助空间比较多等；
3）堆排序(Heap Sort)
：利用 大(小)根堆 来选择 最大(小)关键字，重复n-1次，依次选出 最大(小) 关键字，即完成排序；
堆排序的关键 在于 创建堆 和 调整堆；
首先，介绍堆的含义，所谓堆 是一个 用 顺序存储 表示的 二叉树 结构，在大(小)根堆中，双亲结点 较lchild和rchild 要大(小)，根节点为 最大(小)关键字。
在 顺序存储中，i的lchild为2i，rchild为2i+1；
其次，介绍 调整 堆 的方法，具体如下：
大根堆中 的 最大关键字 为97，将其 与 最后一个结点38 对调，然后调整根堆：
首先，比较38的两个孩子，76>65，则将76上移，38下移，然后，在比较38的两个孩子，49=49，38下移，49上移，完成一次根堆调整。
从这个调整过程可以看出，每次调整都局限于 以38为根节点的子树；
下面给出堆排序的伪代码：
//调整大根堆
void HeapAdjust(SqList &L,int s,int m){ //从下标s到m，调整s的位置
L.r[0] = L.r[s]; //先将s保存到0中
for(j=2*s;j<m;j*=2){
if(j<m && L.r[j].key < L.r[j+1].key){++j;} //将j的值调为 较大叶子节点值对应下标
if(L.r[j].key < L.r[0].key){break;} //不用调整
L.r[s] = L.r[j]; //将s的值转给j
s = j; //小一轮要调整的 堆 的根节点
}
L.r[s] = L.r[0];
}
//创建堆：n/2以下的元素为叶子节点，自成一堆，以n/2以上的元素为根的堆，需要进行调整
void CreatHeap(SqList &L){
n = L.length;
for(i=n/2;i>0;--i){
HeapAdjust(L,i,n);
}
}
//堆排序
void HeapSort(SqList &L){
CreatHeap(L); //创初堆
for(i=L.length;i>1;--i){
t = L.r[i];
L.r[i] = L.r[1];
L.r[1] = t; //将 最大关键字 放到 列表尾部
HeapAdjust(L,1,i-1); //调整根堆
}
}
总结：
0、堆排序 是 不稳定排序；
1、堆排序 的时间复杂度 主要来源于 创建堆 和 调整堆；
创建堆 的时间复杂度为O(n)；
调整堆 的时间复杂度为Log2n，共需调整n-1次，因此，堆排序的时间复杂度 最坏情况为O(nlog2n)；
2、堆排序 只能用于 顺序存储结构，不能用于链式存储结构；
3、相对于 快速排序 最坏情况下 时间复杂度为O(n
2
)，堆排序较优，当记录较多时，比较高效；
4、归并排序(Merging Sort)
我们在这里介绍2路归并：在最开始的时候，将1一个关键字作为一组，进行2 2 归并，一趟排序后，每个新的组中有2个关键字，对新的组进行 2 2归并，归并完成后，形成的组中 有4个关键字。
重复上述操作，直到 2 2 归并后，组内元素为数据元素总数。
以下为 归并排序 的图示：
归并排序伪代码如下：
//进行一趟归并
void Merge(RedType R[],RedType T[],int low,int mid,int high){ //R为原表，T记录归并后的表，low和high为R中的上下界,mid为两个归并表的界限
i=low;
j=mid+1;
k=low;
while(i<=low && j<=high){
if(R[i].key <= R[j].key){T[k++] = R[i++];}
else{T[k++] = R[j++];}
}
while(i<=low){T[k++] = R[i++];}
while(j<=high){T[k++] = R[j++];}
}
//进行归并排序
void MSort(RedType R[],RedType T[],int low,int high){
if(low = high){T[low] = R[low];}
else{
mid = (low+high)/2;
MSort(R,S,low,mid);
MSort(R,S,mid+1,high); //对这两部分 进行归并排序
Merge(R,T,low,mid,high); //对上两部分 进行归并
}
}
void MergeSort(SqList &L){
MSort(L.r,L.r,1,L.length);
}
总结：
0、归并排序 是 稳定排序；
1、假设序列长度为h，一趟归并需要进行 n/2h 次Merge，总共的比较次数为n。归并排序共需要进行log2n （2
i
h = n ; i = log2(n/h)）趟归并。所以，归并排序的时间复杂度为O(nlog2n)。
2、归并排序 需要与 表等长的 存储空间 作为辅助存储空间，因此，其时间复杂度为O(n);
3、归并排序 可用于 链式存储结构，且不需辅助空间，但仍需递归工作栈的存储空间。
5、基数排序(Radix Sorting)
基数排序是典型的分类排序，不需要比较关键字，他是根据关健值中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。
本节 介绍 链式基数排序。
假设逻辑关键字由 d 个 “关键字”组成，每个关键字可能取rd个值，这里说的 基 即指 rd的取值范围。
链式基数排序的具体图示如下：
链式基数排序伪代码：
//链式基数排序 采用 静态链表
#define MAXNUM_KEY 8 //逻辑关键字 的 关键字个数
#define RADIX 10 //每个关键字的取值个数
#define MAX_SPACE 10000
typedef struct{
KeyType keys[MAXNUM_KEY];
InfoType otheritems;
int next;
}SLCell; //每个数据元素存储形式
typedef struct{
SLCell r[MAX_SPACE];
int keynum; //逻辑关键字 的 关键字个数
int recnum; //表长
}SLList; //表的存储形式
typedef int ArrType[RADIX] //存储 每个关键字 的 表达范围
//首先，根据第i位关键字 对数据元素 进行 串串
void Distribute(SLCell &r,int i,ArrType &f,ArrType &e){
//r为表；i为串串的第i位关键字；f为队头列表，e为队尾列表
//初始化f
for(i=0;i<RADIX;++i){f[i]= 0;}
for(p=r[0].next;p;p=r[p].next){ //r[0]为头指针
j = order(r[p].keys[i]); //找出其第i位关键字为RADIX中的哪一个
if(!f[j]){f[j]=p;} //如果为第一个是 第J为RADIX 的元素，执行此操作
else{r[e[j]].next=p;} //否则，将j为的尾元素的next赋为p
e[j] = p;
}
} //通过这个函数，就将分属第i位radix的不同value的元素 分到了不同的 f[j]中
//对Distribute()进行Collect
void Collect(SLCell &r,int i,ArrType f,ArrType e){
for(i=0;!f[i];i = succ(i)); //succ为求后继的操作
r[0].next = f[i];
t = e[i];
while(i<RADIX){
for(i=succ(i);!f[i] && i<RADIX-1;i=succ(i));
if(f[i]){
r[t].next = f[i];
t=e[i];
}
}
r[t].next = 0;
}
//进行 链式基数排序
void RadixSort(SLList &L){
//对表 进行 初始化
for(i=0;i<L.recnum;++i){L.r[i].next = i+1;}
L.r[L.recnum].next = 0;
for(k=0;k<L.keynum;++k){
Distribute(L.r,k,f,e);
Collect(L.r,k,f,e);
}
}
总结：
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 即可。未达到这个目的，我们可以用 “败者树”来 选出最小关键字。
所谓“败者树”，即：叶子节点 为各个关键字，双亲结点 记录着 叶子节点中的败者，胜者向上继续比较，直到 根节点 仍然记录 败者。头结点中记录胜者。
当选出一个胜者后，将原胜者所处位置在 丢入一个 关键字，与该叶子节点所处子树 的 结点 进行比较，选出败者，胜者上，直到选出胜者为止，第二个 最小关键字产生。
败者树 如下图所示：
图a中胜者 为 b3 结点； 图b中胜者 为b1结点；
尽管使用败者树，可以消去k过大的影响，但是实际中，k的选择仍然需要慎重。
除使用多路归并外，还有一种 降低 归并时间 的 方法是，降低初始归并段 的 个数；
为降低初始归并段的个数，我们可以采用 “置换-选择排序”；
置换-选择 排序 的具体步骤如下：
假设初始待排序文件为输入文件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倍。
置换-选择排序中，WA中最小关键字的选出 依然可以用 败者树 来实现，以下为用败者树 选出 最小关键字的过程。
有这么一个规定，如果败者树中各节点“段号”相同，则优先输出 最小的关键字。若“段号”不同，则优先输出 较小的段号。
置换-选择排序中，记录的存储结构如下：
typedef struct{
RedType rec; //记录信息
KeyType key; //记录关键字
int rnum; //记录段号
}RcdNode,WorkArea[W];
WorkArea wa; //内存工作区 定义
利用 “置换-选择排序”得到的初始归并段 并不等长，那么使用什么方式 对这些归并段进行归并最好？
我们先来看一个初始归并段，段长分别为：9，30，12,18,3,17,2,6,24，如果要对这些归并段进行 3-路归并，则可以用如下方式：
此时，外存读写次数为：(9+30+12+18+3+17+2+6+24) * 2 * 2 =484，可以看出，这并不是最优的归并方式，我们可以将归并段的长度看作是叶子节点的权值，以初始归并段为叶子节点，做哈弗曼树，由此，可以得到最小的外存读写次数。
当叶子节点个数 数目 不够时，需附加长度为零的“虚段”，按照哈夫曼树构成的原则，权为零的叶子应离根最远。因此，这个只有8个初始归并段的归并树应如下图所示：
假设m为初始归并段数目，k为k-路归并，则，当(m-1)MOD(k-1)=0时，不需加虚段，否则，需附加 k-(m-1)MOD(k-1)-1 个虚段。
若按最佳归并树 的 归并方案 进行磁盘归并排序，需在内存建立一张载有归并段的长度和它在磁盘上的物理位置的索引表。