数据结构JAVA语言描述习题答案(刘小晶等主编).第7章排序(Java版)

第七章排序1教学内容7.1排序的基本概念

7.2插入排序7.3交换排序

7.4选择排序

7.5归并排序

7.6基数排序

教学重点与难点重点：掌握排序的基本概念以及各种常见排序方法的实现。难点：希尔排序、快速排序、归并排序和堆排序等高效排序方法。【课前思考】1.熟悉排序吗？过去曾经学过哪些排序方法？

在第一章中曾以选择排序和起泡排序为例讨论算法实际复杂度．

2.自己有没有编过排序的程序？是用的什么策略？4

1、排序的定义3、内部排序的方法4、排序算法的性能评价5、待排序记录的类描述2、排序的分类7.1排序的基本概念5

1、排序的定义排序是计算机内经常进行的一种操作，是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,976

严格定义如下：一般情况下，假设含n个记录的序列为{R0,R1,…，Rn-1}其相应的关键字序列为{K0,K1,…，Kn-1}这些关键字相互之间可以进行比较，且在它们之间存在着这样一个关系：

Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为

{Rp1,Rp2,

…，Rpn}的操作称作排序。1、排序的定义7

关键字

是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。

若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。

若此关键字能识别若干记录，则称之谓“次关键字”。8

2、排序的分类(1)按排序过程中所涉及到的存储器不同分为：(2)按相同关键字在排序前后的位置不同分为：稳定排序

内部排序

外部排序

不稳定排序假设Ki=Kj（i≠j),且在排序前的序列中Ri领先于Rj（即i＜j)。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。

9

3、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区10

基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类

归并类其它方法3、内部排序的方法11

(1)插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。12

(2)交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。13

(3)选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。14

(4)归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。(5)其它方法就各类介绍一二个典型算法。如：基数排序下面就各类介绍一二个典型算法。15

4、排序算法的性能评价时间比较次数（与关键字值比较）移动次数空间：指所需辅助空间的大小稳定性16

内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；17

待排序的顺序表记录类描述如下:(P242)

publicclassRecordNode

{privateComparablekey;//关键字

privateObjectelement;//数据元素……}备注：1.key为Comparable接口类型，它能够赋值为任何实现Comparable接口类的对象。

2.element为Object类型，在实际应用时，可根据不同问题定义为不同的具体类。5、待排序记录的类描述18

待排序的顺序表类(P243)publicclass

SeqList{

privateRecordNode[]r;

//顺序表记录结点数组

privateint

curlen;

//顺序表长度，即记录个数//构造方法:构造一个存储空间容量为maxSize的顺序表

publicSeqList(int

maxSize){

this.r=newRecordNode[maxSize];

//为顺序表分配maxSize个存储单元

this.curlen=0;

//置顺序表的当前长度为0}

……}19

总思想：

每次将一个待排序的记录，按其关键字值的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。7.2插入排序20

有序序列r[0..i-1]R[i]无序序列r[i..n-1]一趟插入排序的基本思想：有序序列r[0..i]无序序列r[i+1..n-1]21

实现“一趟插入排序”可分三步进行：3．将r[i]

插入(复制)到r[j+1]的位置上。2．将r[j+1..i-1]中的所有记录均后移

一个位置；1．在r[0..i-1]中查找r[i]的插入位置，

r[0..j].keyr[i].key<r[j+1..i-1].key；22

直接插入排序（基于顺序查找）

确定插入位置的查找方法不同导致不同的算法描述：希尔排序（基于逐趟缩小增量）7.2插入排序23

待排序记录依次存放在数组r[0..n-1]中。思想：

先将第0个记录组成一个有序的子表，然后依次将后面的记录插入到这子表中，且一直保持它的有序性。7.2.1直接插入排序-不带监视哨的算法基本条件：24

例：

（43）

21891543

（1521434389）i=4i=1

（2143）

891543

(214389）

1543i=2直接插入排序示例r0r1r2r3r443

218915437.2.1直接插入排序-不带监视哨的算法（15214389)

43i=325

实现直接插入排序的步骤为：(P244)2）后移并插入3）令i=1，2，…,n-1,重复1）、

2），实现整个序列的排序。1）查找r[i]的插入位置7.2.1直接插入排序-不带监视哨的算法将r[i]暂存在临时变量temp中，将temp与r[j](j=i-1,…，0）依次进行比较

如何查找？26

publicvoidinsertSort(){

RecordNodetemp;

inti,j;

for(i=1;i<this.curlen;i++){

//n-1趟扫描

temp=r[i];

//第i条记录暂存在temp中

for(j=i-1;j>=0&&temp.getKey().compareTo(r[j].getKey())

<0;j--){

r[j+1]=r[j];

//后移

}

r[j+1]=temp;

//r[i]插入到第j+1个位置

}}

7.2.1直接插入排序-不带监视哨的算法P245算法7.1算法需进行改进！！27

此算法中第6行的循环条件中的“j>=0”用来控制下标越界。为了提高算法效率，可对该算法进行如下改进：首先将待排序的n条记录从下标为1的存储单元开始依次存放在数组r中，再将顺序表的第0个存储单元设置为一个“监视哨”，即在查找之前把r[i]赋给r[0]，这样每循环一次只需要进行记录的比较，不需要比较下标是否越界7.2.1直接插入排序-带监视哨的算法28

例：初始关键字：

（43）

21891543(21)（2143）

891543i=2(15)（15214389)43i=4(43)（1521434389）i=5(89)(214389）

1543i=3直接插入排序示例r0r1r2r3r4r5432189154329

从r[i-1]起向前进行顺序查找，

监视哨设置在r[0]；r[0]=r[i];//设置“哨兵”循环结束表明r[i]的插入位置为j+1r[0]jr[i]for(j=i-1;r[0].getKey<r[j].getKey;--j);//从后往前找j=i-1插入位置如何查找到r[i]的插入位置？7.2.1直接插入排序-带监视哨的算法30

对于在查找过程中找到的那些关键字不小于R[i].key的记录，在查找的同时实现记录向后移动；for(j=i-1;r[0].getKey<r[j].getKey;--j)

r[j+1]=r[j]；r[0]jr[i]j=i-1上述循环结束后可以直接进行“插入”插入位置后移并插入7.2.1直接插入排序-带监视哨的算法31

令i=2，…,curlen-1,实现整个序列的排序。for(i=2;i<=curlen;++i)

{在

r[0..i-1]中查找r[i]的插入位置;

插入r[i];

}7.2.1直接插入排序-带监视哨的算法32

voidinsertSortWithGuard()(){//对顺序表

作直接插入排序。for(i=2;i<=this.curlen;++i){

}}r[0]=r[i];//复制为监视哨for(j=i-1;

r[0].getKey().compareTo(r[j].getKey())<0;

j--)

r[j+1]=r[j];

//记录后移r[j+1]=r[0];//插入到正确位置7.2.1直接插入排序-带监视哨的算法P245算法7.233

不带监视哨的直接插入排序性能分析：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：34

平均值：约n2/4１.直接插入排序的时间复杂度：2.只需记录的辅助空间３.是的排序方法一个稳定O（n2)7.2.1直接插入排序-性能分析35

（又称缩小增量排序）

基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。

所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：7.2.2希尔排序36

将记录序列分成若干子序列，分别对每个子序列进行插入排序。

其中，d

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

{r[0]，r[0+d]，r[0+2d]，…，r[0+kd]}{r[1]，r[1+d]，r[1+2d]，…，r[1+kd]}…{r[d－1]，r[2d－1]，r[3d－1]，…，r[d+kd-1]}7.2.2希尔排序37

例1：初始关键字序列如下：{49，38，65，97，76，13，27，49，5504}，请写出它们的希尔排序的全过程(其中d=5,3,1）7.2.2希尔排序38

初始关键字：49,38,65,97,76,13,27,49,55,4取d3=1三趟分组：三趟排序结果：一趟排序结果：二趟排序结果：取d1=5一趟分组：取d2=3二趟分组：493865977613274955413274955449386597761327495544938659776134493827495565977613449382749556597764132738494955657697不稳定的排序方法39publicvoidshellSort(int[]d){

RecordNodetemp;

inti,j;for(intk=0;k<d.length;k++){

int

dk=d[k];for(i=dk;i<this.curlen;i++){

temp=r[i];for(j=i-dk;j>=0&&temp.getKey().compareTo(r[j].getKey())<0;j-=dk){r[j+dk]=r[j];

}

r[j+dk]=temp;}}P247算法希尔排序-算法40

１.希尔排序的时间复杂度：

不确定，但在插入排序中，希尔排序的效能最高，最好情况可达O（nlog2n)３.是的排序方法例：对序列2，1，1进行希尔排序（d分别取2,1时）结果：1，1，2不稳定2.只需记录的辅助空间一个7.2.2希尔排序-性能分析41

1.冒泡排序2.快速排序7.2交换排序42

1.基本思想：

将待排序的数组看成从上到下的存放，把关键字较小的记录看成“较轻的”，关键字较大的记录看成“较重的”，小关键字的记录好像水中的气泡一样，向上浮；大关键字的记录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，且所有的石块都沉到了水中，排序就结束了。7.3.1冒泡排序43

从第一个记录开始，依次对无序区中相邻记录进行关键字比较，如果大在上，小在下，则交换，第一趟扫描下来表中最大的沉在最下面。然后再对前n-1个记录进行冒泡排序，直到排序成功为止。

一般地，第i趟扫描时,r[0]到r[n-i]和r[n-i+1]到r[n－1]分别为当前的无序区和有序区。2.基本步骤7.3.1冒泡排序44

假设在排序过程中，记录序列r[0..n-1]的状态为：第i趟起泡排序无序序列r[0..n-i]有序序列r[n-i+1..n-1]n-i+1无序序列r[0..n-i+1]有序序列r[n-i+1..n-1]比较相邻记录，将关键字最大的记录交换到

n-i+1的位置上例1：写出对关键字序列{43，21，89，15，28，43}进行冒泡排序的各趟结果7.3.1冒泡排序45

985420895420859420854920854290854209大数沉淀，小数起泡a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<5;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}46854209584209548209542809542089a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<4;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}47542089452089425089420589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<3;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}48420589240589204589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<2;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}49204589024589a[0]a[1]a[2]a[3]a[4]a[5]for(i=0;i<1;i++)if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}50for(i=0;i<5;i++)if(a[i]>a[i+1]){……}for(i=0;i<4;i++)if(a[i]>a[i+1]){……}for(i=0;i<1;i++)if(a[i]>a[i+1]){……}……for(i=0;i<6-j;i++)if(a[i]>a[i+1]){……}for(j=1;j<6;j++)6-16-26-551publicvoid

bubbleSort(){

RecordNodetemp;

//辅助结点for(inti=1;i<this.curlen;i++){//进行n-1趟排序for(intj=0;j<this.curlen-i;j++){

if(r[j].getKey().compareTo(r[j+1].getKey())>0){

//逆序时，交换

temp=r[j];r[j]=r[j+1];

r[j+1]=temp;}

}}}7.3.1冒泡排序-算法52

publicvoid

bubbleSort(){

RecordNodetemp;

boolean

flag=true;

//是否交换的标记

for(inti=1;i<this.curlen

&&flag;

i++){

//有交换时再进行下一趟，最多n-1趟

flag=false;

//记录未交换标志

for(intj=0;j<this.curlen-i;j++){

if(r[j].getKey().compareTo(r[j+1].getKey())>0){

//逆序时，交换

temp=r[j];r[j]=r[j+1];

r[j+1]=temp;

flag=true;

//记录交换标志

}}}7.3.1冒泡排序-改进算法P249/算法7.453

2.一般情况下，每经过一趟“冒泡”，“i减一”（即无序区的长度减一），但并不是每趟都如此。例如:2553157989i=7i=613i=21.冒泡排序的结束条件为，

最后一趟没有进行“交换记录”。7.3.1冒泡排序-注意:54

7.3.1冒泡排序-思考:1）若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，算法如何改进？2）双向起泡的排序算法如何写？3）已知奇偶转换排序如下：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。

a)试问排序结束的条件是什么？

b)实现上述排序过程的算法如何？55

最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-17.3.1冒泡排序-性能分析：56

１.起泡排序的时间复杂度：

O（n2)2.只需一个记录的辅助空间

O(1)３.是稳定的排序方法7.3.1冒泡排序-性能分析：57

通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。7.3.2快速排序基本思想：58

找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列r[s..t]将分割成两部分：r[s..i-1]和r[i+1..t]，且

r[j].getKey()≤r[i].getKey()≤r[j].getKey()(s≤j≤i-1)

枢轴

(i+1≤j≤t)。7.3.2快速排序-一趟快速排序1.目标：59

无序的记录序列无序记录子序列(1)无序子序列(2)枢轴通过一趟快速排序后（一次划分）7.3.2快速排序-一趟快速排序60

lowhighij设r[s]=52为枢轴

将r[j].getKey()和枢轴关键字进行比较,要求r[j].getKey()≥

枢轴的关键字；

将r[i].getKey()和枢轴关键字进行比较，要求r[i].getKey()≤

枢轴的关键字。j23i80j14i52prvot52jjji7.3.2快速排序-一趟快速排序i61

493865977613274927i初始关键字：jx49jii65j13i97jj494938659776132749初始关键字：完成一趟排序：2738134976976549一次划分后：(273813)49(76976549)分别进行快速排序：(13)

27

(38)

49(4965)

76(97)

(13)

27

(38)

49

49(65)

76(97)快速排序结束：13

27

3849

4965

76

97不稳定的排序方法62

可见，经过“一次划分”，将关键字序列

52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75

在调整过程中，设立了两个变量：i

和j，它们的初值分别为：low和high，

之后逐渐减小

j，增加

i，并保证

r[j].getKey()≥52，和r[i].getKey()≤52,否则进行记录的“交换”。7.3.2快速排序-一趟快速排序63

以首结点为枢轴,考虑的结点序列为r[low]，r[low+1]，…，r[high],且low<high。1）i=low,j=high,pivot=r[i];2）如果i!=j，则

(a)若r[j].getKey()>pivot,那么j=j-1,

转(a)；否则r[i]=r[j]，i=i+1,转（b）

(b)若r[i].getKey()<=pivot,那么i=i+1，转(b)；否则r[j]=r[i],j=j-1,转2）3）如果i==j，则r[i]=pivot，算法结束。2.算法基本步骤：7.3.2快速排序-一趟快速排序64

intPartition(inti,intj){//一趟快速排序算法7.5}//PartitionRecordNode

pivot=r[i];//枢轴while(i<j){}while(i<j&&pivot.getKey().compareTo(r[j].getKey())<0)j--;//从右向左搜索if(i<j)r[i++]=r[j];while(i<j&&pivot.getKey().compareTo(r[i].getKey())>0)i++;//从左向右搜索if(i<j)r[j--]=r[i];r[i]=pivot;

returni;65

再例如：根据算法步骤写出对关键字序列{26，37，08，63，12，59，12，48}进行快速排序的第一趟排序过程和每一趟排序结果。66

3、快速排序

首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序67

publicvoidqSort(intlow,inthigh){if(low<high){

int

pivotloc=Partition(low,high);

//一趟排序，将排序表分为两部分

qSort(low,pivotloc-1);

//低子表递归排序

qSort(pivotloc+1,high);

//高子表递归排序

}[算法7.6]递归形式的快速排序算法(P251)68

void

QuickSort(){

//对顺序表进行快速排序

qSort(0,curlen-1);}//QuickSort

第一次调用函数Qsort

时，待排序记录序列的上、下界分别为

0

和curlen-1。69

快速排序的性能分析假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间：其中Tpass(n)为对n个记录进行一次划分所需时间。

若待排序列中记录的关键字是随机分布的，则k

取1至n

中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)70

设Tavg(1)≤b则可得结果：由此可得快速排序所需时间的平均值为：71

1)快速排序的时间复杂度为:

2)所需辅助空间

3）是排序O(nlog2n)

是内部排序中性能最好的一种。O（log2n）不稳定例：对序列2，1，1进行快速排序的结果：1，1，27.3.2快速排序-性能分析72

若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。

为避免出现这种情况，需在进行一次划分之前，进行“预处理”，即：

先对R(s).key,R(t).key

和R[(s+t)/2].key，进行相互比较，然后取关键字为

“三者取中”的记录为枢轴记录。7.3.2快速排序73

直接选择排序树形选择排序堆排序7.4选择排序74

1.基本思想

首先在所有记录中选出关键字值最小的记录，把它与第一个记录进行位置交换，然后在其余的记录中再选出关键字值次小的记录与第二个记录进行位置交换，依此类推，直到所有记录排好序。7.4.1直接选择排序75

假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1]无序序列R[i..n]

第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列

R[i+1..n]7.4.1直接选择排序76

例：写出对关键字系列

{4938659776132749

}

进行选择排序的每一趟结果。7.4.1直接选择排序77

13(38659776492749)初始：(4938659776132749)i=11349i=22738i=3i=4i=5i=61327(659776493849)3865132738(9776496549)499713273849(76976549)49761327384976(9765)49766597132738497697(97)497665767697排序结束13273849769765()497676976576782.基本步骤：（1）置i为0。（2）当i<n-1，重复下列步骤：.a.在（R[i],…,R[n-1]）中选出一个关键字值最小的记录R[k]；

b.若R[k]不是R[i],(即k!=i），交换R[i],R[k]的位置，否则不进行交换；

c.i值加1。79

直接选择排序的算法描述如下：void

SelectSort(){//对顺序表作简单选择排序。

for(i=0;i<length-1;++i){

//选择第i小的记录，并交换到位

}}//SelectSortj=SelectMinKey(R,i);

//在R[i..n]中选择关键字最小的记录if(i!=j)R[i]←→R[j];//与第i个记录交换80

publicvoidselectsort()//算法7.8{RecordNodetemp;

for(inti=0;i<this.curlen-1;i++){

if(min!=i){temp=r[i];

r[i]=r[min];

r[min]=temp;}}}

intmin=i;

for(intj=i+1;j<this.curlen;j++)if(r[j].key<r[min].key)min=j;81

性能分析：

对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：

移动记录的次数，最小值为0,

最大值为3(n-1)。82

1)直接选择排序的时间复杂度为

2)所需辅助空间

3）是排序

O(n2)O(1)不稳定例如：对序列3,3,1进行选择排序，结果为：1，3，37.4.1直接选择排序-性能分析83

基本思想是:首先针对n个记录进行两两比较，比较的结果是把关键字值较小者作为优胜者上升到父结点，得到个比较的优胜者(关键字值较小者)，作为第一步比较的结果保留下来；然后对这个记录再进行关键字的两两比较，如此重复，直到选出一个关键字值最小的记录为止。

这个过程可用一个含有n个叶子结点的完全二叉树来表示

7.4.2树形选择排序84

例如：对于由8个关键字组成的序列{52，39，67，95，70，8，25，45}，使用树形选择排序选出最小关键字值的过程可用图(a)所示的完全二叉树来表示。7.4.2树形选择排序85

7.4.2树形选择排序86

要求出次小关键字记录，只需将叶子结点中最小的关键字值改为“∞”，然后从该叶子结点开始与其左(或右)兄弟的关键字进行比较，用较小关键字修改父结点关键字，用此方法，从下到上修改从该叶子结点到根结点路径上的所有结点的关键字值，则可得到次小关键字记录，如图(b)所示。以此类推，可依次选出从小到大的所有关键字。7.4.2树形选择排序87

7.4.2树形选择排序88

⑴空间复杂度树形选择排序虽然减少了排序时间，但使用了较多的附加存储空间。⑵时间复杂度树形选择排序的时间复杂度为O(nlog2n)

⑶算法稳定性树形选择排序是一种稳定的排序算法。算法性能分析89

堆是满足下列性质的数列{r1,r2,…，rn}：或7.4.3堆排序(小顶堆)(大顶堆)

若将该数列视作完全二叉树，则r2i+1

是ri

的左孩子；r2i+2

是ri

的右孩子。所以，堆的含义表明：完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。90

1236276549817355403498是堆14不{12,36,27,65,40,34,98,81,73,55,49}例如:是小顶堆{12,36,27,65,40,14,98,81,73,55,49}不是堆91

2.堆排序的方法：首先把待排序的记录序列对应成一棵完全二叉树，并把它转换成一个初始堆（即首先建初始堆）。这时，根结点具有最大（或最小）的关键字值，然后，交换根结点和最后一个结点（即第n个结点）的位置，除最后一个结点之外，前n-1个结点仍构成一棵完全二叉树，再把它们调整为一个堆。同样交换根结点和最后一个结点（即第n-1个结点）。重复进行下去，直到只剩下一个根结点为止，便得一个有序表。92

例如：建大顶堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交换98和12重新调整为大顶堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}经过筛选初始关键字93

如何“建初始堆”？两个问题:如何“筛选”？94

所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选95

98814973556412362740例如:是大顶堆12但在98和12进行互换之后，它就不是堆了，因此，需要对它进行“筛选”。98128173641298比较比较96

建堆是一个从下往上进行“筛选”的过程。40554973816436122798例如:排序之前的关键字序列为123681734998817355

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。9849406436122797

voidHeapSort(){//堆排序算法7.12(P262)

intn=this.curlen;

RecordNodetemp;}for(inti=n/2-1;i>=0;i--)//创建堆

sift(i,n-1);//每趟将最小关键字值交换到后面，再调整成堆for(inti=n-1;i>0;i--){

temp=r[0];r[0]=r[i];r[i]=temp;

sift(0,i-1);}98

堆排序的时间复杂度分析：1.

对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.

调整“堆顶”n-1

次，总共进行的关键字比较的次数不超过

2(log2(n-1)+log2(n-2)+

…+log22)<2n(log2n)因此，堆排序的时间复杂度为O(nlogn)。2.

对

n

个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多4n；99

结论:

1)堆排序的时间复杂度为

2)所需辅助空间

3）是排序

O(nlog2n)O(1)不稳定100

归并排序的过程基于下列基本思想进行：

将两个或两个以上的有序子序列“归并”为一个有序序列。7.5归并排序101

在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列r[l..n]有序子序列r[l..m]有序子序列r[m+1..n]这个操作对顺序表而言，是轻而易举的。7.5归并排序102

2-路归并的方法

将待排序记录R[0]到R[n-1]看成是n个长度为1的有序子表，把这些子表依次两两归并，便得到[n/2]个有序的子表，然后，再把这[n/2]个有序的子表两两归并，如此重复，直到最后得到一个长度为n的有序表为止。7.5归并排序103

例如，如下图为2-路归并的一个例子：(52)(23)(80)(36)(68)(14)(27)(2352)(3680)(1468)(27)(23365280)(142768)(14232736526880)一趟归并之后二趟归并之后三趟归并之后7.5归并排序104

归并排序的算法如果记录无序序列R[s..t]的两部分

R[s..(s+t)/2]和R[(s+t)/2+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。

由此，应该先分别对这两部分进行2-路归并排序。105

例如：52,23,80,36,68,14(s=1,t=6)[52,23,80][36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]106

容易看出，对n

个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行log2n趟。107

结论：

1)归并排序的时间复杂度为

2)所需辅助空间

3）是排序

O(n)稳定O(nlog2n)7.5归并排序-性能分析108

基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序链式基数排序7.6基数排序109

7.6.1多关键字的排序

n

个记录的序列{R1,R2,…，Rn}对关键字(Ki0,Ki1,…,Kid-1)有序是指：

其中:K0被称为“最主”位关键字Kd-1被称为“最次”位关键字

对于序列中任意两个记录Ri

和Rj(1≤i<j≤n)都满足下列(词典)有序关系：

(Ki0,Ki1,

…,Kid-1)<(Kj0,Kj1,

…,Kjd-1)110

实现多关键字排序通常有两种作法:最次位优先LSD法最主位优先MSD法7.6.1多关键字的排序111

先对K1进行排序，并按K1的不同值将记录序列分成若干子序列之后，分别对K2进行排序，...…，依次类推，直至最后对最次位关键字排序完成为止。7.6.1多关键字的排序-MSD法112

先对Kd

进行排序，然后对Kd-1进行排序，依次类推，直至对最主位关键字K1排序完成为止。

排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。7.6.1多关键字的排序-LSD法113

例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。

无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:7.6.1多关键字的排序114

7.6.2链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。

对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。115

例如：对下列这组关键字

{209,386,768,185,247,606,230,834,539}

首先按其

“个位数”

取值分别为0,1,…,9

“分配”成10组，之后按从0至9的顺序将它们

“收集”

在一起；

然后按其

“十位数”

取值分别为0,1,…,9

“分配”成10组，之后再按从0至9的顺序将它们

“收集”

在一起；最后按其“百位数”重复一遍上述操作。7.6.2链式基数排序116

在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：

1)待排序记录以指针相链，构成一个链表；２)“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；３)“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;４)对每个关键字位均重复2)和3)

两步。7.6.2链式基数排序117

例如：p→369→367→167→239→237→138→230→139进行第一次分配进行第一次收集f[0]r[0]f[7]r[7]f[8]r[8]f[9]r[9]p→230→230←→367←→167→237→367→167→237→138→368→239→139→369←→239→139→138←7.6.2链式基数排序118

进行第二次分配p→230→237→138→239→139p→230→367→167→237→138→368→239→139f[3]r[3]f[6]r[6]→230←→237→138→239→139→367←→167→368→367→167→368进行第二次收集7.6.2链式基数排序119