八、排序
8.1 排序的基本概念
排序(Sort)，就是重新排列表中的元素，使表少的元素满足按关键字有序的过程。
输入∶n个记录R1,R2...., Rn，对应的关键字为k1, k2,... , kn
输出:输入序列的一个重排R1',R2'....,Rn'，使得有k1'≤k2'≤...≤kn'(也可递减)
排序算法的评价指标
算法的稳定性。若待排序表中有两个元素R,和R，其对应的关键字相同即key = keyj，且在排序前R;在R,的前面，若使用某一排序算法排序后，R仍然在R的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
8.2 插入排序
8.2.1 插入排序
算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
算法实现
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
int i,j,temp;
for(i=1; i<n; i++){ //将各元素插入已排好序的序列中
if(A[i]<A[i-1]){ //如果A[i]关键字小于前驱
temp=A[i]; //用temp暂存A[i]
for(j=i-1; j>=0 && A[j]>temp; --j) //检查所有前面已排好序的元素
A[j+1]=A[j]; //所有大于temp的元素都向后挪
A[j+1]=temp; //复制到插入位置
}
}
}
算法实现(带哨兵)
//直接插入排序(带哨兵)
void InsertSort(int A[], int n){
int i,j;
for(i=2; i<=n; i++){ //依次将A[2]~A[n]插入到前面已排序列
if(A[i]<A[i-1]){ //若A[i]关键码小于其前驱，将A[i]插入有序表
A[0]=A[i]; //复制为哨兵，A[0]不放元素
for(j=i-1; A[0]<A[j]; --j) //从后往前查找待插入位置
A[j+1]=A[j]; //向后挪位
A[j+1]=A[0]; //复制到插入位置
}
}
}
算法效率分析
空间复杂度:O⑴
时间复杂度:主要来自对比关键字、移动元素若有n个元素，则需要n-1趟处理
最好情况∶原本就有序
共n-1趟处理，每一趟只需要对比关键字1次，不用移动元素
最好时间复杂度——O(n)
最坏情况：原本为逆序
第1趟:对比关键字2次，移动元素3次
第2趟:对比关键字3次，移动元素4次
...
第i趟:对比关键字i+1次，移动元素 i+2次
...
第n-1趟:对比关键字n次，移动元素n+1次
最坏时间复杂度——O(n^2)
空间复杂度:O⑴
最好时间复杂度（全部有序): O(n)
最坏时间复杂度（全部逆序):O(n^2)
平均时间复杂度:O(n^2)
算法稳定性:稳定
优化——折半插入排序
思路：先用折半查找找到应该插入的位置，再移动元素
当low>high时折半查找停止，应将[low, i-1]内的元素全部右移，并将A[0]复制到 low 所指位置
当A[mid]==A[0]时，为了保证算法的“稳定性”，应继续在mid 所指位置右边寻找插入位置
当 low>high时折半查找停止，应将[low, i-1]内的元素全部右移，并将A[0]复制到low 所指位置当Amid]==A[0]时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n){
int i,j,low,high,mid;
for(i=2; i<=n; i++){ //依次将A[2]~A[n]插入前面的已排序列
A[0]=A[i]; //将A[i]暂存到A[0]
low=1; high=i-1; //设置折半查找的范围
while(low<=high){ //折半查找(默认递增排序)
mid=(low+high)/2; //取中间点
if(A[mid]>A[0])
high=mid-1; //查找左半子表
else
low=mid+1; //查找右半子表
}
for(j=i-1; j>high+1; --j)
A[j+1]=A[j]; //统一后移元素，空出插入位置
A[high+1]=A[0]; //插入操作
}
}
对链表进行插入排序
//对链表L进行插入排序
void InsertSort(LinkList &L){
LNode *p=L->next, *pre;
LNode *r=p->next;
p->next=NULL;
p=r;
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=r;
}
}
移动元素的次数变少了，但是关键字对比的次数依然是O(n^2)数量级，
整体来看时间复杂度依然是O(n^2) 
8.2.2 希尔排序
希尔排序︰先将待排序表分割成若干形如L[i, i + d, i + 2d,..., i + kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程,直到d=1为止。
// 对A[]数组共n个元素进行希尔排序
void ShellSort(ElemType A[], int n){
int d,i,j;
//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
for(d=n/2; d>=1; d=d/2){ //步长d递减
for(i=d+1; i<=n; ++i){
if(A[i]<A[i-d]){ //需将A[i]插入有序增量子表
A[0]=A[i]; //A[0]做暂存单元，不是哨兵
for(j=i-d; j>0 && A[0]<A[j]; j-=d)
A[j+d]=A[j]; //记录后移，查找插入的位置
A[j+d]=A[0]; //插入
}
}
}
}
算法性能分析
空间复杂度：O(1)
时间复杂度：和增量序列d1,d2,d3...的选择有关，目前无法用数学手段证明确切的时间复杂度
最坏时间复杂度为O(n^2),当n在某个范围内时，可达O(n^1.3)
适用性：仅适用于顺序表，不适用于链表
8.3 交换排序
基于“交换”的排序︰根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
8.3.1 冒泡排序
从后往前(或从前往后)两两比较相邻元素的值，若为逆序〈即A[i-1]>A[i])，则交换它们，直到序列比较完。这样过程称为“一趟”冒泡排序。
// 交换a和b的值
void swap(int &a, int &b){
int temp=a;
a=b;
b=temp;
}
// 对A[]数组共n个元素进行冒泡排序
void BubbleSort(int A[], int n){
for(int i=0; i<n-1; i++){
bool flag = false; //标识本趟冒泡是否发生交换
for(int j=n-1; j>i; j--){ //一趟冒泡过程
if(A[j-1]>A[j]){ //若为逆序
swap(A[j-1],A[j]); //交换
flag=true;
}
}
if(flag==false)
return; //若本趟遍历没有发生交换，说明已经有序
}
}
算法效率分析：
时间复杂度：最好情况 O(n)，最差情况O(n^2)，平均情况 O(n^2)
空间复杂度：O(1)。
稳定性：稳定。
适用性：冒泡排序可以用于顺序表、链表。
8.3.2 快速排序
算法思想∶在待排序表L_[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分L[1...k-1和LIk+1..n]，使得L[1...k-1]中的所有元素小于pivot，L[k+1...n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止。
快速排序是所有内部排序算法中性能最优的排序算法。
在快速排序算法中每一趟都会将枢轴元素放到其最终位置上。（可用来判断进行了几趟快速排序）
快速排序可以看作数组中n个元素组织成二叉树，每趟处理的枢轴是二叉树的根节点，递归调用的层数是二叉树的层数。
代码实现：
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
int pivot = A[low]; //第一个元素作为枢轴
while(low<high){ //用low、high搜索枢轴的最终位置
while(low<high && A[high]>=pivot)
--high;
A[low] = A[high]; //比枢轴小的元素移动到左端
while(low<high && A[low]<=pivot)
++low;
A[high] = A[low]; //比枢轴大的元素移动到右端
}
A[low] = pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴的最终位置
}
// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
if(low<high){ //递归跳出的条件
int pivotpos = Partition(A, low, high); //划分
QuickSort(A, low, pivotpos - 1); //划分左子表
QuickSort(A, pivotpos + 1, high); //划分右子表
}
}
算法效率分析：
时间复杂度：快速排序的时间复杂度 = O(n×递归调用的层数)。
最好情况O(nlog2n)，最差情况O(n^2)，平均情况O(n^2)。
空间复杂度：快速排序的空间复杂度 = O(递归调用的层数)。
最好情况O(log2n)，最差情况O(n)，平均情况O(n^2)
稳定性：不稳定。
若每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，则递归深度最小，算法效率最高
快速排序算法优化思路:尽量选择可以把数据中分的枢轴元素。
eg:①选头、中、尾三个位置的元素，取中间值作为枢轴元素;②随机选一个元素作为枢轴元素
平均时间复杂度=O(nlog2n)
8.4 选择排序
8.4.1 简单选择排序
选择排序︰每一趟在待排序元素中选取关键字最小(或最大）的元素加入有序子序列。
n个元素的简单选择排序需要n-1趟处理
算法实现：
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n){
for(int i=0; i<n-1; i++){ //一共进行n-1趟，i指向待排序序列中第一个元素
int min = i; //记录最小元素位置
for(int j=i+1; j<n; j++){ //在A[i...n-1]中选择最小的元素
if(A[j]<A[min]) //更新最小元素位置
min = j; //封装的swap()函数共移动元素3次
}
if(min!=i)
swap(A[i], A[min]);
}
}
算法性能分析
空间复杂度：O(1)
稳定性：不稳定
适用性：既可用于顺序表，也可用于链表
8.4.2_1 堆排序
什么是堆？
若n个关键字序列L[ 1...n ]满足下面某一条性质，则称为堆(Heap) :
若满足∶L(i)≥L(2i)且L(i)≥L(2i+1) (1 ≤i <n/2 ) 一大根堆(大顶堆)
若满足∶L(i)≤L(2i)且L(i)≤L(2i+1) (1≤i <n/2 ) ―小根堆(小顶堆)
思路:把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整
检查当前结点是否满足根≥左、右，若不满足，将当前结点与更大的一个孩子互换
若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断“下坠”)
- i的左孩子 -—2i
- i的右孩子 -—2i+1
- i的父节点 -—[i/2]
建立大根堆(代码)
// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
for(int i=len/2; i>0; i--) //从后往前调整所有非终端结点
HeadAdjust(A, i, len);
}
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
A[0] = A[k]; //A[0]暂存子树的根结点
for(int i=2*k; i<=len; i*=2){ //沿k较大的子结点向下调整
if(i<len && A[i]<A[i+1])
i++; //取key较大的子结点的下标
if(A[0] >= A[i]) //筛选结束
break;
else{
A[k] = A[i]; //将A[i]调整至双亲结点上
k=i; //修改k值，以便继续向下筛选
}
}
A[k] = A[0]; //被筛选结点的值放入最终位置
}
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
BuildMaxHeap(A, len); //初始建立大根堆
//i 指向待排元素序列中的最后有关(堆底元素)
for(int i=len; i>1; i--){ //n-1趟的交换和建堆过程
swap(A[i], A[1]);
HeadAdjust(A,1,i-1);
}
}
时间复杂度：O(nlog2n)。建堆时间O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)
空间复杂度：O(1)。
稳定性：不稳定。
8.4.2_2 堆排序的插入删除
在堆中插入新元素
对于小根堆，新元素放到表尾，与父节点对比,若新元素比父节点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止
在堆中删除元素
被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止
8.5 归并排序和基数排序
8.5.1 归并排序
归并：把两个或多个已经有序的序列合并成一个
“4路”归并——每选出一个小元素注需对比关键字3次
m路归并，每选出一个元素需要对比关键字m-1次
算法思想：把待排序表看作 n 个有序的长度为1的子表，然后两两合并，得到 ⌈n/2⌉ 个长度为2或1的有序表……如此重复直到合并成一个长度为n的有序表为止。
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++)
B[k]=A[k]; //将A中所有元素复制到B中
for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
if(B[i]<=B[j]) //两个元素相等时，优先使用靠前的那个(稳定性)
A[k]=B[i++];
else
A[k]=B[j++]; //将较小值复制到A中
}
while(i<=mid)
A[k++]=B[i++];
while(j<=high)
A[k++]=B[j++];
}
// 递归操作
void MergeSort(int A[], int low, int high){
if(low<high){
int mid = (low+high)/2; //从中间划分
MergeSort(A, low, mid); //对左半部分归并排序
MergeSort(A, mid+1, high); //对右半部分归并排序
Merge(A,low,mid,high); //归并
}
}
8.5.2基数排序
基数排序的算法效率分析
需要r个辅助队列，空间复杂度=O(r)
一趟分配O(n)，一趟手机O(r)，总共d趟分配、收集，总的时间复杂度=O(d(n+r))
(把关键字拆为d个部分 每个部分可能取得r个值)
收集一个队列只需O(1)的时间
稳定性：基数排序是稳定的
基数排序擅长解决的问题:
①数据元素的关键字可以方便地拆分为d 组，且d较小。 反例:给5个人的身份证号排序
②每组关键字的取值范围不大，即r较小。 反例：给中文人名排序
③数据元素个数n较大。 擅长：给十亿人的身份证号排序
8.7 外部排序
8.7.1+8.7.2外部排序
外存、内存之间的数据交换
操作系统以“块”为单位对磁盘存储空间进行管理，如:每块大小1KB
各个磁盘块内存放着各种各样的数据
磁盘的读/写以“块"为单位数据读入内存后才能被修改修改完了还要写回磁盘
外部排序原理
构造初始“归并段”
构造初始归并段：需要16次“读”和16次“写”
第一趟归并 将两个有序归并段归并为一个 把8个有序子序列(初始归并段)两两归并
外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间
若能增加初始归并段的长度，则可减少初始归并段数量r
8.7.3败者树
败者树的构造
败者树——可视为一棵完全二叉树（多了一个头头)。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。
败者树在多路平衡归并中的应用
对于k路归并，第一次构造败者树需要对比关键字k-1次
有了败者树，选出最小元素，只需对比关键字 ⌈log2k⌉ 次
五路归并的败者树 int ls[5];
8.7.4置换-选择排序
可以用一片更大的内存区域来进行内部排序（如:可容纳18个记录)
每个“初始归并段”可包含18个记录
用于内部排序的内存工作区WA可容纳l个记录，则每个初始归并段也只能包含Ⅰ个记录，若文件共有n个记录，则初始归并段的数量r = n/l
置换—选择排序
把最小的元素“置换”出去
注：假设用于内部排序的内存工作区只能容纳3个记录
若内存工作区的元素比minimax小，不可能放到归并段末尾
8.7.5最佳归并树
每个初始归并段看作一个叶子结点，归并段的长度作为结点权值，则上面这棵归并树的带权路径长度WPL= 2*1 +(5+1+6+2)*3 =44=读磁盘的次数=写磁盘的次数
重要结论:归并过程中的磁盘I/O次数=归并树的WPL*2
要让磁盘/Oi次取,就要使归并树WPL最小——哈夫曼树!
构建2路归并的最佳归并树
最佳归并树WPLmin= (1+2)*4＋2*3+5*2＋6*1=34
读磁盘次数=写磁盘次数=34次;总的磁盘I/O次数=68
多路归并的情况
WPL =(9+30+12+18+3+17+2+6+24)*2= 242
归并过程中磁盘I/O总次数=484次
注意:对于k叉归并，若初始归并段的数量无法构成严格的k叉归并树,则需要补充几个长度为0的“虚段”，再进行k 叉哈夫曼树的构造。
