数据结构简明教程（第3版）课件 第9章 排序(上)（下）

第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7外排序第9章

排序1/86所谓排序，是要整理表中的元素，使之按关键字递增（递减）有序排列。其确切定义如下：

输入：n个元素，R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。

输出：Ri,0,Ri,1,…,Ri,n-1,使得ki,0≤ki,1≤…≤ki,n-1(或ki,0≥ki,1≥…≥ki,n-1)。本章仅考虑递增排序9.1排序的基本概念1.什么是排序9.1排序的基本概念2/86在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序。若排序过程中要进行数据的内、外存交换，则称之为外排序。2.内排序和外排序9.1排序的基本概念3/863.内排序的分类根据内排序算法是否基于关键字的比较，将内排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法。而基数排序是不基于比较的排序算法。9.1排序的基本概念4/864.基于比较的排序算法的性能基于比较的排序算法中，主要进行以下两种基本操作：这类排序算法的性能由算法的时间和空间确定的，而时间是由比较和移动的次数之和确定的，两个元素的一次交换一般需要3次移动。比较：关键字之间的比较移动：元素从一个位置移动到另一个位置9.1排序的基本概念5/86若待排序元素的关键字顺序正好和要排序顺序相同，称此表中元素为正序。若待排序元素的关键字顺序正好和要排序顺序相反，称此表中元素为反序。基于比较的排序算法中有些算法是与初始序列的正序或反序相关，有些算法与初始序列的正序和反序无关。9.1排序的基本概念6/86当待排序元素的关键字均不相同时，排序的结果是唯一，否则排序的结果不一定唯一。

如果待排序的表中，存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，称这种排序方法是稳定的；反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。5.算法的稳定性9.1排序的基本概念7/86在本章中，以顺序表作为排序数据的存储结构（除基数排序采用单链表和外排序之外）。为简单起见，假设关键字类型为int类型。待排序的顺序表中元素类型定义如下：typedefintKeyType;typedefstruct{KeyTypekey; //存放关键字,KeyType为关键字类型

ElemTypedata; //其他数据,ElemType为其他数据的类型}SqType;6.排序数据的组织9.1排序的基本概念8/869.2插入排序插入排序基本思路：每一趟将一个待排序的元素，按其关键字值的大小插入到已经排序的部分文件中适当位置上，直到全部插入完成。主要的插入排序算法：直接插入排序、折半插入排序和希尔排序。9.2插入排序9/869.2.1直接插入排序直接插入排序是一种最简单的排序方法，其过程是依次将每个元素插入到一个有序的序列中去。

有序区R[0]

……

R[i-1]无序区R[i]

……

R[n-1]有序区R[0]……

R[i-1]

R[i]无序区R[i+1]

……

R[n-1]一趟排序初始时，有序区只有一个元素R[0]i＝1~n-1，共经过n-1趟排序9.2插入排序10/86

【例9.1】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用直接插入排序法进行排序的过程。初始序列75876892886177968072i=175876892886177968072i=268758792886177968072i=368758792886177968072i=468758788926177968072i=561687587889277968072i=661687577878892968072i=761687577878892968072i=861687577808788929672i=961687275778087889296最终结果616872757780878892969.2插入排序i=1的行表示i=1这一趟的排序结果11/86以i=6即插入77为例说明一趟的过程：616875878892770123456有序区tmp…i=5的排序结果：i=6的排序结果12/86直接插入排序算法如下：voidInsertSort(SqTypeR[],intn) {inti,j;SqTypetmp;

for(i=1;i<n;i++)

//从第二个元素即R[1]开始的

{if(R[i-1].key>R[i].key)

{tmp=R[i];

//取出无序区的第一个元素R[i]

j=i-1; //在R[0..i-1]中找R[i]的插入位置

do

{R[j+1]=R[j]; //将关键字大于tmp.key的元素后移

j--; //继续向前比较

}while(j>=0&&R[j].key>tmp.key);

R[j+1]=tmp;

//在j+1处插入R[i]

}

}}9.2插入排序13/86直接插入排序算法分析：最好的情况（关键字在元素序列中顺序有序）：“比较”的次数：0“移动”的次数：最坏的情况（关键字在元素序列中逆序有序）：“比较”的次数：“移动”的次数：总的平均比较和移动次数约为9.2插入排序14/86归纳起来，直接插入排序算法的性能如表9.1所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n)O(n2)O(n2)O(1)稳定9.2插入排序15/869.2.2折半插入排序利用有序区的有序性。可以采用折半查找方法先在R[0..i-1]中找到插入位置，再通过移动元素进行插入。这样的插入排序称为折半插入排序或二分插入排序。9.2插入排序16/86折半插入排序的算法如下：voidBinInsertSort(SqTypeR[],intn){inti,j,low,high,mid;SqTypetmp;

for(i=1;i<n;i++)

{if(R[i-1].key>R[i].key)

{tmp=R[i]; //将R[i]保存到tmp中

low=0;high=i-1;

while(low<=high)

//在R[low..high]中折半查找

{mid=(low+high)/2;//取中间位置

if(tmp.key<R[mid].key)

high=mid-1;

//插入点在左半区

else

low=mid+1;

//插入点在右半区

}

for(j=i-1;j>=high+1;j--) //元素后移

R[j+1]=R[j];

R[high+1]=tmp;

//插入原来的R[i]

}

}}9.2插入排序17/86折半插入排序的元素移动次数与直接插入排序相同，不同的仅是变分散移动为集中移动。在R[0..i-1]中查找插入R[i]的位置，折半查找的平均关键字比较次数为log2(i+1)，平均移动元素的次数为i/2+2，所以平均时间复杂度为：就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。9.2插入排序18/86希尔排序基本思路：先取定一个小于n的整数d1作为第一个增量，把表的全部元素分成d1个组，所有距离为d1的倍数的元素放在同一个组中，在各组内进行直接插入排序。然后取第二个增量d2（＜d1），重复上述的分组和排序，直至所取的增量dt=1（dt<dt-1<…<d2<d1），即所有元素放在同一组中进行直接插入排序为止。9.2.3希尔排序9.2插入排序19/86将元素序列分成若干子序列，分别对每个子序列进行插入排序。

其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n

个元素分成d

个子序列：

{R[0]，R[d]，R[2d]，…，

R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}

…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}9.2插入排序20/86例如：9876543210初始序列8765943210d=5直接插入排序4321098765d=d/2=243210987650123456789直接插入排序d=d/2=10123456789直接插入排序0123456789注意：对于d=1的一趟，排序前的数据已将近正序！9.2插入排序21/86取d1=n/2，di+1=

di/2

时的希尔排序的算法如下：voidShellSort(SqTypeR[],intn) {inti,j,d;

SqTypetmp;

d=n/2;

//增量置初值

while(d>0)

{for(i=d;i<n;i++)

{tmp=R[i]; //对所有相隔d位置的元素组采用直接插入排序

j=i-d;

while(j>=0&&tmp.key<R[j].key){R[j+d]=R[j];j=j-d;

}

R[j+d]=tmp;

}

d=d/2;

//减小增量

}}9.2插入排序22/86希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？例如：有10个元素要排序。希尔排序直接插入排序大约时间=102=100d=5：分为5组，时间约为5*22＝20d=2：分为2组，时间约为2*52＝50d=1：分为1组，几乎有序，时间约为10＋＋＝809.2插入排序23/86归纳起来，希尔排序算法的性能如表9.2所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况－O(n2)O(n1.5)O(1)不稳定9.2插入排序24/869.3交换排序交换排序基本思路：两两比较待排序元素的关键字，并交换不满足次序要求的那些偶对，直到全部满足为止。主要的交换排序算法：冒泡排序和快速排序。9.3交换排序25/86有序区R[0]┇R[i-1]无序区R[i]R[i+1]┇R[n-1]将无序区中最小元素放在R[i]有序区R[0]┇R[i-1]R[i]无序区R[i+1]┇R[n-1]一趟排序初始有序区为空。i＝0~n-2，共n-1趟使整个数据有序。R[i]有序区总是全局有序的9.3.1冒泡排序9.3交换排序26/86R[j]和R[j-1]反序

交换。若某一趟比较时不出现任何元素交换，说明所有元素已排好序了，就可以结束本算法。9.3交换排序27/86

【例9.3】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用冒泡排序法进行排序的过程。初始序列75876892886177968072i=0[61]758768928872779680i=161[68]7587729288778096i=26168[72]75877792888096i=3616872[75]778780928896i=461687275[77]8087889296i=56168727577[80]87889296最后结果616872757780878892969.3交换排序28/86冒泡排序算法如下：voidBubbleSort(SqTypeR[],intn){

inti,j,exchange;

SqTypetmp;

for(i=0;i<n-1;i++)

{exchange=0;

//本趟排序前置exchange为0

for(j=n-1;j>i;j--) //比较,找出最小关键字的元素

{

if(R[j].key<R[j-1].key)

{tmp=R[j];

//R[j]与R[j-1]进行交换,

R[j]=R[j-1]; //将最小关键字元素前移

R[j-1]=tmp;

exchange=1; //本趟排序发生交换置exchange为1

}

}if(exchange==0) //本趟未发生交换时结束算法

return;

}}29/86最好的情况（正序）：只需进行一趟冒泡“比较”的次数：0“移动”的次数：n-1最坏的情况（反序）：需进行n-1趟冒泡“比较”的次数：“移动”的次数：9.3交换排序30/86归纳起来，冒泡排序算法的性能如表9.3所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n)O(n2)O(n2)O(1)稳定9.3交换排序31/86

首先对无序的元素序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序序列无序子序列(1)无序子序列(2)基准一次划分分别进行快速排序9.3.2快速排序9.3交换排序32/86每趟使表的第一个元素（基准）放入适当位置，将表一分为二，对子表按递归方式继续这种划分。直至划分的子表长为0或者1。9.3交换排序33/86

【例9.4】设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用快速排序方法进行排序的过程。9.3交换排序34/866

87

9

0

1

3

2455

423019

7861

423

050，1，2，3，4，5，6，7，8，902

3

413

42348

7978快速排序递归树将递归树看成一棵3叉树，每个分支结点对应一次递归调用。这里递归次数：7左右子序列处理的顺序无关9.3交换排序35/8631542划分如何做？tmpiji=j：处理完毕划分完毕整个序列：R[s..t]左子序列：R[s..i-1]右子序列：R[i+1..t]36/86快速排序算法如下：voidQuickSort(SqTypeR[],ints,intt)//对R[s..t]的元素进行递增快速排序{inti=s,j=t;SqTypetmp;if(s<t) //区间内至少存在2个元素的情况

{tmp=R[s]; //用区间的第1个元素作为基准

while(i!=j) //从区间两端交替向中间扫描,直至i=j为止

{while(j>i&&R[j].key>=tmp.key)

j--; //从右向左扫描,找第1个小于tmp.key的R[j] if(i<j)

{R[i]=R[j]; //将R[j]前移到R[i]的位置

i++;}

while(i<j&&R[i].key<=tmp.key)

i++; //从左向右扫描,找第1个大于tmp.key的R[i]

if(i<j){R[j]=R[i]; //将R[i]后移到R[j]的位置

j--;}

}

R[i]=tmp;9.3交换排序37/86QuickSort(R,s,i-1);

//对左区间递归排序

QuickSort(R,i+1,t);

//对右区间递归排序

}}9.3交换排序R[s]………R[t]R[s]…R[i-1]R[i+1]…R[t]R[i]一次划分分别进行快速排序38/86算法分析最好的情况（随机分布）n个元素n/2个元素n/2-1个元素时间复杂度:O(nlog2n)最坏的情况（正序或者反序）n个元素n-1个元素空时间复杂度:O(n2)39/86则可得结果：结论:

快速排序的时间复杂度为O(nlog2n)平均情况：平均所需栈空间为O(log2n)。nk-1n-k1次划分的时间Tavg(n)=Cnlog2n。9.3交换排序40/86归纳起来，快速排序算法的性能如表9.4所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定9.3交换排序41/869.4选择排序选择排序基本思路：每步从待排序的元素中选出关键字最小的元素，按顺序放在已排序的元素序列的最后，直到全部排完为止。主要的选择排序算法：简单选择排序和堆排序。9.4选择排序42/86有序序列R[0..i-1]无序序列R[i..n-1]

第i

趟简单选择排序从中选出关键字最小的元素有序序列R[0..i-1]无序序列R[i+1..n-1]9.4.1简单选择排序9.4选择排序43/86

【例9.5】已知有10个待排序的元素，它们的关键字序列为(75,87,68,92,88,61,77,96,80,72)，给出用直接选择排序法进行排序的过程。初始序列75876892886177968072i=061876892887577968072i=161688792887577968072i=261687292887577968087i=361687275889277968087i=461687275779288968087i=561687275778088969287i=661687275778087969288i=761687275778087889296i=861687275778087889296最后结果616872757780878892969.4选择排序44/86简单选择排序算法如下：voidSelectSort(SqTypeR[],intn) {inti,j,k;

SqTypetmp;

for(i=0;i<n-1;i++)

{k=i;

for(j=i+1;j<n;j++){

if(R[j].key<R[k].key)

k=j; //用k指出每趟在无序区段的最小元素

}if(k!=i)

{tmp=R[i]; //将R[k]与R[i]交换

R[i]=R[k];R[k]=tmp;

}

}}9.4选择排序45/86

对n

个元素进行简单选择排序，所需进行的关键字间的比较次数总计为：移动元素的次数，最小值为0,最大值为3(n-1)。9.4选择排序46/86归纳起来，简单选择排序算法的性能如表9.5所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(n2)O(n2)O(n2)O(1)不稳定9.4选择排序47/86堆排序采用堆结构选择最大（最小）元素。设排序元素为R[1..n]。将R[1..n]看成是一棵完全二叉树的顺序存储结构。如果每个结点的关键字均大于等于其所有孩子结点的关键字，称为大根堆。如果每个结点的关键字均小于等于其所有孩子结点的关键字，称为小根堆。本章的堆排序采用的大根堆。9.4.2堆排序9.4选择排序48/86a1a2a3an…完全二叉树i2i2i+1左孩子右孩子大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字。最小关键字的元素一定是某个叶子结点！！！层序编号方式：a1

a2

…

an将序列a1

a2

…

an看成是一颗完全二叉树9.4选择排序49/86堆排序的关键是构造堆,这里采用筛选算法建堆。所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选堆9.4选择排序50/86例如：（6,8,9,5,7,1）89571大根堆大根堆考虑根，不是大根堆比较tmp6比较整个调整成大根堆了！9.4选择排序51/86

假设对R[low..high]进行堆调整，它是一棵满足筛选条件的完全二叉树，即以R[low]为根结点的左子树和右子树均为堆，其调整堆的算法sift()如下：voidSift(SqTypeR[],intlow,inthigh) //对R[low..high]进行堆筛选{inti=low,j=2*i; //R[j]是R[i]的左孩子

SqTypetmp=R[i];while(j<=high)

{if(j<high&&R[j].key<R[j+1].key)

j++;

//若右孩子较大,把j指向右孩子

if(tmp.key<R[j].key)

{R[i]=R[j]; //将R[j]调整到双亲结点位置上

i=j; //修改i和j值,以便继续向下筛选

j=2*i;

}

elsebreak; //已是大根堆,筛选结束

}

R[i]=tmp; //被筛选结点的值放入最终位置}9.4选择排序52/869.4选择排序是一个堆是一个堆295413从根开始筛选大根堆tmp筛选示例相当于：将2有序插入的（9,4）中（9,4,2）53/86堆排序过程：从最后一个分支结点（编号为n/2）开始到根结点（编号为1）通过多次调用筛选算法建立初始堆。排序过程：9.4选择排序将R[1]（无序区中最大元素）与无序区最后一个元素交换，归位无序区最后一个元素，无序区减少一个元素。再筛选，重复进行，直到无序区只有一个元素。54/86堆排序的算法如下：voidHeapSort(SqTypeR[],intn)//对R[1..n]进行递增堆排序{inti;

SqTypetmp;

for(i=n/2;i>=1;i--) //循环建立初始堆

Sift(R,i,n);

for(i=n;i>=2;i--) //进行n-1次循环,完成堆排序

{ tmp=R[1]; //将R[1]和R[i]交换

R[1]=R[i];R[i]=tmp;

Sift(R,1,i-1); //筛选

}}9.4选择排序55/86【例9.6】已知有10个待排序的元素，它们的关键字序列为（75，87，68，92，88，61，77，96，80，72），给出用堆排序法进行排序的过程。75876892886177968072（1）建立初始堆的过程758768928861779680729.4选择排序56/8675876892886177968072758768968861779280729.4选择排序57/8675876896886177928072758777968861689280729.4选择排序58/8675877796886168928072759677928861688780729.4选择排序59/867596779288616887807296927787886168758072初始堆：96,92,77,87,88,61,68,75,80,729.4选择排序60/86（2）排序过程96927787886168758072第1趟排序结果（i=10）初始堆：72,92,77,87,88,61,68,75,80,96交换72969.4选择排序61/86729277878861687580第2趟排序结果（i=9）初始堆：80,88,77,87,72,61,68,75,92,96交换928877877261687580筛选9280最终结果：61,68,72,75,77,80,87,88,92,90以此类推9.4选择排序62/86堆排序的时间复杂度分析：对高度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

因此，堆排序的时间复杂度为O(nlog2n)。对n个关键字，建成高度为h(=

log2n+1)的堆，所需进行的关键字比较的次数不超过4n9.4选择排序63/86归纳起来，堆排序算法的性能如表9.6所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定9.4选择排序64/86归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表─二路归并排序。9.5归并排序9.5

归并排序65/86在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的元素有序子序列。归并为一个元素的有序序列。有序序列R[low..high]有序子序列R[low..mid]有序子序列R[mid+1..high]9.5

归并排序66/86

【例9.7】已知有10个待排序的元素，它们的关键字序列为（75，87，68，92，88，61，77，96，80，72），给出用归并排序法进行排序的过程。75，87，68，92，88，61，77，96，80，7275，8768，9261，8877，9672，8068，75，87，9261，77，88，9672，8061，68，75，77，87，88，92，9672，8061，68，72，75，77，80，87，88，92，96

log2n

趟9.5

归并排序67/86将两个有序子表归并为一个有序子表的算法Merge()：voidMerge(SqTypeR[],intlow,intmid,inthigh)//将R[low..mid]和R[mid+1..high]两个相邻的有序表归并为有序表R[low..high]{SqType*R1;

inti=low,j=mid+1,k=0; //k是R1的下标R1=(SqType*)malloc((high-low+1)*sizeof(SqType));

//动态分配空间R1while(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++;

}}9.5

归并排序68/86

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++)

R[i]=R1[k]; //将R1复制回R中

free(R1); //释放R1所占内存空间}9.5

归并排序69/86MergePass()算法解决一趟归并问题：voidMergePass(SqTypeR[],intlength,intn)//一趟二路归并排序{inti;

for(i=0;i+2*length-1<n;i=i+2*length)

Merge(R,i,i+length-1,i+2*length-1);

//归并length长的两相邻子表if(i+length-1<n)

//余下两个子表,后者长度小于lengthMerge(R,i,i+length-1,n-1);}9.5

归并排序70/86二路归并排序算法如下：voidMergeSort(SqTypeR[],intn) //二路归并算法{intlength;

for(length=1;length<n;length=2*length)

MergePass(R,length,n);}9.5

归并排序71/86每一趟归并的时间复杂度为O(n)，总共需进行

log2n

趟。所以对n个元素进行归并排序的时间复杂度为Ο(nlog2n)。9.5

归并排序72/86归纳起来，二路归并排序算法的性能如表9.7所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定9.5

归并排序73/86基数排序是通过“分配”和“收集”过程来实现排序。是一种借助于多关键字排序的思想对单关键字排序的方法。9.6基数排序9.6基数排序74/86一般地，元素R[i]的关键字R[i].key是由d位数字组成，即kd-1kd-2…k0，每一个数字表示关键字的一位，其中kd-1为最高位，k0是最低位，每一位的值都在0≤ki<r范围内，其中r称为基数。例如，对于二进制数r为2，对于十进制数r为10。

9.6基数排序75/86基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。最低位优先的过程：先按最低位的值对元素进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有元素进行排序，直至最高位，则完成了基数排序的整个过程。最高位优先类似。9.6基数排序76/86分配：开始时，把Q0,Q1,…,Qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj（j=0,1,…,n-1），如果aj的关键字kji=k，就把aj放进Qk队列中。收集：把Q0,Q1,…,Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。对i=0,1,…,d-1，依次做一次“分配”和“收集”（其实就是一次稳定的排序过程）。9.6基数排序77/86建立10个队列，f为队头，r为队尾

进行第1次分配：按个位进行第1次收集h→369→367→167→239→237→138→230→139f[0]←r[0]f[7]←r[7]f[8]←r[8]f[9]←r[9]→369→367→167→237→239→139→138→230h→230→367→167→237→138→369→239→139例如(369,367,167,239,237,138,230,139)

基数排序第1趟排序完毕分配时是按一个一个元素进行的收集时是按一个一个队列进行的9.6基数排序78/86

进行第2次分配：按拾位进行第2次收集f[3]←r[3]f[6]←r[6]→367→167→369→230h第2趟排序完毕→237→138→139→239h→230→367→167→237→138→369→239→139→230→237→138→139→239→367→167→3699.6基数排序79/86

进行第3次分配：按百位f[1]←r[1]f[2]←r[2]f[3]←r[3]→239→139→138→237→230→369→367h→230→237→138→139→239→367→167→369→167进行第3次收集h第3趟排序完毕，得到最终排序结果→139→138→167→239→237→230→369→3679.6基数排序80/86单键表中结点类型RadixNode声明如下：typedefstructrnode{charkey[MAXD]; //存放关键字ElemTypedata; //存放其他数据

structrnode*next;}RadixNode; //单链表结点类型9.6基数排序123"321"低位高位对于整数应该按个位开始排序，转换为字符数组后按最高位优先排序！81/86voidRadixSort1(RadixNode*&h,intd,intr)//实现基数排序:h为待排序数列单链表指针,r为基数,d为关键字位数{RadixNode*head[MAXR]; //建立链队队头数组

RadixNode*tail[MAXR]; //建立链队队尾数组RadixNode*p,*tc;

inti,j,k;9.6基数排序最高位优先基数排序算法82/86for(i=d-1;i>=0;i--) //从高位到低位循环{for(j=0;j<r;j++) //初始化各链队首、尾指针

head[j]=tail[j]=NULL;

p=h;

while(p!=NULL)

//分配：对于原链表中每个结点循环

{k=p->key[i]-'0'; //找第k个链队

if(head[k]==NULL) //第k个链队空，队头队尾均指向p结点

head[k]=tail[k]=p;

else

{tail[k]->next=p; //第k个链队非空时，p结点入队

tail[k]=p;

}

p=p->next; //取下一个待排序的元素

}9.6基数排序83/86h=NULL;

//重新用h来收集所有结点

for(j=0;j<r;j++) //收集：对于每一个链队循环

{

if(head[j]!=NULL) //若第j个链队是第一个非空链队

{if(h==NULL)

{h=head[j];tc=tail[j];}

else

//若第j个链队是其他非空链队

{tc->next=head[j];tc=tail[j];}

}

tc->next=NULL; //尾结点的next域置NULL

}

}}9.6基数排序84/86

基数排序的时间复杂度为O(d(n+r))其中：分配为O(n)

收集为O(r)（r为“基数”）

d为“分配-收集”的趟数9.6基数排序85/86归纳起来，基数排序算法的性能如表9.8所示。时间复杂度空间复杂度稳定性最好情况最坏情况平均情况O(d(n+r))O(d(n+r))O(d(n+r))O(r)稳定9.6基数排序86/86第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7外排序第9章

排序87/32（1）生成若干初始归并段（顺串）：这一过程也称为文件预处理，常规方法：

①把含有n个元素的文件，按内存大小分成若干长度为L的子文件（归并段）。

②分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。

（2）多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。9.7外排序9.7外排序外排序的基本方法是归并排序法。它分为以下两个步骤：88/32内存abc.databc1.databc2.dat…abcn.dat内存abc1.databc2.dat…abcn.databc.dat第1步第2步有序均有序某内排序算法某排序算法：一般为归并算法9.7外排序89/32外排序的时间：读写文件的时间：用读写元素次数表示。关键字比较的时间：内存中的元素比较。外排序的时间≈读写文件时间+关键字比较时间9.7外排序90/329.7.1磁盘排序过程磁盘（磁盘是一种直接存取设备）排序过程如下：Fin文件内存读写Fout文件F1文件F2文件Fm文件…写写写内存读读读

生成若干初始归并段

归并成一个有序文件9.7外排序91/32设有一个文件Fin.dat，内含4500个元素：A1,A2,…,A4500。现在要对该文件进行排序。可占用的内存空间至多只能对750个元素进行排序。输入文件（被排序的文件）放在磁盘上，页块长为250个元素。文件Fin.dat（含4500个元素）容量为750个元素产生6个长度为750个元素的有序文件F1～F6。第一阶段某种内排序方法9.7外排序92/32可用内存空间大小为750个元素第二阶段：归并过程

F1F2F3F4F5F6F7F8F9F10F119.7外排序93/329.7.2初始归并段的生成方法1采用前面介绍的常规内排序方法，可以实现初始归并段的生成，但所生成的归并段的大小正好等于一次能放入内存中的元素个数。显然存在局限性。

内存abc.databc1.databc2.dat…abcn.dat均有序某内排序算法特点：产生的初始归并段个数多，每个初始归并段的长度大致相等。9.7外排序94/32采用置换－选择排序算法用于生成初始归并段。方法2

特点：产生的初始归并段个数少，每个初始归并段的长度可能差异大。9.7外排序95/32

【例9.9】设某个磁盘文件中共有18个元素，各元素的关键字分别为（15，4，97，64，17，32，108，44，76，9，39，82，56，31，80，73，255，68）。

若内存工作区可容纳5个元素，用置换-选择排序算法可产生几个初始归并段，每个初始归并段包含哪些元素？9.7外排序96/32173294476108398256318073154976425568∞18个元素（w=5）：内存工作区w=5归并段1：归并段2：Rmin=415173244647682971089依次类推，产生归并段2：9，31，39，56，68，73，80，2559.7外排序97/32k=2时,采用平衡归并时，如果初始归并段有m个，那么这样的归并树就有

log2m

+1层。要对数据进行

log2m

趟扫描。9.7.3多路平衡归并

说明：如果所有初始归并段的长度（初始归并段中的元素个数）相等或大致相等，可采用k路平衡归并。1.k路平衡归并的效率分析9.7外排序98/32例如：二路平衡归并5初始序列：（5,4,1,6,8,3,2,7）4168327451638271456237812345678高度log2m=4归并3趟每个页块读写各1次假设一个页块存放1个元素读或者写元素次数恰好是WPL，这里WPL=8*1*3=24读写元素次数=2WPL，这里为48用WPL反映外排序中的读写文件的时间9.7外排序99/32k路平衡归并的读写文件时间分析：若有m个初始归并段，共u个元素归并趟数=

logkm

k越大，WPL越少，则读写元素的次数越少。在内存空间允许的情况下，k越大越好！9.7外排序100/32若在归并中采用简单选择方法，每次在k个元素中选择最小者，需要关键字比较k-1次。每趟归并u个元素需要做(u-1)*(k-1)次比较，s=

logkm

）趟归并总共需要的关键字比较次数为：k路平衡归并的关键字比较时间分析：k越大，关键字比较次数越多！增大归并路数k，会使内部归并的时间增大。若k增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢得的时间。s*(u-1)*(k-1)=

logkm

*(u-1)*(k-1)=

log2m

*(u-1)*(k-1)／

log2k

9.7外排序101/32在k路归并中从k个元素简单选择最小元素2.利用败者树实现k路平衡归并采用败者树从k个元素简单选择最小元素9.7外排序102/32利用败者树实现k路平衡归并的过程是：

败者树类似于堆排序中的堆。先建立败者树。然后对k个输入有序段进行k路平衡归并。9.7外排序103/32

【例9.10】设有5个初始归并段，它们中各元素的关键字分别是：

F0：{17，21，∞}

F1：{5，44，∞}

F2：{10，12，∞}

F3：{29，32，∞}

F4：{15，56，∞}

其中，∞是段结束标志。说明利用败者树进行k=5路平衡归并排序的过程。9.7外排序104/32解：

构建败者树29F315F417F05F110F25(-∞)5(-∞)5(-∞)5(-∞)冠军（最小者）k=5：创建含有k个叶子结点的完全二叉树，总共2k-1=9个结点，另外添加一个冠军结点。每个叶子结点对应一个归并段，段号为0～4。初始时每个分支结点（含冠军）取值“5(-∞)”，5表示段号（此时为虚拟段号），-∞表示最小关键字。例如，某结点取值为“4(15)”，表示结点值来自4号段的关键字15对应的元素。9.7外排序105/3229F3