排序排序 （ sorting） 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素 （ 或记录 ） 的任意序列,重新排列成一个按关键字有序的序列 。
由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中对外存进行访问的排序过程。
插入排序线性插入排序的基本思想是：第 1遍，将初始文件中的记录 R1看作有序子文件，将 R2插入这个子文件中。若 R2的关键字小于 R1的关键字，则
R2插在 R1的前面，否则 R2插在 R1的后面。第 2
遍，将 R3插入前面的两个记录的有序子文件中，
得到 3个记录的有序子文件。依此类推，继续进行下去，直到将 Rn插入到前面的 n-1个记录的有序子文件中，最后得到 n个记录的有序文件。
线性插入排序的基本思想是：第 1遍,将初始文件中的记录 R1看作有序子文件,
将 R2插入这个子文件中 。 若 R2的关键字小于 R1的关键字,则 R2插在 R1的前面,否则 R2插在 R1的后面 。 第 2遍,
将 R3插入前面的两个记录的有序子文件中,得到 3个记录的有序子文件 。
依此类推,继续进行下去,直到将 Rn
插入到前面的 n-1个记录的有序子文件中,最后得到 n个记录的有序文件 。
图 9-1所示为线性插入排序的例子 。
为了避免检测是否应插在 R1的前面，在
R1的前面设立记录 R0，它既是中间变量，又是监视哨。设（ R1,R2,…,
Ri-1）是已排序的有序子文件，则插入 Ri的步骤是：首先将 Ri存放到 Ro中，
然后将 Ko（即原 Ri的关键字 Ki）依次与 Ki-1,Ki-2,… 比较，若 Ko<Kj
（ j=i-1,i-2,…,1），则 Rj后移一个位置，否则停止比较和移动；最后，
将 Ro（即原来待插入的记录 Ri）移到
j+1的位置上。由于 Ri的前面有监视哨 Ro，因此不必每次判断下标 j是否出界。算法描述如下：
void insertsort(struct node r[ n+1],int n)
/* r[n+1]为一维数组,其中 r[0]为监视哨,r[1]到 r[n]为待排序的 n个记录,排序好的记录仍放在 r中 */
{ for(i=2;i<=n;i++) /*共进行 n-1趟 */
{ r[0]=r[i]; /*r[0]为监视哨,也可做下边循环结束标志 */
j=i-1;
while(r[j].key>r[0].key)
{ r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
折半插入排序在线性插入排序中,我们采用顺序查找法来确定记录的插入位置 。 由于 （ R1,R2,…,Ri-1） 是有序子文件,我们可以采用折半查找法来确定 R1的插入位置,这种排序称为折半插入排序 。 其算法可写出如下：
void binarysort(struct noder[n+1],int n)
/*按关键字递增的次序对记录 r[1],r[2],……,r[n]进行折半插入排序 */
{ for(i=2;i<=n;i++)
{ r[0]=r[i];
l=1;
h=i-1;
while(l<=h)
{ mid=(l+h)/2;
if(r[0].key<r[mid].key)
h=mid-1;
else l=mid+1;
}
for(j=i-1;j>=l;j--)
r[j+1]=r[j];
r[l]=r[0];
}
}
在上面的算法中，每插入一个 R1，平均比较次数为 log2i。
希尔排序希尔排序 （ Shell’s Method） 又称,缩小增量排序,（ Diminishing Increment Sort）,
是由 D.L.Shell在 1959年提出来的 。 它的作法是：先取定一个小于 n的整数 d1作为第一个增量,把文件的全部记录分成 d1个组,所有距离为 d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,到第二个增量 d2<d1重复上述分组和排序,直至所取的增量 dt=1（ dt<dt-1<… <d2<d1）,即所有记录放在同一组中进行直接插入排序为止 。
先从一个具体的例子来看希尔排序 。 假设待排序文件有 10个记录,其关键字分别是：
49,38,65,97,76,13,27,49/,55,04。 增量序列取值依次为,5,3,1。
第一趟排序时,d1=5,整个文件被分成 5组,（ R1,R6）,（ R2,R7）,…,（ R5，
R10） 各组中的第 1个记录都自成一个有序区,我们依次将各组的第 2个记录 R6，
R7,… R10分别插入到各组的有序区中,使文件的各组均是有序的,其结果见图 9-
2的第七行 。
第二趟排序时,d2=3,整个文件分成三组,（ R1,R4,R7,R10）,（ R2,R5,R8）,
（ R3,R6,R9）,各组的第 1个记录仍自成一个有序区,然后依次将各组的第 2个记录 R4,R5,R6分别插入到该组的当前有序区中,使得 （ R1,R4）,（ R2,R5）,
（ R3,R6） 均变为新的有序区,接着依次将各组的第 3个记录 R7,R8,R9分别插入到该组当前的有序区中,又使得 （ R1,R4,R7）,（ R2,R5,R8）,（ R3,R6，
R9） 均变为新的有序区,最后将 R10插入到有序区 （ R1,R4,R7） 中就得到第二趟排序结果 。
最后一趟排序时,d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。
若不设置监视哨，根据上例的分析不难写出希尔排序算法，请读者自行完成之。下面我们先分析如何设置监视哨，然后给出具体算法。设某一趟希尔排序的增量为 h，则整个文件被分成 h组：（ R1,Rh+1,R2h+1,… ），
（ R2,Rh+2,R2h+2,… ）,… （ Rh,R2h,R3h,… ），
因为各组中记录之间的距离均为是 h，故第 1组至第 h组的哨兵位置依次为 1-h,2-h,…,0。如果象直接插入排序算法那样，将待插入记录 Ri（ h+1≤i≤N） 在查找插入位置之前保存到监视哨中，那么必须先计 Ri属于哪一组，才能决定使用哪个监视哨来保存 Ri。为了避免这种计算，我们可以将 Ri保存到另一个辅肋记录 X中，
而将所有监视哨 R1-h,R2-h,…,R0的关键字，设置为小于文件中的任何关键字即可。因为增量是变化的，
所以，各趟排序中所需的监视哨数目也不相同，但是我们可以按最大增量 d1来设置监视哨。
rectype R[n+d1]； /* R[d1-1]为 d1个监视哨 */
int d[t]； /* d[0]到 d[t-1]为增量序列 */
SHELLSORT(R,d)
Rectype R[]；
int d[]；
{int i,j,k,h；
rectype temp;
int maxint=32767； /*机器中最大整数 */
for (i=0； i<d[0]； i++)
R[i].key=-maxint； /*设置哨兵 */
K=0；
Do{
H=d[k]； /*取本趟增量 */
For(i=h+di； i<n+d1； i++) /*R[h+d1]到 R[n+d1-1]插入当前有序区 */
{temp=R[i]}； /*保存待插入记录 R[i]*/
j=i-h；
while(temp.key<R[j].key) /*查找正确的插入位置 */
{R[j+h]=R[j]}； /*后移记录 */
j=j-h； /*得到前一记录位置 */
}
R[j+h]=temp； /*插入 R[i]*/
} /*本趟排序完成 */
k++；
} while (h！ =1)； /*增量为 1排序后终止算法 */
} /*SHELLSORT*/
读者可能看出,当增量 h=1时,SHELLSORT算法与 INSERTSORT基本一致 。
对希尔排序的分析提出了许多困难的数学问题,特别是如何选择增量序列才能产生最好的排序效果,至今没有得到解决 。 希尔本为最初提出取 d1=┗ n/2┛,di+1=┗ di/2┛,dt=1,t=┗ log2n┛ 。 后来又有人提出其它选择增量序列的方法,如 di+1=┗ (di-1)/3┛,dt=1，
t=┗ log3n-1┛ ；以及 di+1=┗ (di-1)/2┛,dt=1,t=┗ log2n-1┛ 。
为什么希尔排序的时间性能优于直接插入排序呢？ 我们知道直接插入排序在文件初态为正序时所需要时间最少,实际上,当文件初基本有序时直接插入排序所需的比较和移动次数均较少 。 另一面,
当 n值较小时,n和 n2的差别也较小,即直接插入排序的最好时间复杂度 O(n)和最坏时间复杂度 O(n2)差别不大 。 在希尔排序时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,
后来增量 di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按 di-1作为距离排过序,使文件较近于有序状态,
所以新的国趟排序过程也较快 。 因此,希尔排序在较率上较直接接入排序有较大的改进 。
希尔排序是不稳定的。参见图 9-2的例子，该例中两个相同关键字 49
在排序前后的相对次序发生了变化。
选择排序选择排序 （ selection sort） 也是一种简单排序法 。 一个记录最多只需进行一次交换就可以直接到达它的排序位置 。
设待排序的文件为 （ R1,R2,…,Rn）,进行选择排序的基本步骤如下：
（ 1） 置 i 为 1；
（ 2） 当 i<n时,重复下列步骤；
1） 当 (Ri,…,Rn)中选出一个关键字最小的记录 Rmin,若 Rmin不是 Ri,即
Rmin≠i则交换 Ri和 Rmin的位置；否则,不进行交换 。
2） i的值加 1。
第 1遍扫描时,在 n个记录中为了选出最小关键字的记录,需要进行 n-1次比较,第 2扫描时,在余下的 n-1记录中,再选出具有最小关键字的记录需要比较 n-2次,…… 第 n-1扫描时,在最后的 2个记录中,比较 1次选出最小关键字的记录 。
堆排序堆排序 (heap sort)是在选择排序的基础上发展起来的 。 它比选择排序的效率要高 。 在堆排序中,把待排序的文件逻辑上看作是一棵顺序二叉树,并用到堆的概念 。
在介绍堆排序之前,先引入堆的概念 。
我们回忆一下，一棵有 n个结点的顺序二叉树可以用一个长度为 n的向量 (一维数组 )来表示；反过来，一个有 n个记录的顺序表示的文件，在概念上可以看作是一棵有 n
个结点 (即记录 )的顺序二叉树。例如，一个顺序表示的文件 (R1,R2,……,R9)，可以看作为图 9-4所示的顺序二叉树。
当我们把顺序表示的文件 (R1,R2,…,Rn)看作为顺序二叉树时,由顺序二叉树的性质可知：记录 Ri(1<i≤n)的双亲是记录 R[i 2]； R1的左孩子是记录 R2i(2i≤n),但若 2i>n,则 Ri的左孩子不存在；
Ri的右孩子是记录 R2i+1(2i+1≤n),但若 2i+1>n,则 Ri的右孩子不存在 。
什么是堆呢?堆是一个具有这样性质的顺序二叉树,每个非终端结点 (记录 )的关键字大于等于它的孩子结点的关键字 。 例如,图 9-5所示的顺序二叉树就是一个堆 。
显然,在一个堆中,根结点具有最大值 (指关键字,下同 ),而且堆中任何一个结点的非空左,右子树都是一个堆,它的根结点到任一叶子的每条路径上的结点都是递减有序的 。
堆排序的基本思想是：首先把待排序的顺序表示 (一维数组 )的文件 (R1,R2,…,Rn)在概念上看作一棵顺序二叉树,并将它转换成一个堆 。 这时,根结点具有最大值,删去根结点,然后将剩下的结点重新调整为一个堆 。 反复进行下去,直到只剩下一个结点为止 。
堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆 。 初始状态时,结点是随机排列的,需要经过多次调整才能把它转换成一个堆,这个堆叫做初始堆 。 建成堆之后,交换根结点和堆的最后一个结点的位置,相当于删去了根结点 。 同时,剩下的结点 (除原堆中的根结点 )又构成一棵顺序二叉树 。 这时,根结点的左,右子树显然仍都是一个堆,它们的根结点具有最大值
(除上面删去的原堆中的根结点 )。 把这样一棵左,右子树均是堆的顺序二叉树调整为新堆,是很容易实现的 。
例如,对于图 7-7所示的堆,交换根结点 63和最后的结点 30之后,便得到图 9-6(a)所示的顺序二叉树 (除 63之外 )。 现在,新的根结点是 30,其左,右子树仍然都是堆 。 下面讨论如何把这棵二叉树调整为一个新堆 。
由于堆的根结点应该是具有最大值的结点,且已知左,右子树是堆,因此,新堆的根结点应该是这棵二叉树的根结点,根结点的左孩子,根结点的右孩子 (若存在的话 )中最大的那个结点 。 于是,先找出根结点的左,右孩子,比较它们的大小 。 将其中较大的孩子再与根结点比较大小 。
如果这个孩子大于根结点,则将这个孩子上移到根结点的位置,而根结点下沉到这个孩子的位置,即交换它们的位置 。 在图 9-6(a)中,根结点 30的左,右孩子分别是 60,59,由于 60>59，
并且 60>30,于是应交换根结点 30和左孩子 60的位置 。
这时，新的根结点 60的右子树没有改变，仍然是一个堆。但是，由于结点 30下沉到左子树的根上，
使得左子树有可能不再是堆了。按照上面所用的办法，把这棵子树调整为一个堆，显然，结点 30的左、右子树原来都是堆,30的左、右子树分别是 40,45。由于 40<45，并且 45>30，于是应交换结点 30和右孩子 45的位置。
void adjust(struct node r[m+1],int m)
/* 将文件 (r[1],r[2],…,r[m])解释为一棵顺序二叉树,将其中以 r[i]为根结点的二叉树调整为一个堆,设以 r[i]为根的二叉树的左,右子树已是堆,1≤i≤1[m/2] */
{ x=r[i];j=2*i;
/*求出 r[i]的左孩子 r[2*i],即 r[j] */
while (j<=m) /*有左孩子 */
{ if ((j<m) &&(r[j].key<r[j+1].key)) /*比较左,右孩子 */
j=j+1; /*左孩子 <右孩子 */
if (x.key<r[j].key) /*比较根结点和它的大孩子 */
{ r[i]=r[j]; /*大孩子上移到它的双亲位置 */
i=j; /*今 r[j]为根结点 */
j=2*i; /*求出左孩子 */
}
else j=m+1 /*根不小于它的任一孩子时,强迫退出 while
循环 */
}
r[i]:=x; /*将存放在 x
中的根结点放到 r[i]中 */
}
快速排序快速排序 (Quick Sort)称划分交换排序。其基本思想是：在当前无序区 R[1]到 R[h]到中任取一个记录作为比较的“基准”（不妨记为 temp），
用此基准将当前无序区划分为左右两个较小的无序子区,R[1]到 R[i-1]和 R[i+1]到 R[h]，且左边的无序子区中记录的关键字均小于或等于基准 temp的关键字，右边的无序子区中记录的关键字均大于或等于基准 temp的关键字，而基准
temp则位于最终排序的位置上
R[1]到 R[i-1]中关键字 ≤temp.key=R[i+1]到 R[h]的关键字 （ 1≤i≤h）
当 R[1]到 R[I-1]和 R[I+1]到 R[h]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中记录均已排好序为止 。
要完成对当前无序区 R[1]到 R[h]的划分，具体做法是：设置两个指针
i和 j，它们的初值分别为 i=1和 j=h。不妨取基准为无序区的第 1个记录 R[i]（即 R[1]），并将它保存在变量 temp中。令 j自 h起向左扫描，直到找到第 1个关键字小于 temp.key的记录 R[j]，将 R[j]移至 i
所指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）的位置，
使关键字小于基准关键字的记录移到了基准的左边）；然后，令 i
自 i+1起向右扫描，直至找到第 1个关键字大于 temp.key的记录 R[i]，
将 R[i]移至 j指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）
的位置，使关键字大于基准关键字的记录移到了基准的右边）；
接着，令 j自 j+1起向右扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至 i=j时,i便是基准 x的最终位置，将 x放在此位置 上就完成了一次划分。
综合上面的叙述,下面分别给出一次划分及其排序的算法 。
int partition(r,1,h) /*返回划分后被定们的基准记录的位置 */
rectype R[ ]; /*对无序区 R[1]到 R[h]做划分 */
int 1,h;
{int i,j;
rectype temp;
i=1;j=h temp=R[i]; /*初始化,temp为基准 */
Do{
While((R[j].key>=temp.key) && (i<j))
j--; /*从右向左扫描,查找第 1个关键字小于 temp.key的记录 */
if(i<j) R[i++]=R[j]; /*交换 R[i]和 R[j]*/
while((R[i].key<=temp.key) && (i<j))
i++; /*从左向左扫描,查找第 1个关键字大于
temp.key的记录 */
if(i<j) R[j--]=R[i]; /*交换 R[i]和 R[j]*/
}
quicksort(R,s1,t1) /*对 R[s1]到 R[t1]*/
rectype R[ ];
int s1,t1;
{int i;
if (s1<t1) /* 只有一个记录或无记录须排序 */
{i= partition (R,s1,t1); /*对 R[s1]到 R[t1]做划分 */
quicksort (R,s1,i-1); /*递归处理左区间 */
quicksort (R,i+1,t1); /*递归处理右区间 */
}
}
图 9-7展示了一次划分的过程及整个快速排序的过程 。 图中方括号表示无序区,方框表示基准 temp的关键字,它未参加真正的交换,只是在划分完成时才将它放入正确的位置上 。
初始关键字 [[49 ] 38 65 97 76 13 27 49`]
i j
j向左扫描 [[49] 38 65 97 76 13 27 49 `]
i j
第一次交换后 [27 38 65 97 76 13 [ ] 49`]
i j
i向右扫描 [27 38 65 97 76 13 [ ] 49 `]
i j
第二次交换后 [27 38 [ ] 97 76 13 65 49 `]
i j
j向左扫描,位置不变第三次交换后 [27 38 13 97 76 [ ] 65 49]`]
i向左扫描,位置不变,i j
第四次交换后 [27 38 13 [ ] 76 97 65 49 `]
i j
j向左扫描 [27 38 13 [49] 76 97 65 49 `]
i j
初始关键字,[49 38 65 97 76 13 27 49`]
一趟排序之后,[27 38 13] 49 [76 97 65 49`]
二趟排序之后,[13] 27 [38] 49 [49` 65] 76 [97]
三趟排序之后,13 27 38 49 49` [65] 76 97
最后的排序结果,13 27 38 79 79` 65 76 97
(b) 各趟排序之后的状态最坏情况是第次划分选取的基准都是当前无序区中关键字最小 （ 或最大 ） 的记录,划分的基准左边的无序子区为空 （ 或右边的无序子区为空 ）,而划分所得的另一个非空的无序子区中记录数目,
仅仅比划分前的无序区中记录个数减少一个 。 因此,快速排序必须做 n-1趟,每一趟中需进行 n-i次比较,故总手工艺比数次数达到最大值：
Cmax=∑(n-i)=n(n-1)/2=O(n2)
显然,如果按上面给出的划分算法,每次取当前无序区的第 1个记录为基准,那么当文件的记录已按递增序 （ 或递减序 ） 排列时,每次划分所取的基准就是当前无序区中关键字最小 （ 或最大 ） 的记录,则快速排序所需的比较次数反而最多 。
在最好情况下,每次划分所取的基准都是当前无序区的,中值,记录,划分的结果是基准的左,右两个无序子区的长度大致相等地 。
设 C（ n） 表示对长度为 n的文件进行快速排序所需的比较次数,
显然,它应该等于对长度为 n的无序区进行划分所需的比较次数 n-
1。 加上递归地对划分所得的左,右两个无序子区 （ 长度 ≤n/2） 进行快速排序所需的比较总人数。
假设文件长度 n=2k,那么总的比较次数为：
C(n) ≤n+2C(n/2)
≤n+2[n/2+2C(n/22)]=2n+4C(n/22)
≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)
≤……
≤kn+2kC(n/2k)=nlog2n+nC(1)
=O(nlog2n)
注意：式中 C（ 1）为一常数,k=log2n。,
因为快速排序的记录移动次数不大于比较的次数,所以,
快速排序的最坏时间复杂度应为 O（ n2）,最好时间复杂雅兴 O(log2n)。 为了改善最坏情况下的时间性能,可采用三者取中的规则,即在每一趟划分开始前,首先比较 R[1].key,R[h].key和 R[[(1+h)/2]].key,令三者中取中值的记录和 R[1]交换之 。
可以证明：快速排序的平均时间复杂度也是 O(nlog2n)，
它是目前基于比较的内部排序方法 中速度最快的,快速排序亦因此而得名 。
快速排序需要一个栈空间来实现递归 。 若每次划分均能将文件均 匀分割 为两 部分,则栈的 最大深 度为
[log2n]+1,所需栈空间为 O（ log2n） 。 最坏情况下,递归深度为 n,所需栈空间为 O（ n)。
快速排序是不稳定的，请读者自行检验。
归并排序归并排序 (Merge Sort)是利用“归并”技术来进行排序，
所谓归并是指将若干个已排序的子文件合并成一个有序的文件。简单的归并是将两个有序的子文件合并成一个有序的文件。假设 R(low)到 R[m]和 R[m+1]到
R[high]是存储在同一个数组中且相邻的两个有序的子文件，要将它们合并为一个有序文件 R1[low]到 R1[high]，
只要设置三个指示器 i,j和 k，其初值分别是这三个记录区的起始位置。合并时依次比较 R[i]和 R[j]的关键字，
取关键字较小的记录复制到 R1[k]中，然后，将指向被复制记录的指示器加 1和指向复制位置的指示器 K加 1，
重复这一过程，直至全部记录被复制到 R1[low]到
R1[high]中为止。
基数排序前介绍的排序方法都是根据关键字值的大小来进行排序的 。 本节介绍的方法是按组成关键字的各个位的值来实现的排序的,这种方法称为基数排序 （ radix sort） 。 采用基数排序法需要使用一批桶 （ 或箱子 ）,故这种方法又称为桶排序列 。 下面以十进制数为例来说明基数排充的过程 。
假定待排序文件中所有记录的关键字为不超过 d位的非负整数,从最高位到最低位
（ 个位 ） 的编号依次为 1,2,…,d。 设置 10个队列 （ 即上面所说的桶 ）,它们的编号分别为 0,1,2,…,9。 当第一遍扫描文字时,将记录按关键字的个位 （ 即第 d位）数分别放到相应的队列中：个位数为 0的关键字，其记录依次放入 0号队列中 i
个位数为 1的关键字，其记录放入 1号队列中 … ；个位数为 9的关键字，其记录放入
9号队列中。这一过程叫做按个位数分配。现在把这 10个队列中的记录，按 0号,1
号,9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。
这是第 1遍。第 2遍排序使用同样的办法，将第 1遍排序后的记录按其关键字的十位数（第 d— 1位）分配到相应的队列中，再把队列中的记录收集和排列起来。继续进行下去。第 d遍排序时，按第 d— 1遍排序后记录的关键字的最高位（第 1位）进行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以
10为基的关键字的基数排序法。
关键字
1 02
2 77
3 70
4 54
5 64
6 21
7 55
8 11
9 38
1 0 21
初始状态
70
21,1 1,2 1
02
5 4,6 4
55
77
38
70
21
11
21
02
54
64
55
77
38
02
11
2 1,2 1
38
54,55
64
7 0,7 7
02
11
21
21
38
54
55
64
70
77
10 个队列 关键字第一遍，按个位数分配收集后 收集后第二遍，按十位数分配例如,给出关键字序列 （ 02,77,70,54,64,21,55,11,38,21）,其中关键字 02用 1个 0在 2的前面补足到 2位,余关键字均为 2位的正整数 。 进行基数排序的过程如图 9-9所示 。
在这个例子中,文件和所有的队列都表示成向量 （ 一维数组 ） 。 显然,关键字的某一位有可能均为同一个数字 （ 例如,个数都为 0）,这时所有的记录都同时装入同一个队列中 （ 例如,同时装入 0号队列中 ） 。 因此,如果每个队列的大小和文件大小相同,则需要一个 10倍于文件大小的附加空间 。 此外,排序时需要进行反复的分配和收集记录 。 所以,采用顺序表示是不方便的 。
基数排序所需的计算时间不仅与文件的大小 n有关，而且还与关键字的位数、
关键字的基有关。设关键字的基为 r（十进制数的基为 10，二进制数的基为 2），为建立 r个空队列所需的时间为 O（ r）。把 n个记录分放到各个队列中并重新收集起来所需的时间为 O（ n），因此一遍排序所需的时间为
O（ n+r）。若每个关键字有 d位，则总共要进行 d遍排，所以基数排序的时间复杂度为 O（ d（ n+r））。由于关键字的位数 d直接与基数 r以及最大关键字的值有关，因此不同的 r和关键字将需要不同的时间。
在已介绍的上述各种内部排序方法中，就所需要的计算时间来看，快速排序、归并排序、堆排序是很好的方法。但是，归并排序需要大小为
n的辅助空间，快速排序需要一个栈空。除了快速排序、堆排序、选择排序不稳定外，基它排序方法都是稳定的。评价一个排序算法性能好坏的主要标准是它所需的计算时间和存储空间。影响计算时间的两个景要因素是比较关键字的次数和记录的移动次数。在实际应用中，
究竟应该选用何种排序方法，取决于具体的应用和机器条件。
外部排序外部排序基本上由两个相对独立的阶段组成 。 首先,按可用内存大小,将外存上含 n个记录的文件分成若干长度为 l的子文件或段
（ segment）,依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写入外存,通常称这些有序子文件为归并段或顺串 （ run） ；然后,对这些归并段进行逐趟归并,使归并段 （ 有序的子文件 ） 逐渐由小至大,直至得到整个有序文件为止 。 显然,第一阶段的工作是上一章已经讨论过的内容 。 本章主要讨论第二阶段即归并的过程 。 先从一个具体例子来看外排中的归并是如何进行的？
假设有一个含 10000个记录的文件，首先通过 10次内部排序得到 10个初始归并段 R1~R10，其中每一段都含 1000个记录。然后对它们作如下图所示的两两归并，直至得到一个有序文件为止。
将两个有序段归并成一个有序段的过程,若在内存进行,则很简单,
上一章中的 merge过程便可实现此归并 。 但是,在外部排序中实现两两归并时,不仅要调用 merge过程,而且要进行外存的读 /写,
这是由于我们不可能将两个有序段及归并结果段同时存放在内存中的缘故 。 在 11.1节中已经提到,对外存上信息的读 /写是以,物理块,为单位的 。 假设在上例中每个物理块可以容纳 200个记录,
则每一趟归并需进行 50次,读,和 50次,写,,四趟归并加上内部排序时所需进行的读 /写使得在外排中总共需进行 500次的读 /写 。
一般情况下,外部排序所需总的时间 =
内部排序 （ 产生初始归并段 ） 所需的时间 m*tIS
+外部信息读写的时间 d*tIO （ 11-1）
+内部归并所需的时间 s*utmg
其中,tIS是为得到一个初始归并段进行内部排序所需时间的均值；
tIO是进行一次外存读 /写时间的均值； utmg是对 u个记录进行内部归并所需时间； m为经过内部排序之后得到的初始归并段的个数；
s为归并的趟数； d为总的读 /写次数。
其中 tIO取决于所用的外部设备,显然,tIO较 tmg要大得多 。 因此,提高外排的效率应主要着眼于减少外存信息读写的次数 d。
下面来分析 d和,归并过程,的关系 。 若对上例中所得的 10个初始归并段进行 5-路平衡归并 （ 即每一趟将 5个或 5个以下的有序子文件归并成一个有序子文件 ）,则从下图可见,仅需进行二趟归并,外排时总的读 /写次数便减至 2*100+100=300,比 2-路归并减少了 200次的读 /写 。
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
└──┴──┼──┴───┘ └──┴──┼──┴───┘
R1ˊ R2ˊ
└───────┬──────┘
有序文件可见,对同一文件而言,进行外排时所需读 /写外存的次数和归并的趟数 s成正比 。 而在一般情况下,对 m个初始归并段进行 k-路平衡归并时,归并的趟数
s = [ logkm ]
可见，若增加 k或减少 m便能减少 s。
各种排序方法的比较迄今为止,已有的排序方法远远不止本章讨论的这些方法,人们之所以热衷于研究多种排序方法,不仅是由于排序在计算机中所处的重要地位,而且还因为不同的方法各有其优缺点,可适用于不同的场合 。 选取排序方法时需要考虑的因素有：
待排序的记录数目 n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件,辅助空间的大小等 。
依据这些因素,可得出如下几点结论：
（ 1） 若 n较小 （ 譬如 n50),可采用直接插入排序或直接选 。 由于直接插入排序所需记录移动操作较直接选择排序多,因此若记录本身信息量较大时,则选用直接选择排序为宜 。
（ 2） 若文件的初始状态已是按关键字基本有序,则选用直接插入排序泡排序为宜 。
（ 3） 若 N较大,则应采用时间复杂度为的排序方法：快速排序 \堆排序或归并排序,快速排序是目前基于内部排序的中被认为是最好的方法,档待排序的关键字是随机人布时,快速排序的平均时间最少,但堆排序所需的辅助窨少于快速排序,并且不会出现序可能出现的最坏情况,这两种排序方法都是不稳定的,若要求排序稳定则可选用归并排序 。 但本文章结合介绍的单个记录起进行两两归并排算法并不值得提倡,通常可以将它和直接排序结合在一起用 。 先利用直接插入排序求得的子文件,然后,再两 两 归并之 。 因为直接插入排序是稳定的,所以,改进后的归并排序是稳定的 。
（ 4） 在基于比较的排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此,可以利用一棵二叉树来描述比较判定过程,由此可以证明 ;当文件的 N个关键字分布时,任何借助于比较的排序算法,至少要的时间,由于箱排序和基数排序只需一步就会引起 M种可能的转移,即把一个记录半装入 M个箱子之一,因此,在一般情况下,箱乔序和排序可能在时间内完成对 N个记录的 。 但踞的是,箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字,当关键字的取值范围属于某个无穷集合时,
无法使用箱排序和排序,这时只有借助于比较方法来排序 。 由此可知,若 N较大,记录的关键字倍数较少时且可以分解时采用排序较好 。
（ 5） 前面讨论的排序算法,除排序外,都是在一维数组上实现的,当记录本身信息量较大时,为了避免浪费大量时间移动记录,可以用链表作为存储结构,如插入排序和归并排序都易于在链表上实现,并分别称之为表和归并表,但有的方法,如快速排序和堆排序,
在链表上难于实现,在这种情况下,可以提取关键字建立索引表,然后,对索引表进行排序 。 然而更为简单的方法是 ;引入一个整形向量作为辅助表,排序前,若排序算法中要求交换,则只需交换 R[I ]和 R[j]即可,排序结束后,向量就指示了记录之间的顺序关系：
无论是用链表还是用辅助窨来实现排序,都有可能要求最终结果是,
若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种 重排时间是 o(n)。
本章小结排序（ sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。本章主要介绍了排序的概念及其基本思想，排序过程和实现算法，简述了各种算法的时间复杂度和空间复杂度。一个好的排序算法所需要的比较次数和存储空间都应该较少，
但从本章讨论的各种排序算法中可以看到，不存在
“十全十美”的排序算法，各种方法各有优缺点，可适用于不同的场合。由于排序运算在计算机应用问题中经常碰到，读者应重点理解各种排序算法的基本思想，熟悉过程及实现算法，以及对算法的分析方法，
从而面对实际问题时能选择合适的算法。
由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中对外存进行访问的排序过程。
插入排序线性插入排序的基本思想是：第 1遍，将初始文件中的记录 R1看作有序子文件，将 R2插入这个子文件中。若 R2的关键字小于 R1的关键字，则
R2插在 R1的前面，否则 R2插在 R1的后面。第 2
遍，将 R3插入前面的两个记录的有序子文件中，
得到 3个记录的有序子文件。依此类推，继续进行下去，直到将 Rn插入到前面的 n-1个记录的有序子文件中，最后得到 n个记录的有序文件。
线性插入排序的基本思想是：第 1遍,将初始文件中的记录 R1看作有序子文件,
将 R2插入这个子文件中 。 若 R2的关键字小于 R1的关键字,则 R2插在 R1的前面,否则 R2插在 R1的后面 。 第 2遍,
将 R3插入前面的两个记录的有序子文件中,得到 3个记录的有序子文件 。
依此类推,继续进行下去,直到将 Rn
插入到前面的 n-1个记录的有序子文件中,最后得到 n个记录的有序文件 。
图 9-1所示为线性插入排序的例子 。
为了避免检测是否应插在 R1的前面，在
R1的前面设立记录 R0，它既是中间变量，又是监视哨。设（ R1,R2,…,
Ri-1）是已排序的有序子文件，则插入 Ri的步骤是：首先将 Ri存放到 Ro中，
然后将 Ko（即原 Ri的关键字 Ki）依次与 Ki-1,Ki-2,… 比较，若 Ko<Kj
（ j=i-1,i-2,…,1），则 Rj后移一个位置，否则停止比较和移动；最后，
将 Ro（即原来待插入的记录 Ri）移到
j+1的位置上。由于 Ri的前面有监视哨 Ro，因此不必每次判断下标 j是否出界。算法描述如下：
void insertsort(struct node r[ n+1],int n)
/* r[n+1]为一维数组,其中 r[0]为监视哨,r[1]到 r[n]为待排序的 n个记录,排序好的记录仍放在 r中 */
{ for(i=2;i<=n;i++) /*共进行 n-1趟 */
{ r[0]=r[i]; /*r[0]为监视哨,也可做下边循环结束标志 */
j=i-1;
while(r[j].key>r[0].key)
{ r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
}
折半插入排序在线性插入排序中,我们采用顺序查找法来确定记录的插入位置 。 由于 （ R1,R2,…,Ri-1） 是有序子文件,我们可以采用折半查找法来确定 R1的插入位置,这种排序称为折半插入排序 。 其算法可写出如下：
void binarysort(struct noder[n+1],int n)
/*按关键字递增的次序对记录 r[1],r[2],……,r[n]进行折半插入排序 */
{ for(i=2;i<=n;i++)
{ r[0]=r[i];
l=1;
h=i-1;
while(l<=h)
{ mid=(l+h)/2;
if(r[0].key<r[mid].key)
h=mid-1;
else l=mid+1;
}
for(j=i-1;j>=l;j--)
r[j+1]=r[j];
r[l]=r[0];
}
}
在上面的算法中，每插入一个 R1，平均比较次数为 log2i。
希尔排序希尔排序 （ Shell’s Method） 又称,缩小增量排序,（ Diminishing Increment Sort）,
是由 D.L.Shell在 1959年提出来的 。 它的作法是：先取定一个小于 n的整数 d1作为第一个增量,把文件的全部记录分成 d1个组,所有距离为 d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,到第二个增量 d2<d1重复上述分组和排序,直至所取的增量 dt=1（ dt<dt-1<… <d2<d1）,即所有记录放在同一组中进行直接插入排序为止 。
先从一个具体的例子来看希尔排序 。 假设待排序文件有 10个记录,其关键字分别是：
49,38,65,97,76,13,27,49/,55,04。 增量序列取值依次为,5,3,1。
第一趟排序时,d1=5,整个文件被分成 5组,（ R1,R6）,（ R2,R7）,…,（ R5，
R10） 各组中的第 1个记录都自成一个有序区,我们依次将各组的第 2个记录 R6，
R7,… R10分别插入到各组的有序区中,使文件的各组均是有序的,其结果见图 9-
2的第七行 。
第二趟排序时,d2=3,整个文件分成三组,（ R1,R4,R7,R10）,（ R2,R5,R8）,
（ R3,R6,R9）,各组的第 1个记录仍自成一个有序区,然后依次将各组的第 2个记录 R4,R5,R6分别插入到该组的当前有序区中,使得 （ R1,R4）,（ R2,R5）,
（ R3,R6） 均变为新的有序区,接着依次将各组的第 3个记录 R7,R8,R9分别插入到该组当前的有序区中,又使得 （ R1,R4,R7）,（ R2,R5,R8）,（ R3,R6，
R9） 均变为新的有序区,最后将 R10插入到有序区 （ R1,R4,R7） 中就得到第二趟排序结果 。
最后一趟排序时,d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。
若不设置监视哨，根据上例的分析不难写出希尔排序算法，请读者自行完成之。下面我们先分析如何设置监视哨，然后给出具体算法。设某一趟希尔排序的增量为 h，则整个文件被分成 h组：（ R1,Rh+1,R2h+1,… ），
（ R2,Rh+2,R2h+2,… ）,… （ Rh,R2h,R3h,… ），
因为各组中记录之间的距离均为是 h，故第 1组至第 h组的哨兵位置依次为 1-h,2-h,…,0。如果象直接插入排序算法那样，将待插入记录 Ri（ h+1≤i≤N） 在查找插入位置之前保存到监视哨中，那么必须先计 Ri属于哪一组，才能决定使用哪个监视哨来保存 Ri。为了避免这种计算，我们可以将 Ri保存到另一个辅肋记录 X中，
而将所有监视哨 R1-h,R2-h,…,R0的关键字，设置为小于文件中的任何关键字即可。因为增量是变化的，
所以，各趟排序中所需的监视哨数目也不相同，但是我们可以按最大增量 d1来设置监视哨。
rectype R[n+d1]； /* R[d1-1]为 d1个监视哨 */
int d[t]； /* d[0]到 d[t-1]为增量序列 */
SHELLSORT(R,d)
Rectype R[]；
int d[]；
{int i,j,k,h；
rectype temp;
int maxint=32767； /*机器中最大整数 */
for (i=0； i<d[0]； i++)
R[i].key=-maxint； /*设置哨兵 */
K=0；
Do{
H=d[k]； /*取本趟增量 */
For(i=h+di； i<n+d1； i++) /*R[h+d1]到 R[n+d1-1]插入当前有序区 */
{temp=R[i]}； /*保存待插入记录 R[i]*/
j=i-h；
while(temp.key<R[j].key) /*查找正确的插入位置 */
{R[j+h]=R[j]}； /*后移记录 */
j=j-h； /*得到前一记录位置 */
}
R[j+h]=temp； /*插入 R[i]*/
} /*本趟排序完成 */
k++；
} while (h！ =1)； /*增量为 1排序后终止算法 */
} /*SHELLSORT*/
读者可能看出,当增量 h=1时,SHELLSORT算法与 INSERTSORT基本一致 。
对希尔排序的分析提出了许多困难的数学问题,特别是如何选择增量序列才能产生最好的排序效果,至今没有得到解决 。 希尔本为最初提出取 d1=┗ n/2┛,di+1=┗ di/2┛,dt=1,t=┗ log2n┛ 。 后来又有人提出其它选择增量序列的方法,如 di+1=┗ (di-1)/3┛,dt=1，
t=┗ log3n-1┛ ；以及 di+1=┗ (di-1)/2┛,dt=1,t=┗ log2n-1┛ 。
为什么希尔排序的时间性能优于直接插入排序呢？ 我们知道直接插入排序在文件初态为正序时所需要时间最少,实际上,当文件初基本有序时直接插入排序所需的比较和移动次数均较少 。 另一面,
当 n值较小时,n和 n2的差别也较小,即直接插入排序的最好时间复杂度 O(n)和最坏时间复杂度 O(n2)差别不大 。 在希尔排序时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,
后来增量 di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,但由于已经按 di-1作为距离排过序,使文件较近于有序状态,
所以新的国趟排序过程也较快 。 因此,希尔排序在较率上较直接接入排序有较大的改进 。
希尔排序是不稳定的。参见图 9-2的例子，该例中两个相同关键字 49
在排序前后的相对次序发生了变化。
选择排序选择排序 （ selection sort） 也是一种简单排序法 。 一个记录最多只需进行一次交换就可以直接到达它的排序位置 。
设待排序的文件为 （ R1,R2,…,Rn）,进行选择排序的基本步骤如下：
（ 1） 置 i 为 1；
（ 2） 当 i<n时,重复下列步骤；
1） 当 (Ri,…,Rn)中选出一个关键字最小的记录 Rmin,若 Rmin不是 Ri,即
Rmin≠i则交换 Ri和 Rmin的位置；否则,不进行交换 。
2） i的值加 1。
第 1遍扫描时,在 n个记录中为了选出最小关键字的记录,需要进行 n-1次比较,第 2扫描时,在余下的 n-1记录中,再选出具有最小关键字的记录需要比较 n-2次,…… 第 n-1扫描时,在最后的 2个记录中,比较 1次选出最小关键字的记录 。
堆排序堆排序 (heap sort)是在选择排序的基础上发展起来的 。 它比选择排序的效率要高 。 在堆排序中,把待排序的文件逻辑上看作是一棵顺序二叉树,并用到堆的概念 。
在介绍堆排序之前,先引入堆的概念 。
我们回忆一下，一棵有 n个结点的顺序二叉树可以用一个长度为 n的向量 (一维数组 )来表示；反过来，一个有 n个记录的顺序表示的文件，在概念上可以看作是一棵有 n
个结点 (即记录 )的顺序二叉树。例如，一个顺序表示的文件 (R1,R2,……,R9)，可以看作为图 9-4所示的顺序二叉树。
当我们把顺序表示的文件 (R1,R2,…,Rn)看作为顺序二叉树时,由顺序二叉树的性质可知：记录 Ri(1<i≤n)的双亲是记录 R[i 2]； R1的左孩子是记录 R2i(2i≤n),但若 2i>n,则 Ri的左孩子不存在；
Ri的右孩子是记录 R2i+1(2i+1≤n),但若 2i+1>n,则 Ri的右孩子不存在 。
什么是堆呢?堆是一个具有这样性质的顺序二叉树,每个非终端结点 (记录 )的关键字大于等于它的孩子结点的关键字 。 例如,图 9-5所示的顺序二叉树就是一个堆 。
显然,在一个堆中,根结点具有最大值 (指关键字,下同 ),而且堆中任何一个结点的非空左,右子树都是一个堆,它的根结点到任一叶子的每条路径上的结点都是递减有序的 。
堆排序的基本思想是：首先把待排序的顺序表示 (一维数组 )的文件 (R1,R2,…,Rn)在概念上看作一棵顺序二叉树,并将它转换成一个堆 。 这时,根结点具有最大值,删去根结点,然后将剩下的结点重新调整为一个堆 。 反复进行下去,直到只剩下一个结点为止 。
堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆 。 初始状态时,结点是随机排列的,需要经过多次调整才能把它转换成一个堆,这个堆叫做初始堆 。 建成堆之后,交换根结点和堆的最后一个结点的位置,相当于删去了根结点 。 同时,剩下的结点 (除原堆中的根结点 )又构成一棵顺序二叉树 。 这时,根结点的左,右子树显然仍都是一个堆,它们的根结点具有最大值
(除上面删去的原堆中的根结点 )。 把这样一棵左,右子树均是堆的顺序二叉树调整为新堆,是很容易实现的 。
例如,对于图 7-7所示的堆,交换根结点 63和最后的结点 30之后,便得到图 9-6(a)所示的顺序二叉树 (除 63之外 )。 现在,新的根结点是 30,其左,右子树仍然都是堆 。 下面讨论如何把这棵二叉树调整为一个新堆 。
由于堆的根结点应该是具有最大值的结点,且已知左,右子树是堆,因此,新堆的根结点应该是这棵二叉树的根结点,根结点的左孩子,根结点的右孩子 (若存在的话 )中最大的那个结点 。 于是,先找出根结点的左,右孩子,比较它们的大小 。 将其中较大的孩子再与根结点比较大小 。
如果这个孩子大于根结点,则将这个孩子上移到根结点的位置,而根结点下沉到这个孩子的位置,即交换它们的位置 。 在图 9-6(a)中,根结点 30的左,右孩子分别是 60,59,由于 60>59，
并且 60>30,于是应交换根结点 30和左孩子 60的位置 。
这时，新的根结点 60的右子树没有改变，仍然是一个堆。但是，由于结点 30下沉到左子树的根上，
使得左子树有可能不再是堆了。按照上面所用的办法，把这棵子树调整为一个堆，显然，结点 30的左、右子树原来都是堆,30的左、右子树分别是 40,45。由于 40<45，并且 45>30，于是应交换结点 30和右孩子 45的位置。
void adjust(struct node r[m+1],int m)
/* 将文件 (r[1],r[2],…,r[m])解释为一棵顺序二叉树,将其中以 r[i]为根结点的二叉树调整为一个堆,设以 r[i]为根的二叉树的左,右子树已是堆,1≤i≤1[m/2] */
{ x=r[i];j=2*i;
/*求出 r[i]的左孩子 r[2*i],即 r[j] */
while (j<=m) /*有左孩子 */
{ if ((j<m) &&(r[j].key<r[j+1].key)) /*比较左,右孩子 */
j=j+1; /*左孩子 <右孩子 */
if (x.key<r[j].key) /*比较根结点和它的大孩子 */
{ r[i]=r[j]; /*大孩子上移到它的双亲位置 */
i=j; /*今 r[j]为根结点 */
j=2*i; /*求出左孩子 */
}
else j=m+1 /*根不小于它的任一孩子时,强迫退出 while
循环 */
}
r[i]:=x; /*将存放在 x
中的根结点放到 r[i]中 */
}
快速排序快速排序 (Quick Sort)称划分交换排序。其基本思想是：在当前无序区 R[1]到 R[h]到中任取一个记录作为比较的“基准”（不妨记为 temp），
用此基准将当前无序区划分为左右两个较小的无序子区,R[1]到 R[i-1]和 R[i+1]到 R[h]，且左边的无序子区中记录的关键字均小于或等于基准 temp的关键字，右边的无序子区中记录的关键字均大于或等于基准 temp的关键字，而基准
temp则位于最终排序的位置上
R[1]到 R[i-1]中关键字 ≤temp.key=R[i+1]到 R[h]的关键字 （ 1≤i≤h）
当 R[1]到 R[I-1]和 R[I+1]到 R[h]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中记录均已排好序为止 。
要完成对当前无序区 R[1]到 R[h]的划分，具体做法是：设置两个指针
i和 j，它们的初值分别为 i=1和 j=h。不妨取基准为无序区的第 1个记录 R[i]（即 R[1]），并将它保存在变量 temp中。令 j自 h起向左扫描，直到找到第 1个关键字小于 temp.key的记录 R[j]，将 R[j]移至 i
所指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）的位置，
使关键字小于基准关键字的记录移到了基准的左边）；然后，令 i
自 i+1起向右扫描，直至找到第 1个关键字大于 temp.key的记录 R[i]，
将 R[i]移至 j指的位置上（这相当于交换了 R[j]和基准 R[i]（即 temp）
的位置，使关键字大于基准关键字的记录移到了基准的右边）；
接着，令 j自 j+1起向右扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至 i=j时,i便是基准 x的最终位置，将 x放在此位置 上就完成了一次划分。
综合上面的叙述,下面分别给出一次划分及其排序的算法 。
int partition(r,1,h) /*返回划分后被定们的基准记录的位置 */
rectype R[ ]; /*对无序区 R[1]到 R[h]做划分 */
int 1,h;
{int i,j;
rectype temp;
i=1;j=h temp=R[i]; /*初始化,temp为基准 */
Do{
While((R[j].key>=temp.key) && (i<j))
j--; /*从右向左扫描,查找第 1个关键字小于 temp.key的记录 */
if(i<j) R[i++]=R[j]; /*交换 R[i]和 R[j]*/
while((R[i].key<=temp.key) && (i<j))
i++; /*从左向左扫描,查找第 1个关键字大于
temp.key的记录 */
if(i<j) R[j--]=R[i]; /*交换 R[i]和 R[j]*/
}
quicksort(R,s1,t1) /*对 R[s1]到 R[t1]*/
rectype R[ ];
int s1,t1;
{int i;
if (s1<t1) /* 只有一个记录或无记录须排序 */
{i= partition (R,s1,t1); /*对 R[s1]到 R[t1]做划分 */
quicksort (R,s1,i-1); /*递归处理左区间 */
quicksort (R,i+1,t1); /*递归处理右区间 */
}
}
图 9-7展示了一次划分的过程及整个快速排序的过程 。 图中方括号表示无序区,方框表示基准 temp的关键字,它未参加真正的交换,只是在划分完成时才将它放入正确的位置上 。
初始关键字 [[49 ] 38 65 97 76 13 27 49`]
i j
j向左扫描 [[49] 38 65 97 76 13 27 49 `]
i j
第一次交换后 [27 38 65 97 76 13 [ ] 49`]
i j
i向右扫描 [27 38 65 97 76 13 [ ] 49 `]
i j
第二次交换后 [27 38 [ ] 97 76 13 65 49 `]
i j
j向左扫描,位置不变第三次交换后 [27 38 13 97 76 [ ] 65 49]`]
i向左扫描,位置不变,i j
第四次交换后 [27 38 13 [ ] 76 97 65 49 `]
i j
j向左扫描 [27 38 13 [49] 76 97 65 49 `]
i j
初始关键字,[49 38 65 97 76 13 27 49`]
一趟排序之后,[27 38 13] 49 [76 97 65 49`]
二趟排序之后,[13] 27 [38] 49 [49` 65] 76 [97]
三趟排序之后,13 27 38 49 49` [65] 76 97
最后的排序结果,13 27 38 79 79` 65 76 97
(b) 各趟排序之后的状态最坏情况是第次划分选取的基准都是当前无序区中关键字最小 （ 或最大 ） 的记录,划分的基准左边的无序子区为空 （ 或右边的无序子区为空 ）,而划分所得的另一个非空的无序子区中记录数目,
仅仅比划分前的无序区中记录个数减少一个 。 因此,快速排序必须做 n-1趟,每一趟中需进行 n-i次比较,故总手工艺比数次数达到最大值：
Cmax=∑(n-i)=n(n-1)/2=O(n2)
显然,如果按上面给出的划分算法,每次取当前无序区的第 1个记录为基准,那么当文件的记录已按递增序 （ 或递减序 ） 排列时,每次划分所取的基准就是当前无序区中关键字最小 （ 或最大 ） 的记录,则快速排序所需的比较次数反而最多 。
在最好情况下,每次划分所取的基准都是当前无序区的,中值,记录,划分的结果是基准的左,右两个无序子区的长度大致相等地 。
设 C（ n） 表示对长度为 n的文件进行快速排序所需的比较次数,
显然,它应该等于对长度为 n的无序区进行划分所需的比较次数 n-
1。 加上递归地对划分所得的左,右两个无序子区 （ 长度 ≤n/2） 进行快速排序所需的比较总人数。
假设文件长度 n=2k,那么总的比较次数为：
C(n) ≤n+2C(n/2)
≤n+2[n/2+2C(n/22)]=2n+4C(n/22)
≤2n+4[n/4+2C(n/23)]=3n+8C(n/23)
≤……
≤kn+2kC(n/2k)=nlog2n+nC(1)
=O(nlog2n)
注意：式中 C（ 1）为一常数,k=log2n。,
因为快速排序的记录移动次数不大于比较的次数,所以,
快速排序的最坏时间复杂度应为 O（ n2）,最好时间复杂雅兴 O(log2n)。 为了改善最坏情况下的时间性能,可采用三者取中的规则,即在每一趟划分开始前,首先比较 R[1].key,R[h].key和 R[[(1+h)/2]].key,令三者中取中值的记录和 R[1]交换之 。
可以证明：快速排序的平均时间复杂度也是 O(nlog2n)，
它是目前基于比较的内部排序方法 中速度最快的,快速排序亦因此而得名 。
快速排序需要一个栈空间来实现递归 。 若每次划分均能将文件均 匀分割 为两 部分,则栈的 最大深 度为
[log2n]+1,所需栈空间为 O（ log2n） 。 最坏情况下,递归深度为 n,所需栈空间为 O（ n)。
快速排序是不稳定的，请读者自行检验。
归并排序归并排序 (Merge Sort)是利用“归并”技术来进行排序，
所谓归并是指将若干个已排序的子文件合并成一个有序的文件。简单的归并是将两个有序的子文件合并成一个有序的文件。假设 R(low)到 R[m]和 R[m+1]到
R[high]是存储在同一个数组中且相邻的两个有序的子文件，要将它们合并为一个有序文件 R1[low]到 R1[high]，
只要设置三个指示器 i,j和 k，其初值分别是这三个记录区的起始位置。合并时依次比较 R[i]和 R[j]的关键字，
取关键字较小的记录复制到 R1[k]中，然后，将指向被复制记录的指示器加 1和指向复制位置的指示器 K加 1，
重复这一过程，直至全部记录被复制到 R1[low]到
R1[high]中为止。
基数排序前介绍的排序方法都是根据关键字值的大小来进行排序的 。 本节介绍的方法是按组成关键字的各个位的值来实现的排序的,这种方法称为基数排序 （ radix sort） 。 采用基数排序法需要使用一批桶 （ 或箱子 ）,故这种方法又称为桶排序列 。 下面以十进制数为例来说明基数排充的过程 。
假定待排序文件中所有记录的关键字为不超过 d位的非负整数,从最高位到最低位
（ 个位 ） 的编号依次为 1,2,…,d。 设置 10个队列 （ 即上面所说的桶 ）,它们的编号分别为 0,1,2,…,9。 当第一遍扫描文字时,将记录按关键字的个位 （ 即第 d位）数分别放到相应的队列中：个位数为 0的关键字，其记录依次放入 0号队列中 i
个位数为 1的关键字，其记录放入 1号队列中 … ；个位数为 9的关键字，其记录放入
9号队列中。这一过程叫做按个位数分配。现在把这 10个队列中的记录，按 0号,1
号,9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。
这是第 1遍。第 2遍排序使用同样的办法，将第 1遍排序后的记录按其关键字的十位数（第 d— 1位）分配到相应的队列中，再把队列中的记录收集和排列起来。继续进行下去。第 d遍排序时，按第 d— 1遍排序后记录的关键字的最高位（第 1位）进行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以
10为基的关键字的基数排序法。
关键字
1 02
2 77
3 70
4 54
5 64
6 21
7 55
8 11
9 38
1 0 21
初始状态
70
21,1 1,2 1
02
5 4,6 4
55
77
38
70
21
11
21
02
54
64
55
77
38
02
11
2 1,2 1
38
54,55
64
7 0,7 7
02
11
21
21
38
54
55
64
70
77
10 个队列 关键字第一遍，按个位数分配收集后 收集后第二遍，按十位数分配例如,给出关键字序列 （ 02,77,70,54,64,21,55,11,38,21）,其中关键字 02用 1个 0在 2的前面补足到 2位,余关键字均为 2位的正整数 。 进行基数排序的过程如图 9-9所示 。
在这个例子中,文件和所有的队列都表示成向量 （ 一维数组 ） 。 显然,关键字的某一位有可能均为同一个数字 （ 例如,个数都为 0）,这时所有的记录都同时装入同一个队列中 （ 例如,同时装入 0号队列中 ） 。 因此,如果每个队列的大小和文件大小相同,则需要一个 10倍于文件大小的附加空间 。 此外,排序时需要进行反复的分配和收集记录 。 所以,采用顺序表示是不方便的 。
基数排序所需的计算时间不仅与文件的大小 n有关，而且还与关键字的位数、
关键字的基有关。设关键字的基为 r（十进制数的基为 10，二进制数的基为 2），为建立 r个空队列所需的时间为 O（ r）。把 n个记录分放到各个队列中并重新收集起来所需的时间为 O（ n），因此一遍排序所需的时间为
O（ n+r）。若每个关键字有 d位，则总共要进行 d遍排，所以基数排序的时间复杂度为 O（ d（ n+r））。由于关键字的位数 d直接与基数 r以及最大关键字的值有关，因此不同的 r和关键字将需要不同的时间。
在已介绍的上述各种内部排序方法中，就所需要的计算时间来看，快速排序、归并排序、堆排序是很好的方法。但是，归并排序需要大小为
n的辅助空间，快速排序需要一个栈空。除了快速排序、堆排序、选择排序不稳定外，基它排序方法都是稳定的。评价一个排序算法性能好坏的主要标准是它所需的计算时间和存储空间。影响计算时间的两个景要因素是比较关键字的次数和记录的移动次数。在实际应用中，
究竟应该选用何种排序方法，取决于具体的应用和机器条件。
外部排序外部排序基本上由两个相对独立的阶段组成 。 首先,按可用内存大小,将外存上含 n个记录的文件分成若干长度为 l的子文件或段
（ segment）,依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写入外存,通常称这些有序子文件为归并段或顺串 （ run） ；然后,对这些归并段进行逐趟归并,使归并段 （ 有序的子文件 ） 逐渐由小至大,直至得到整个有序文件为止 。 显然,第一阶段的工作是上一章已经讨论过的内容 。 本章主要讨论第二阶段即归并的过程 。 先从一个具体例子来看外排中的归并是如何进行的？
假设有一个含 10000个记录的文件，首先通过 10次内部排序得到 10个初始归并段 R1~R10，其中每一段都含 1000个记录。然后对它们作如下图所示的两两归并，直至得到一个有序文件为止。
将两个有序段归并成一个有序段的过程,若在内存进行,则很简单,
上一章中的 merge过程便可实现此归并 。 但是,在外部排序中实现两两归并时,不仅要调用 merge过程,而且要进行外存的读 /写,
这是由于我们不可能将两个有序段及归并结果段同时存放在内存中的缘故 。 在 11.1节中已经提到,对外存上信息的读 /写是以,物理块,为单位的 。 假设在上例中每个物理块可以容纳 200个记录,
则每一趟归并需进行 50次,读,和 50次,写,,四趟归并加上内部排序时所需进行的读 /写使得在外排中总共需进行 500次的读 /写 。
一般情况下,外部排序所需总的时间 =
内部排序 （ 产生初始归并段 ） 所需的时间 m*tIS
+外部信息读写的时间 d*tIO （ 11-1）
+内部归并所需的时间 s*utmg
其中,tIS是为得到一个初始归并段进行内部排序所需时间的均值；
tIO是进行一次外存读 /写时间的均值； utmg是对 u个记录进行内部归并所需时间； m为经过内部排序之后得到的初始归并段的个数；
s为归并的趟数； d为总的读 /写次数。
其中 tIO取决于所用的外部设备,显然,tIO较 tmg要大得多 。 因此,提高外排的效率应主要着眼于减少外存信息读写的次数 d。
下面来分析 d和,归并过程,的关系 。 若对上例中所得的 10个初始归并段进行 5-路平衡归并 （ 即每一趟将 5个或 5个以下的有序子文件归并成一个有序子文件 ）,则从下图可见,仅需进行二趟归并,外排时总的读 /写次数便减至 2*100+100=300,比 2-路归并减少了 200次的读 /写 。
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
└──┴──┼──┴───┘ └──┴──┼──┴───┘
R1ˊ R2ˊ
└───────┬──────┘
有序文件可见,对同一文件而言,进行外排时所需读 /写外存的次数和归并的趟数 s成正比 。 而在一般情况下,对 m个初始归并段进行 k-路平衡归并时,归并的趟数
s = [ logkm ]
可见，若增加 k或减少 m便能减少 s。
各种排序方法的比较迄今为止,已有的排序方法远远不止本章讨论的这些方法,人们之所以热衷于研究多种排序方法,不仅是由于排序在计算机中所处的重要地位,而且还因为不同的方法各有其优缺点,可适用于不同的场合 。 选取排序方法时需要考虑的因素有：
待排序的记录数目 n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件,辅助空间的大小等 。
依据这些因素,可得出如下几点结论：
（ 1） 若 n较小 （ 譬如 n50),可采用直接插入排序或直接选 。 由于直接插入排序所需记录移动操作较直接选择排序多,因此若记录本身信息量较大时,则选用直接选择排序为宜 。
（ 2） 若文件的初始状态已是按关键字基本有序,则选用直接插入排序泡排序为宜 。
（ 3） 若 N较大,则应采用时间复杂度为的排序方法：快速排序 \堆排序或归并排序,快速排序是目前基于内部排序的中被认为是最好的方法,档待排序的关键字是随机人布时,快速排序的平均时间最少,但堆排序所需的辅助窨少于快速排序,并且不会出现序可能出现的最坏情况,这两种排序方法都是不稳定的,若要求排序稳定则可选用归并排序 。 但本文章结合介绍的单个记录起进行两两归并排算法并不值得提倡,通常可以将它和直接排序结合在一起用 。 先利用直接插入排序求得的子文件,然后,再两 两 归并之 。 因为直接插入排序是稳定的,所以,改进后的归并排序是稳定的 。
（ 4） 在基于比较的排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此,可以利用一棵二叉树来描述比较判定过程,由此可以证明 ;当文件的 N个关键字分布时,任何借助于比较的排序算法,至少要的时间,由于箱排序和基数排序只需一步就会引起 M种可能的转移,即把一个记录半装入 M个箱子之一,因此,在一般情况下,箱乔序和排序可能在时间内完成对 N个记录的 。 但踞的是,箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字,当关键字的取值范围属于某个无穷集合时,
无法使用箱排序和排序,这时只有借助于比较方法来排序 。 由此可知,若 N较大,记录的关键字倍数较少时且可以分解时采用排序较好 。
（ 5） 前面讨论的排序算法,除排序外,都是在一维数组上实现的,当记录本身信息量较大时,为了避免浪费大量时间移动记录,可以用链表作为存储结构,如插入排序和归并排序都易于在链表上实现,并分别称之为表和归并表,但有的方法,如快速排序和堆排序,
在链表上难于实现,在这种情况下,可以提取关键字建立索引表,然后,对索引表进行排序 。 然而更为简单的方法是 ;引入一个整形向量作为辅助表,排序前,若排序算法中要求交换,则只需交换 R[I ]和 R[j]即可,排序结束后,向量就指示了记录之间的顺序关系：
无论是用链表还是用辅助窨来实现排序,都有可能要求最终结果是,
若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种 重排时间是 o(n)。
本章小结排序（ sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。本章主要介绍了排序的概念及其基本思想，排序过程和实现算法，简述了各种算法的时间复杂度和空间复杂度。一个好的排序算法所需要的比较次数和存储空间都应该较少，
但从本章讨论的各种排序算法中可以看到，不存在
“十全十美”的排序算法，各种方法各有优缺点，可适用于不同的场合。由于排序运算在计算机应用问题中经常碰到，读者应重点理解各种排序算法的基本思想，熟悉过程及实现算法，以及对算法的分析方法，
从而面对实际问题时能选择合适的算法。
