第11章内排序11.1排序的基本概念所谓排序，就是要整理表中的记录，使之按关键字递增（或递减）有序排列。其确切定义如下：输入：n个记录,Ro,R1,,Rn-1,其相应的关键字分别为ko,k1,"",kn-1。输出：Rio,Ril,,Rin-1,使得kio≤kil≤≤kin-1(或kio≥kil≥.≥kin-1)。当待排序记录的关键字均不相同时,排序的结果是惟一的，否则排序的结果不一定惟一。如果待排序的表中存在有多个关键字相同的记录.经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。在排序过程中，若整个表都是放在内存中处理排序时不涉及数据的内、外存交换，则称之为内排序：反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。内排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区待排序的顺序表类型的类型定义如下：/*定义关键字类型*/typedef int Key Type;/*记录类型*typedef struct1/*关键字项*/KeyType key,InfoType data,/*其他数据项,类型为InfoType*/↓RecType,/*排序的记录类型定义*/11.2插入排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。两种插入排序方法：(1)直接插入排序(2)希尔排序。11.2.1直接插入排序假设待排序的记录存放在数组R[0.n-1]中,排序过程的某一中间时刻,R被划分成两个子区间R[0.i-1]和R[i.n-1],其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第1个记录R[i插入到有序区R[0..i-1]中适当的位置上，使R[0..i变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。在有序区中插入R[i的过程voidInsertSort(RecTypeR[],intn)/*对R[0..n-1]按递增有序进行直接插入排序*/1int i,j;RecType temp;for (i=1;i<n;i++) temp=R[i];
第 11 章 内 排 序 11.1 排序的基本概念 所谓排序,就是要整理表中的记录,使之按关键字递增(或递减)有序排列。其确切定义如 下： 输入：n 个记录,R0,R1,.,Rn-1,其相应的关键字分别为 k0,k1,.,kn-1。 输出：Ri0,Ri1,.,Rin-1,使得 ki0≤ki1≤.≤kin-1 (或 ki0≥ki1≥.≥kin-1)。 当待排序记录的关键字均不相同时,排序的结果是惟一的,否则排序的结果不一定惟一。如果 待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的 相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同关键字的记录之间的相对 次序发生变化,则称这种排序方法是不稳定的。 在排序过程中,若整个表都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之 为内排序；反之,若排序过程中要进行数据的内、外存交换,则称之为外排序。 内排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区 待排序的顺序表类型的类型定义如下： typedef int KeyType; /*定义关键字类型*/ typedef struct /*记录类型*/ { KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为 InfoType*/ } RecType; /*排序的记录类型定义*/ 11.2 插入排序 插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好 序的子表中的适当位置,直到全部记录插入完成为止。 两种插入排序方法： (1)直接插入排序 (2)希尔排序。 11.2.1 直接插入排序 假设待排序的记录存放在数组 R[0.n-1]中,排序过程的某一中间时刻,R 被划分成两个子 区间 R[0.i-1]和 R[i.n-1],其中：前一个子区间是已排好序的有序区,后一个子区间则是当前未 排序的部分,不妨称其为无序区。 直接插入排序的基本操作是将当前无序区的第 1 个记录 R[i]插入到有序区 R[0.i-1]中 适当的位置上,使 R[0.i]变为新的有序区。这种方法通常称为增量法,因为它每次使有序区增 加 1 个记录。 在有序区中插入 R[i]的过程 void InsertSort(RecType R[],int n) /*对 R[0.n-1]按递增有序进行直接插入排序*/ { int i,j;RecType temp; for (i=1;i<n;i++) { temp=R[i];
j=i-1；/*从右向左在有序区R[0..i-1]找R[i]的插入位置*while (i>=0 && temp.key<R[i].key)R[i+1]=R[i];/*将关键字大于R[i].key的记录后移*/j,3/*在j+1处插入R[]*/R[j+1]=temp,111.2.2希尔排序希尔排序也是一种插入排序方法实际上是一种分组插入方法。其基本思想是：先取定一个小于n的整数d1作为第一个增量把表的全部记录分成dl个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<<d2<d1),即所有记录放在同一组中进行直接插入排序为止。将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。11.3交换排序交换排序的基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。两种交换排序：(1)冒泡排序(2)快速排序11.3.1冒泡排序冒泡排序的基本思想是：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。比较相邻记录，将关键字最大的记录交换到n-i+1的位置上voidBubbleSort(RecTypeR,intn)intij;RecTypetemp;tfor (i=0;i<n-1;i++)for(i=n-1j>ij--）/*比较找本趟最小关键字的记录*/if (R[i].key<R[j-1].key) temp=R[i];/*R[i与R[i-1]进行交换*R[i]=R[j-1];R[i-1]=temp;31311.3.2快速排序快速排序是由冒泡排序改进而得的
j=i-1; /*从右向左在有序区 R[0.i-1]找 R[i]的插入位置*/ while (j>=0 && temp.key<R[j].key) { R[j+1]=R[j]; /*将关键字大于 R[i].key 的记录后移*/ j-; } R[j+1]=temp; /*在 j+1 处插入 R[i]*/ } } 11.2.2 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。 其基本思想是：先取定一个小于 n 的整数 d1 作为第一个增量,把表的全部记录分成 d1 个组,所有距离为 d1 的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第 二个增量 d2(＜d1),重复上述的分组和排序,直至所取的增量 dt=1(dt<dt-1<.<d2<d1),即所有 记录放在同一组中进行直接插入排序为止。 将记录序列分成若干子序列，分别对每个子序列进行插入排序。 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。 11.3 交换排序 交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行 交换,直到没有反序的记录为止。 两种交换排序: (1)冒泡排序 (2)快速排序 11.3.1 冒泡排序 冒泡排序的基本思想是： 通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一 般逐渐往上“漂浮”直至“水面”。 整个算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记 录换至关键字较大的记录之上,使得经过一趟冒泡排序后,关键字最小的记录到达最上端,接 着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上。依次类推,一直到所有 记录都有序为止。 比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上 void BubbleSort(RecType R[],int n) { int i,j;RecType temp; for (i=0;i<n-1;i++) { for (j=n-1;j>i;j-) /*比较找本趟最小关键字的记录*/ if (R[j].key<R[j-1].key) { temp=R[j]; /*R[j]与 R[j-1]进行交换*/ R[j]=R[j-1]; R[j-1]=temp; } } } 11.3.2 快速排序 快速排序是由冒泡排序改进而得的
基本思想是：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入适当位置后数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分所有比它大的记录放置在后一部分，并把该记录排在这两部分的中间称为该记录归位),这个过程称作一趟快速排序。voidQuickSort(RecTypeR[l,ints,intt)/*对R[s]至R[]的元素进行快速排序*RecType temp,1int i-s,j-t;if(s<t)/*区间内至少存在一个元素的情况*//*用区间的第1个记录作为基准*/temp=R[s];while (il=i)/*从两端交替向中间扫描，直至i=j为止*/while (>i&& R[i].key>temp.key)j--,if(iki)/*表示找到这样的R[i],R[]、R[i]交换*/R[i]=R[j]; i++;while (i<j&&R[i].key<temp.key)i++;if(iki)/*表示找到这样的R[il,R[i]、R[il交换*1R[i]=R[i]; j--; 享R[i]=temp;/*对左区间递归排序*QuickSort(R,s,i-1)QuickSort(R,i+1,t);/*对右区间递归排序*/3划分11.4选择排序选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。两种选择排序方法：(1)直接选择排序(或称简单选择排序)(2)堆排序11.4.1直接选择排序直接选择排序的基本思想是：第i趟排序开始时,当前有序区和无序区分别为R[0.i-1]和R[i.n-1](O≤i<n-1),该趟排序则是从当前无序区中选出关键字最小的记录R[K],将它与无序区的第1个记录Ri交换使R[O.i和Ri+1.n-1分别变为新的有序区和新的无序区。11.4.2堆排序堆排序是一树形选择排序,它的特点是,在排序过程中,将R[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。堆的定义是：n个关键字序列K1,K2,Kn称为堆，当且仅当该序列满足如下性质（简称为堆性质)：(1)Ki≤K2i且Ki≤K2i+1或（2)Ki≥K2i且Ki≥K2i+1(1≤i≤n/2）满足第(1)种情况的堆称为小根堆，满足第(2)种情况的堆称为大根堆。voidsift(RecTypeR,intlow,inthigh)/*调整堆的算法*int i=low,j=2*i;/*R]是R[i]的左孩子*L
基本思想是：在待排序的 n 个记录中任取一个记录(通常取第一个记录),把该记录放入适 当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前 一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归 位),这个过程称作一趟快速排序。 void QuickSort(RecType R[],int s,int t) /*对 R[s]至 R[t]的元素进行快速排序*/ { int i=s,j=t; RecType temp; if (s<t) /*区间内至少存在一个元素的情况*/ { temp=R[s]; /*用区间的第 1 个记录作为基准*/ while (i!=j) /*从两端交替向中间扫描,直至 i=j 为止*/ { while (j>i && R[j].key>temp.key) j-; if (i<j) /*表示找到这样的 R[j],R[i]、R[j]交换*/ { R[i]=R[j]; i++; } while (i<j && R[i].key<temp.key) i++; if (i<j) /*表示找到这样的 R[i],R[i]、R[j]交换*/ { R[j]=R[i]; j-; } } R[i]=temp; QuickSort(R,s,i-1); /*对左区间递归排序*/ QuickSort(R,i+1,t); /*对右区间递归排序*/ } } 划分 11.4 选择排序 选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排 好序的子表的最后,直到全部记录排序完毕。 两种选择排序方法： (1)直接选择排序(或称简单选择排序) (2)堆排序 11.4.1 直接选择排序 直接选择排序的基本思想是：第i 趟排序开始时,当前有序区和无序区分别为 R[0.i-1] 和 R[i.n-1](0≤i＜n-1),该趟排序则是从当前无序区中选出关键字最小的记录 R[k],将它与无 序区的第 1 个记录 R[i]交换,使 R[0.i]和 R[i+1.n-1]分别变为新的有序区和新的无序区。 11.4.2 堆排序 堆排序是一树形选择排序,它的特点是,在排序过程中,将 R[1.n]看成是一棵完全二 叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区 中选择关键字最大(或最小)的记录。 堆的定义是：n 个关键字序列 K1,K2,.,Kn 称为堆,当且仅当该序列满足如下性质(简 称为堆性质)： (1)Ki≤K2i 且 Ki≤K2i+1 或 (2)Ki≥K2i 且 Ki≥K2i+1(1≤i≤ n/2 ) 满足第(1)种情况的堆称为小根堆,满足第(2)种情况的堆称为大根堆。 void sift(RecType R[],int low,int high) /*调整堆的算法*/ { int i=low,j=2*i; /*R[j]是 R[i]的左孩子*/
RecType temp=R[i];while (i<=high)if(j<high && R[i].key<R[i+1].key) j++;福if(temp.key<R[i].key).R[i]=R[i];/*将R[i]调整到双亲结点位置上*/ij;/*修改i和i值，以便继续向下筛选*/j=2*i,3else break,*筛选结束*/1R[i]=temp,/*被筛选结点的值放入最终位置*/1有了调整堆的函数，利用该函数，将已有堆中的根与最后一个叶子交换进一步恢复堆,直到一棵树只剩一个根为止。实现堆排序的算法如下：void HeapSort(RecType R[l,int n)inti,RecTypetemp;/*循环建立初始堆*/for (i=n/2;i>=1;i--)sift(R,i,n);for (i=n;i>=2;i--):/*进行n-1次循环，完成推排序*/temp=R[1];/*将第一个元素同当前区间内R[1]对换*/R[1]=R[i];R[i]=temp;/*筛选R[1]结点,得到i-1个结点的堆*/sift(R, 1,i-1),3111.5归并排序归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列R[1.n]有序子序列R[1..m]有序子序列R[m+1..n]这个操作对顺序表而言，是轻而易举的。void Merge(RecType R[l,int low,int mid,int high)RecType *Rl;1int i=low,j=mid+1,k=0,/*k是R1的下标，i、i分别为第1、2段的下标*/R1=(RecType *)malloc(high-low+1)*sizeof(RecType):while (i<=mid&&j<=high)if(R[].key<=R[i].key）/*将第1段中的记录放入R1中*(Ri[k]=R[i]; i++;k++,?else/*将第2段中的记录放入R1中*/（Ri[k]=R[i];j++;k++;}Merge()实现了一次归并：
RecType temp=R[i]; while (j<=high) { if (j<high && R[j].key<R[j+1].key) j++; if (temp.key<R[j].key) { R[i]=R[j]; /*将 R[j]调整到双亲结点位置上*/ i=j; /*修改 i 和 j 值,以便继续向下筛选*/ j=2*i; } else break; /*筛选结束*/ } R[i]=temp; /*被筛选结点的值放入最终位置*/ } 有了调整堆的函数,利用该函数,将已有堆中的根与最后一个叶子交换,进一步恢复堆,直到一 棵树只剩一个根为止。实现堆排序的算法如下： void HeapSort(RecType R[],int n) { int i; RecType temp; for (i=n/2;i>=1;i-) /*循环建立初始堆*/ sift(R,i,n); for (i=n;i>=2;i-) /*进行 n-1 次循环,完成推排序*/ { temp=R[1]; /*将第一个元素同当前区间内 R[1]对换*/ R[1]=R[i];R[i]=temp; sift(R,1,i-1); /*筛选 R[1]结点,得到 i-1 个结点的堆*/ } } 11.5 归并排序 归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并 是直接将两个有序的子表合并成一个有序的表。 在内部排序中，通常采用的是 2-路归并排序。即：将两个位置相邻的记录有序子序列 归并为一个记录的有序序列。 有 序 序 列 R[l.n] 有序子序列 R[l.m] 有序子序列 R[m+1.n] 这个操作对顺序表而言，是轻而易举的。 void Merge(RecType R[],int low,int mid,int high) { RecType *R1; int i=low,j=mid+1,k=0; /*k 是 R1 的下标,i、j 分别为第 1、2 段的下标*/ R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); while (i<=mid && j<=high) if (R[i].key<=R[j].key) /*将第 1 段中的记录放入 R1 中*/ { R1[k]=R[i]; i++;k++; } else /*将第 2 段中的记录放入 R1 中*/ { R1[k]=R[j]; j++;k++; } Merge()实现了一次归并 :
/*将第1段余下部分复制到R1*/while (i<=mid)RI[k]=R[i];i++;k++;]while (j<=high)/*将第2段余下部分复制到R1*RI[k]=R[i];j++;k++;for(k=0,i=low,i<=high;k++,i++)/*将R1复制回R中*/R[i]=R1[k];子void MergePass(RecType R[],int length,int n)inti.1for（i=0;i+2*length-1<n;i=i+2*length）/*归并length长的两相邻子表*/Merge(R,i,i+length-1,i+2*length-1),if(i+length-1<n)/*余下两个子表，后者长度小于length*/Merge(R,i,i+length-1,n-1);/*归并这两个子表*1MergePass(实现了一趟归并二路归并排序算法如下：void MergeSort(RecType R[l,int n)/*自底向上的二路归并算法*/int length,for (length=1;length<n;length=2*length)MergePass(R,length,n);3例11.7设待排序的表有8个记录,其关键字分别为18,2,20,34,12,32,6,16。说明采用归并排序方法进行排序的过程。容易看出，对n个记录进行归并排序的时间复杂度为O(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行log2n趟。11.6基数排序前面所讨论的排序算法均是基于关键字之间的比较来实现的，而基数排序是通过“分配”和“收集”过程来实现排序，是一种借助于多关键字排序的思想对单关键字排序的方法。一般地,记录R[i]的关键字R[i].key是由d位数字组成,即kd-1kd-2k0,每一个数字表示关键字的一位,其中kd-1为最高位,ko是最低位,每一位的值都在0≤ki<r范围内,其中，r称为基数。以r为基数的最低位优先排序的过程是：假设线性表由结点序列ao.al..an-I构成每个结点aj的关键字由d元组(k,k,k,k)组成,其中0≤k≤r-1(0≤j<n,0≤i≤d-1)。在排序过程中,使用r个队列Q0,Q1",Qr-1。排序过程如下：对i=0,1,"d-1,依次做一次“分配”和“收集”（其实就是一次稳定的排序过程)。分配：开始时,把Q0,Q1,Qr-1各个队列置成空队列,然后依次考察线性表中的每一个结点aj(j=0,1,,n-1),如果aj的关键字k=k,就把aj放进Qk队列中。收集：把Q0,Q1,,Qr-1各个队列中的结点依次首尾相接,得到新的结点序列,从而组成新的线性表。#define MAXE20/*线性表中最多元素个数*/#define MAXR 10/*基数的最大取值*/
while (i<=mid) /*将第 1 段余下部分复制到 R1*/ { R1[k]=R[i]; i++;k++; } while (j<=high) /*将第 2 段余下部分复制到 R1*/ { R1[k]=R[j]; j++;k++; } for (k=0,i=low;i<=high;k++,i++) /*将 R1 复制回 R 中*/ R[i]=R1[k]; } void MergePass(RecType R[],int length,int n) { int i; for (i=0;i+2*length-1<n;i=i+2*length) /*归并 length 长的两相邻子表*/ Merge(R,i,i+length-1,i+2*length-1); if (i+length-1<n) /*余下两个子表,后者长度小于 length*/ Merge(R,i,i+length-1,n-1); /*归并这两个子表*/ } MergePass()实现了一趟归并 二路归并排序算法如下： void MergeSort(RecType R[],int n) /*自底向上的二路归并算法*/ { int length; for (length=1;length<n;length=2*length) MergePass(R,length,n); } 例 11.7 设待排序的表有 8 个记录,其关键字分别为{18,2,20,34,12,32,6,16}。说明采用归并排 序方法进行排序的过程。 容易看出，对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。 11.6 基数排序 前面所讨论的排序算法均是基于关键字之间的比较来实现的,而基数排序是通过“分 配”和“收集”过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。 一般地,记录 R[i]的关键字 R[i].key 是由 d 位数字组成,即 kd-1kd-2.k0,每一个数字表示关键 字的一位,其中kd-1为最高位,k0是最低位,每一位的值都在0≤ki＜r 范围内,其中,r 称为基数。 以 r 为基数的最低位优先排序的过程是：假设线性表由结点序列 a0,a1,.,an-l 构成,每个结点 aj 的关键字由 d 元组(k,k.,k,k)组成,其中 0≤k≤r-1(0≤j＜n,0≤i≤d-1)。在排序过程中,使用 r 个队列 Q0,Q1,.,Qr-1。排序过程如下： 对 i=0,1,.,d-1,依次做一次“分配”和“收集”(其实就是一次稳定的排序过程)。 分配：开始时,把 Q0,Q1,.,Qr-1 各个队列置成空队列,然后依次考察线性表中的每一个 结点 aj(j=0,1,.,n-1),如果 aj 的关键字 k=k,就把 aj 放进 Qk 队列中。 收集：把 Q0,Q1,.,Qr-1 各个队列中的结点依次首尾相接,得到新的结点序列,从而组成 新的线性表。 #define MAXE 20 /*线性表中最多元素个数*/ #define MAXR 10 /*基数的最大取值*/