1. 第七章 排序
1.1. 概述
排序就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索服务的。
相同键值的两个记录在排序前后相对位置的变化情况是排序算法研究中经常关注的一个问题，这个问题称为排序算法的稳定性。稳定性是排序方法本身的特性，与数据无关，换句话说，一种排序方法如果是稳定的，则对所有的数据序列都是稳定的，反过来，如果在一组数据上出现不稳定的现象，则该方法是不稳定的。
排序可分为两大类：
- 内部排序（Internal Sorting）：待排序的记录全部存放在计算机内存中进行的排序过程；
- 外部排序（External Sorting）：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。
待排序的数据存储结构，用类C语言描述如下：
typedef struct
{
int key;
ItemType otheritem;
}RecordType;
typedef RecordType List[n+1];
1.2. 插入排序
常见的插入排序方法：
- 直接插入排序
- 折半插入排序
- 表插入排序
- 希尔排序
直接插入排序（Straight Insertion Sorting）是一种简单的排序方法，它的基本思想是依次将每个记录插入到一个已排好序的有序表中去，从而得到一个新的、记录数增加1的有序表。
直接插入排序算法描述如下：
void StraightInsertSort(List R, int n) // 对顺序表R进行直接插入排序
{
int i,j;
for(i=2;i<=n;i++) // n为表长，从第二个记录起进行插入
{
R[0] = R[i]; // 第i个记录复制为岗哨
j=i-1;
while(R[0].key<R[j].key) // 与岗哨比较，直至键值不大于岗哨键值
{
R[j+1]=R[j]; // 将第j个记录赋值给第j+1个记录
j--;
}
R[j+1]=R[0]; // 将第i个记录插入到序列中
}
}
直接插入的算法简单，易于理解，容易实现，时间复杂度为O（n^2），若待排序记录的数量很大时，一般不选用直接插入排序。从空间来看，它只需要一个记录的辅助空间，即空间复杂度O（1）。
直接插入排序方法是稳定的。
1.3. 交换排序
交换排序的基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录，这样将键值较小的记录向序列前部移动，键值较大的记录向序列后部移动。
1.3.1. 冒泡排序
冒泡排序（Bubble Sorting）是一种交换排序，其过程是首先将第一个记录的键值和第二个记录的键值进行比较，若为逆序（即R[1].key>R[2].key），则将这两个记录交换，然后继续比较第二个和第三个记录的键值。依此类推，直到完成第n-1个记录和第n个记录的键值比较交换为止。
冒泡排序的算法描述如下：
void BubbleSort(List R, int n)
{
int i,j,temp,endsort;
for(i=1;i<n-1;i++)
{
endsort=0;
for(j=1;j<n-i-1;j++)1
{
if(R[j].key>R[j+1].key) // 如果逆序则交换记录
{
temp=R[j];
R[j]=R[j+1];
R[j+1]=temp;
endsort = 1;
}
}
if(endsort==0) break;
}
}
该算法的时间复杂度为O（n^2），冒泡排序是稳定的排序方法。
1.3.2. 快速排序
快速排序（Quick Sorting）是交换排序的一种，实质上是对冒泡排序的一种改进。它的基本思想：在n个记录中取某一个记录的键值为标准，通常取第一个记录键值为基准，通过一趟排序将待排序的记录分为小于或等于这个键值和大于这个键值的两个独立的部分，这时一部分的记录键值均比另一部分记录的键值小，然后，对这两部分记录继续分别进行快速排序，以达到整个序列有序。
下面给出一趟快速排序的算法：
int QuickPartition(List R, int low, int high)
{
// 对R[low]，R[low+1],...,R[high]子序列进行一趟快速排序
x=R[low];// 置初值
while(low<high)
{
while((low<high)&&(R[high].key>=x.key)) high--;
R[low]=R[high];// 自尾端进行比较，将比x键值小的记录移至低端
while((low<high)&&(R[low].key<=x.key)) low--;
R[high]=R[low];// 自首端进行比较，将比x键值大的记录移至高端
}
R[low]=x;// 一趟快速排序结束，将x移至其最中位置
return low;
}
完整的快速排序可写成如下递归算法：
void QuickSort(List R, int low, int high)
{
// 对记录序列R[low],R[low+1],...,R[high]进行快速排序
if(low<high)
{
temp=QuickPartition(R,low,high);
QuickSort(R,low,temp-1);
QuickSort(R,temp+1,high);
}
}
1.4. 选择排序
选择排序（Selection Sorting）的基本思想：每一次n-i+1(i=1,2,...,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。
1.4.1. 直接选择排序
直接选择排序算法的基本思想：在第i次选择操作中，通过n-i次键值间比较，从n-i+1个记录中选出键值最小的记录，并和i（1<=i<=n-1）个记录交换。
算法描述如下：
void SelectSort(List R, int n)
{
int min,i,j;
for(i=1;i<=n-1;i++)// 每次循环，选择出一个最小键值
{
min=i;// 假设第i个记录键值最小
for(j=i+1;j<=n;j++)
{
if(R[j].key<R[min].key) min=j;// 记录下键值最小记录的下标
}
if(min!=i) swap(R[min], R[i]);// 将最小键值记录和交换第i个记录交换
}
}
1.4.2. 堆排序
自顶向下的调整过程称为“筛选”，算法描述如下：
void Sift(List R, int k, int m)
{
/* 假设R[k],R[k+1],...,R[m]是以R[k]为根的完全二叉树，R[k]的左、右子树均满足堆的性质。本算法调整R[k]使整个序列R[k],R[k+1],...,R[m]满足堆的性质 */
int i,j,x;
List t;
i=k;j=2*i;
x=R[k].key;
t=R[k];
while(j<=m)
{
if((j<m)&&(R[j].key>R[j+1].key))
{
j++;// 若存在右子树，且右子树根的关键字小，则沿右分支筛选
if(x<R[j].key)break;// 筛选完毕
else { R[i]=R[j];i=j;j=2*i;}
}
}
R[i]=t;// 填入恰当位置
}
堆排序算法描述如下：
void HeapSort(List R)
{
// 对R[n]进行堆排序，排序完成后，R中记录按关键字自大至小有序排列
int i;
for(i=n/2;i>=1;i--)
Shit(R,i,n);// 从第n/2个记录开始进行筛选建堆
for(i=n;i>=2;i--)
{
swap(R[1],R[i]);// 将堆顶记录和堆中最后一个记录互换
Sift(R,1,i-1);// 调整R[1]是R[1],...,R[i-1]变成堆
}
}
1.5. 归并排序
- 要求：若干个有序子序列组成。
- 归并：将两个或两个以上的有序表合并成一个新的有序表。
- 合并方法：比较各子序列的第一个记录的键值，最小的一个是排序后序列的第一个记录的键值。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排序结果。
- 归并排序的基础是合并。
1.5.1. 有序序列的合并
void Merge(List a, List R, int h, int m, int n)
{
// 将ah,...,am和am+1,...,an两个有序序列合并成一个有序序列Rh,...,Rn
k=h;j=m+1;// k,j置成文件的起始位置
while((h<=m) && (j<n))// 将a中记录从小到大合并入R
{
if(a[h].key<=a[j].key)// a[h]键值小，送入R[k]并修改h值
{
R[k]=a[h];
h++;
}
else // a[j]键值小，送入R[k]并修改j值
{
R[k]=a[j];
j++;
}
k++;
}
while(h<m){R[k]=a[h];h++;k++;}// j>n，将ah,...,am剩余部分插入R的末尾
while(j<=n){R[k]=a[j];j++;k++;}// h>m，将am+1,...,an剩余部分插入R的末尾
}
1.5.2. 二路归并排序
二路归并排序即是将两个有序表合并成一个有序表的排序方法，其基本思想：假设序列有n个记录，可看成n个有序的子序列，每个序列的长度为1。首先将每相邻的两个记录合并，得到n/2个较大的有序子序列，每个子序列包含2个记录，再将上述子序列两两合并，得到n/2/2个有序子序列，如此反复，直至得到一个长度为n的有序序列为止，排序结束。
二路归并算法的核心是每一次的归并操作，所以根据前面介绍的算法Merge，写出执行一次归并的算法MergePass如下：
void MergePass(List a,List b,int n, int h)
{
/* 在含有n个记录的序列a中，将长度各为h的相邻两个有序子序列合并成长度为2h的一个有序序列，并把结果存入b中 */
i=1;
while(i<=n-2*h+1)
{
merge(a,b,i,i+h-1,i+2*h-1);// 将序列ai,...,ai+h-1和序列ai+h,...,ai+2*h-1合并成序列bi,...,bi+2*h-1
i+=2*h;//下边i移动2*h
}
if(i+h-1<n)// h<剩余序列长度<2h
merge(a,b,i,i+h-1,n);// 将序列ai,...,ai+h-1和ai+h,...,an合并成bi,...,bn
else for(t=i;t<=n;t++)b[t]=a[t];// 将剩余序列长度<h,将ai,...,an复制到bi,...,bn
}
二路归并排序算法描述如下：
void MergeSort(List a,int n)
{
// 将序列a1,a2,...,an按关键字的非递减次序进行排序，b也定义为list类型
m=1;// m为子序列长度，初始值为1
while(m<n)
{
MergePass(a,b,n,m);// 将序列a中有序子序列合并到b
m=2*m;// 子序列长度扩大1倍
MergePass(b,a,n,m);// 将序列b中有序子序列合并到a
m=2*没；// 子序列长度扩大1倍
}
}