计算机软件技术基础第3章1

第3章查找与排序技术

3.1基本的查找技术

3.2哈希表技术

3.3基本的排序技术

3.4二叉排序树及其查找

3.1基本的查找技术

3.1.1顺序查找

3.1.2有序表的对分查找

3.1.3分块查找

3.1.1顺序查找

⑴如果线性表为无序表（即表中元素的排列是

无序的），则不管是顺序存储结构还是链式存

储结构，都只能用顺序查找。

⑵即使是有序线性表，如果采用链式存储结构,

也只能用顺序查找。

线性表在顺序存储结构下的顺序查找

输入：线性表长度n以及线性表的存储空间V；

被查找的元素X。

输出：被查找元素x在线性表中的序号鼠

如果在线性表中不存在元素x,则输出k=

—1O

PROCEDURESERCH(V,n,x,k)

k=l

WHILE(kWn)and(V(k)Wx)DOk=k+l

IF(k=n+l)THENk=-l

RETURN

/*函数返回被查找元素X在线性表中的序号，

如果在线性表中不存在元素值X,则返回一1*/

intsearch(intv[],intn,intx)

{intk；

k=0；

while((k<n)&&(v[k]!=x))k=k+l；

if(k==n)k=­1；

return(k)；

线性表在链式存储结构下的顺序查找

输入：线性链表头指针HEAD以及存储空间V、NEXT；

被查找的元素X。

输出：被查找元素x的结点在线性链表中的存储序号k。

如果在线性链表中不存在元素值为x的结点，

则输出k=-1。

PROCEDURELSERCH(V,NEXT,HEAD,x,k)

k=HEAD

WHILE(kWO)and(V(k)Wx)DOk=NEXT(k)

IF(k=0)THENk=-l

RETURN

structnode

{intd；structnode*next；}；

/*函数返回被查找元素x所在结点的存储地址，

如果在线性链表中不存在元素值为x的结点，则返回

NULL*/

structnode*Iserch(structnode*head,intx)

{structnode*k；

k=head；

while((k!=NULL)&&(k—>d!=x))k=k—>next；

return(k)；

3.1.2有序表的对分查找

设有序线性表的长度为n,被查元素为x。

将x与线性表的中间项进行比较：

(1)若中间项的值等于x,则说明查到，查找结束；

(2)若x小于中间项的值，则在线性表的前半部分(即中间项以前

的部分)以相同的方法进行查找；

(3)若x大于中间项的值，则在线性表的后半部分(即中间项以后

的部分)以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为0(说明线性表中没有

这个元素)为止。

在最坏情况下，对分查找只需比较log2n次，而顺序查找需比较n

次。

有序线性表在顺序存储结构下的对分查找

输入：有序线性表长度n以及线性表的存储空间V；被查找的元素X。

输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存

在兀素x,则输出k=-1。

PROCEDUREBSERCH(V,n,x,k)

i=l；j=n

WHILE(i<=j)DO

{k=(i+j)/2

IF(V(k)=x)THENRETURN

IF(V(k)>x)THENj=k—1；

ELSEi=k+l；

}

IF(i>j)THENk=-l

RETURN

intbserch(intv[],intn,intx)

/*函数返回被查找元素x在线性表中的序号

如果在线性表中不存在元素值x,则返回一1*/

{inti,j,k；

i=l;j=n；

while(i<=j)

{k=(i+j)/2；

if(v[k—1]==x)return(k—1)；

if(v[k-1]>x)j=k—1；

elsei=k+l；

return(—1)；

3.1.3分块查找（索引顺序）

分块有序表

将长度为n线性表分成m个子表，各子表的长度可以相等，也可以互相不

等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素o

分块有序表的结构可以分为两部分：

⑴线性表本身采用顺序存储结构。

⑵再建立一个索引表。在索引表中，对线性表的每个子表建立一个索

引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的

最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线

性表中的序号。

structindnode

{intkey；/*数据域，存放子表中的最大值,

其类型与线性表中元素的数据类

型相同*/

intk；/*指针域，指示子表中第一个元素

在线性表中的序号*/

索引表

数据域224686

指针域1713

线性表：2213080920334244382446605874478653

⑴首先查找索引表，以便确定被查元素所在的子表。由

于索引表数据域中的数据是有序的，因此可以采用对

分查找。

⑵然后在相应的子表中用顺序查找法进行具体的查找。

分块查找

输入：长度为n的线性表L的存储空间V（Ln）；索引表中

的数据域存储空间KEY（1：m）与指针域存储空间

K（l：m）；被查元素x。

输出：被查元素x在线性表L中的序号j（即使L（j）

=乂的））。如果x不在线性表L中，则置j=—1。

PROCEDUREINSERCH(V,n,KEY,K,m,x,j)

i=l；j=m

WHILE(j-i>l)DO［对分查找索引表］

{t=(i+j)/2

IF(xWKEY(t))THENj=t

ELSEi=t

)

IF(iWj)and(x>KEY(i))THENi=j

j=K(i)；t=n

IF(iWm)THENt=K(i+l)-l［确定顺序查找的终点］

WHILE(jWt)and(V(j)Wx)DOj=j+l［顺序查找子表］

IF(j>t)THENj=—1

RETURN

在分块查找中，为了找到被查元素X所在的子表，需要对分查找索引

表，在最坏情况下需要查找log2（m+l）次。

在相应子表中用顺序查找法查找元素x,在最坏情况下需要查找n/m

（假设各子表长度相等）次；而在平均情况下需要查找n/（2m）次。

因此，分块查找的工作量为：

在最坏情况下需要查找log2（m+l）+n/m次，

平均情况下大约需要查找log2（口+1）+n/（2m）次。

当m=n时，线性表L即为有序表，分块查找即为对分查找

当m=l时，线性表L为一般的无序表，分块查找即为顺序查找。

分块查找的效率介于对分查找和顺序查找之间。

structindnode

{intkey；/*数据域，存放子表中的最大值,

intk；/*指针域，指示子表中第一个

元素在线性表中的序号*/

intinserch(intv[],intn,structindnodes[],intm,intx)

{inti,j,t；

i=l;j=m；

while(j-i>l)/*对分查找索引表*/

{t=(i+j)/2；

if(x<=s[t].key)j=t；

elsei=t；

}

if((i!=j)&&(x>s[i].key))i=j；

j=s[i].k；t=n；

if(i!=m)t=s[i+l].k—1；/*确定顺序查找的终点*/

while((j<=t)&&(V[j]!=x))j=j+1；/*顺序查找子表*/

if(j>t)j=-1；

return(j)；

3.2哈希表技术

3.2.1Hash表的基本概念

基本思想：对被查元素的关键字做某种运算后直接确定

所要查找项目在表中的位置。

3.2.2几种常用的Hash表

11.线性Hash表

2.随机Hash表

<3,溢出Hash表

4.拉链Hash表

I5.指标Hash表

3.2.1Hash表的基本概念

1.直接查找技术

设表的长度为n。如果存在一个函数i=i(k),对于表中的任

意一个元素的关键字k,满足以下条件：

(1)KiCn；

(2)对于任意的元素关键字瓦Wk2,恒存在i(kJWiIk?)。

则称此表为直接查找表。

其中函数i=i(k)称为关键字k的映像函数。

对于直接查找表的操作：

⑴直接查找表的填入

要将关键字为k的元素填入到直接查找表，只

需做以下两步：

1)计算关键字k的映象函数i=i(k)；

2)将关键字k及有关元素信息填入到表的第i项。

(2)直接查找表的取出

要在直接查找表中取出关键字k的元素，也只

需做以下两步：

1)升算美键字k的映象函数i=i(k)；

2)检查表中第i项：

若第i项为空，则说明表中没有关键字为k的元

素；

否则取出第i项中的元素即可。

2.Hash表

例

将关键字序列

(09,31,26,19,01,13,02,11,27,16,05,21)

依次填入长度为n=12的表中。

映象函数为i=INT(k/3)+lo

表项序号123<456789101112

®i=INT(k/3)+l01050913161921262731

埴入的关键字k0211

设表的长度为n。如果存在一个函数i=i(k),对于表中的

任意一个元素的关键字k,满足IWiWn,则称此表为

Hash表。

其中函数1=i(k)称为关键字k的Hash码。

Hash表技术的关键是处理表中元素的冲突问题，其工作：

(1)构造合适的Hash码，以便尽量减少表中元素冲突的次数。

即Hash码的均匀性要比较好。

⑵当表中元素发生冲突时，要进行适当的处理。

3.Hash码的构造

(1)使各关键字尽可能均匀地分布在Hash表中，

即Hash码的均匀性要好，以便减少冲突发生的

机会。

⑵Hash码的计算要尽量简单。

Hash码的构造方法：

(1)截段法(数值分析法的一种)

(2)分段叠加法

(3)除法(除留余数法)

i=mod(k,n)

(4)乘法

i=mod(k*0,n)

0一般取0.618033988747,或0.6125423371,

或0.6161616161。

3.2.2几种常用的Hash表

1.线性Hash表

⑴线性Hash表的填入

将关键字k及有关信息填入线性Hash表的步骤如下：

1)计算关键字k的布511码1=i(k)o

2)检查表中第i项的内容：

若第i项为空，则将关键字k及有关信息填入该项；

若第i项不空，则令i=mod(i+l,n),转2)继续检查。

只要Hash表尚未填满，最终总可以找到一个空项，将关

键字

k及有关信息填入到Hash表中。

(2)线性Hash表的取出

要在线性Hash表中取出关键字k的元素，其步骤如下：

1)计算关键字k的Hash码i=i(k)。

2)检查表中第i项的内容：

若第i项登记着关键字k,则取出该项元素即可；

若第i项为空，则表示在Hash表中没有该关键字的信息;

若第i项不空，且登记的不是关键字k,则令

i=mod(i+l,n)

转2)继续检查。

例

将关键字序列

(09,31,26,19,01,13,02,11,27,16,05,21)

依次填入长度为n=12的线性Hash表中。

设Hash码为i=INT(k/3)+1。

表项序号123456789101112

关键字kU10205091311191626273121

冲突次数01100202U004

缺点:

1）在线性Hash表填入的过程中，当发生冲

突时，首先考虑的是下一项，因此，当

Hash码的冲突较多时，在线性Hash表中

会存在“堆聚”现象，即许多关键字被

连续登记在一起，从而会降低查找效率。

2）在线性Hash表的填入过程中，处理冲突

时会带来新的冲突。

2.随机Hash表

(1)随机Hash表的填入

将关键字k及有关信息填入随机Hash表的步骤如下：

1)计算关键字k的Hash码i0=i(k)。且令i=i()。

2)伪随机数序列初始化，令j=l(即将取随机数指针指向

伪随机数序列中的第1个随机数)。

3)检查表中第i项的内容：

若第i项为空，则将关键字k及有关信息填入该项；

若第i项不空,则令i=mod(io+RN(j),n),并令j=j+

1(即将取随机数指针指向下一个随机数)，转3)继续

检查。

其中RN(j)表示伪随机数序列RN中的第j个随机数。

伪随机数序列RN按下列方法产生:

R=1

FORj=lTOnDO

{R=mod(5*R,4n)

RN(j)=INT(R/4)

例

将关键字序列

(09,31,26,19,01,13,02,11,27,16,05,21)

依次填入长度为n=24=16的随机Hash表中。

设Hash码为i=INT(k/3)+1。

伪随机数序列为：

1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0。

表项序号12345678910111213141516

关键字k010205091316192126113127

冲突次数011000000202

(2)随机Hash表的取出

要在随机Hash表中取出关键字k的元素，其步骤如下：

1)计算关键字k的Hash码i0=i(k)。且令i=i()。

2)伪随机数序列初始化，令j=l(即将取随机数指针指向伪

随机数序列中的第1个随机数)。

3)检查表中第i项的内容：

若第i项登记着关键字k,则取出该项元素即可；

若第i项空，则表示在Hash表中没有该关键字信息；

若第i项不空，且登记的不是关键字k,则令

i=mod(i0+RN(j),n),并令j=j+l(即将取随机数指

针指向下一个随机数)，转3)继续检查。

其中RN(j)表示伪随机数序列RN中的第j个随机数。

3.溢出Hash表

溢出Hash表包括Hash表和溢出表两部分。

在Hash表的填入过程中，将冲突的元素顺序填入溢出

表，而当查找过程中发现冲突时，就在溢出表中进行

顺序查找。

溢出表是一个顺序查找表。

(1)溢出Hash表的填入

将关键字k及有关信息填入溢出Hash表的步

骤如下：

1)计算关键字k的Hash码i=i(k)。

2)检查表中第i项的内容：

若第i项为空，则将关键字k及有关信息

填入该项；

若第i项不空，则将关键字k及有关信息

依次填入溢出表中的自由项。

(2)溢出Hash表的取出

要在溢出Hash表中取出关键字k的元素，其步骤如

下：

1)计算关键字k的Hasl^^=i(k)o

2)检查表中第i项的内容：

若第i项登记着关键字k,则取出该项元素即可;

若第i项为空，则表示在Hash表中没有该关键字

信息；

工正;项不空，且登记的不是关键字k,则转入

在溢出表中进行顺序查找。

例

将关键字序列(09,31,26,19,01,13,02,11,27,16,05,21)

依次填入长度为n=12的溢出Hash表中。

设Hash码为i=INT(k/3)+1。

Hash表

1123456789101112

k01050913161921262731

溢出表

1234••・

k0211

4.拉链Hash表

拉链Hash表又分为外链Hash表与内链Hash表。

(1)外链Hash表的填入

将关键字k及有关信息填入外链Hash表的步骤如

下：

1)计算关键字k的Hash码i=i(k)。

2)取得一个新结点p,并将关键字k及有关信息填

入结点P。

3)将结点p链入以H(i)为头指针的链表的链头。

iH(i)

例：z02010

050

将关键字序列(09,31,26,19,30

01,13,02,11,27,16,05,21)4z11090

依次填入长度为n=12的外链Hash表5f13

中。616_0_

设Hash码为i=INT(k/3)+1。7f190_

8

210

9—>260

10—>27_0_

11T310

120

(2)外链Hash表的取出

要在外链Hash表中取出关键字k的元素，其

步骤如下：

1)计算关键字k的Haslr^i=i(k)。

2)在以H(i)为头指针的链表中顺序查找关

键字力k的结点。若找到，则从结点中取

出该元素。

若哈希函数为H,编写在拉链Hash表a中查找关键字为K的数据元素

的算法

typedefstructchain{intkey;intdate;structchain*next;}node;

node*hash_search(node*a口，intk)

{——

node*p;

inti;i=H(k);p=a[i];

while(p!=NULL&&p->key!=k)p=p->next;

if(p==NULL)

{printff'searchingfailed,5);

return(NULL);

)

else

return(p);

设哈希函数为H(k)=kmodll,哈希函数长度为11(地址空间为070)

,给定表(SUN,MON,TUE,WED,TJHU,FRI,SAT)取单词的第一个字母

在英语字母表中的序号为关键字K,构造哈希表，并用拉链法解决

地址冲突。

5.指标Hash表

针对表项空间长度不等的情况。

指标Hash表包括指标表与内容表两部分。

内容表：所有关键字及有关信息。

指标表：表项存放关键字信息在内容表中的地址。

3.3基本的排序技术

3.3.1冒泡排序与快速排序

3.3.2简单插入排序与希尔排序

3.3.3简单选择排序与堆排序

3.3.4其他排序方法简介

3.3.1冒泡排序与快速排序

1.冒泡排序

(1)首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻

两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则

将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将

两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的

最后O

(2)然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较

相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素,

则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断

地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换

到了表的最前面。

(3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此

时的线性表已经变为有序。

输入：无序序列P(Ln)o

输出：有序序列P(Ln)o

PROCEDUREBUBSORT(P,n)

k=1；m=n

WHILE(k<m)DO［子表未空］

{j=m—1；m=0

FORi=kTOjDO［从前往后扫描子表］

IF(p(i)>p(i+l))THEN［发现逆序进行交换］

{d=p⑴;p(i)=p(i+l)；p(i+l)=d；m=i}

j=k+l；k=0

FORi=mTOjBY-1DO［从后往前扫描子表］

IF(p(i-l)>p(i))THEN［发现逆序进行交换］

{d=p⑴;p(i)=p(i—1)；p(i-1)=d；k=i}

RETURN

原序列51731694286

第1遍以前往后）5-<-->17^~~---->69-*~~>4­2**~~>8-*—>6

结果153167428回9

以后往前）15-<~->16—7<*~->4^^>28-<—>69

结果11回326746回；9

第2遍以前往后）115—3—267—4—689

结果111Tl2564叵|789

以后往前）115*--*6*->46789

结果1121Tl456回789

第3遍以前往后）11234566789

最后结果

11•■:*1*./2，.3fk•-4566789

bubsort(intp[],intn)

intm,k,j,i；

intd；

k=0；m=n—1；

while(k<m)/*子表未空*/

{j=m—1；m=0；

for(i=k；i〈=j；i++)/*从前往后扫描*/

if(p：i]>p：i+l])/*发现逆序进行交换*/

{d=p[i]；

p[i]=p[i+l];

p[i+l]=d；

m=i；}

j=k+l；k=0；

for(i=m；i>=j；i--)/*从后往前扫描*/

if(p[i-1]/*发现逆序进行交换*/

{

d=p[i]；

p[i]=p[i-l];

p[i-l]=d；k=i；

return；

2.快速排序

通过一次交换消除多个逆序。

分副

无

序<T

分割—

线--->JL

性

表分割

首先，在表的第一个、中间一个与最后一个元素中选取中

项，

设为P(k),并将P(k)赋给T,再将表中的第一个元素移到

P(k)的位置上。

然后设置两个指针i和j分别指向表的起始与最后的位置。

反复作以下两步：

⑴将j逐渐减小,并逐次比较P(j)与T,直到发现一个

P(j)<T为止,将P(j)移到P(i)的位置上。

(2)将i逐渐增大,并逐次比较P(i)与T,直到发现一个

P⑴〉T为止,将P(i)移到P(j)的位置上。

上述两个操作交替进行，直到指针i与j指向同一个位置

(即i=j)为止，此时将T移到P(i)的位置上。

线性表的分割

输入：待分割的子表P(m：n)o

输出：分割后的分界线位置i。

PROCEDURESPLIT(P,m,n,i)

选取P(k)其中mWkWn

T=P(k)；P(k)=P(m)

i=m；j=n

winjH

1=(J)d

{1一「=「'(Dd=(Dd}

N9HI(r>I)HI

l+!=!OQ(「>I)PUEQW⑴d)miHM

I+I=J，(「)d=(I)d

N3HI(P>I)HI

i—「=「oa(P>i)p™(i^(Dd)aniHM)

oad)miHM

快速排序的递归算法

输入：待排序的子表P(m：n)o

输出：有序子表P(m：n)o

PROCEDUREQKSORT1(P,m,n)

IF(n>m)THEN［子表不空］

{SPLIT(P,m,n,i)；［分割］

QKSORT1(P,m,i—1)；［对前面子表进行快速排序］

QKSORTl(p,i+1,n)；［对后面子表进行快速排序］

RETURN

qksortl(intp[],intm,intn)

{inti；

if(n>m)/*子表不空*/

{i=split(p,m,n)；/*分割*/

qksortl(p,m,i—1)；/*对前子表进行快速排序*/

qksortl(p,i+1,n)；/*对后子表进行快速排序*/

}

return；

staticintsplit(intp[],intm,intn)

/*返回分界线位置*/

{inti,j,k,u；

intt；

i=m—1；j=n—1；k=(i+j)/2；

if((p[i]>=p[j])&&(p[j]>=p[k]))

u=j；/*选取一个元素*/

elseif((p[i]>=p[k])&&(p[k]>=p[j]))u=k；

elseu=i；

t=p[u]；p[u]=p[i]；

while(i!=j)

{while((i<j)&&(p[j]>=t))j=j—1；

if(i<j)

{p[i]=p[j];i=i+l；

while((i<j)&&(p[i]<=t))i=i+l；

if(i<j)

{j=j-1;}

p[i]=t；return(i+1)；

快速排序的非递归算法

输入：待排序的子表P(in：n)0

输出：有序子表P(m：n)0

PROCEDUREQKSORT2(P,m,n)

建立一个栈，并初始化［栈中每一个元素有两个数据项：子表第一个

元素下标与最后一个元素下标］

将下标m与n进栈［子表进栈］

WHILE栈非空DO［还有子表需要分割］

(从栈中退出两个下标m与n［从栈中退出一个子表进行分割］

WHILE(n>m)DO［子表不空］

{SPLIT(P,m,n,i)［进行分割］

将下标i+1与n进栈［将分割出的后一个子表进栈］

n=i-l［对分割出前一个子表继续进行分割］

}

RETURN

习题:利用快速排序方法对一组记录的关键码(54,38,96,23,

15,72,60,45,83)以第一个关键码作为划分基准进行排序,分析

递归调用的过程和每次递归调用是对那一组数据。

初始序列：543896231572604583

第一趟后:453815235472609683

第一次递归调用

第二趟后：233815455472609683

第二次递归调用

第三趟后：152338455472609683

第三次递归调用

第四趟后：152338455460729683

第四次递归调用

第五趟后：152338455460728396

习题:利用快速排序方法对一组记录的关键码(503,87,512,61,908,

170,897,275,653,462)以第一个关键码作为划分基准进行排序,

分析递归调用的过程和每次递归调用是对那一组数据。

初始序列：5038751261908170897275653462

第一趟后：4628727561170503897908653512

第二趟后：1708727561462503897908653512

第三趟后：6187170275462503897908653512

第四趟后：6187170275462503897908653512

第五趟后：6187170275462503512653897908

第六趟后：6187170275462503512653897908

3.3.2简单插入排序与希尔排序

L简单插入排序

将无序序列中的各元素依次插入到已经有序的线

桂行市。

输入：待排序序列P(Ln)o

输出：有序序列P(Ln)o

PROCEDUREINSORT(P,n)

FORj=2TOnDO

{T=P(j)；k=j—1

WHILE(k>0)and(P(k)>T)DO

{P(k+1)=P(k)；k=k+l}

P(k+1)=T

RETURN

II

insort(intp口，intn)

{intj,k；

intt；

for(j=l；j<n；j++)

{t=p[j]；k=j—1；

while((k>=0)&&(p[k]>t))

{p[k+1]=p[k]；k=k—1；

p[k+l]=t；

return；

2.希尔排序

基本思想：将整个无序序列分割成若干小子序列分别进行插入

排序。

子序列的分割方法如下：

将相隔某个增量h的元素构成一个子序列。在排序

过程中，逐次减小这个增量，最后当h减到1时，进

行一次插入排序，排序就完成。

增量序列一般取ht=n/2k(k=l,2,…，[log2n]),

其中n为待排序序列的长度。

6___6___

ZCM

g____

coCO-13

CO____2当

9

了__

co

OO____6-66

CU

送一自一2

g____00―国一"6

LD_00

co巴一

22___3-CT)

区一•区一S-'

cn___00_S-'t-

匕一4后一1£一ir.i

co

II

A

输入：待排序序列P(Ln)o

输出：有序序列P(l：n)o

PROCEDURESHLSORT(P,n)

h—n/2

WHILE(h>0)DO

{FORj=h+lTOnDO

{t=P(j)；i=j—h

WHILE(i>0)and(P(i)>t)DO

{P(i+h)=P⑴;i=i—h}

P(i+h)=t

}

h=h/2

RETURN

voidshlsort(intp[],intn)

{inth,j,i；

ETt；

h=n/2；

while(h>0)

{for(j=h；j<=n—1；j++)

{t=p[j]；i=j-h；

while((i>=0)&&(p[i]>t))

{p[i+h]=p[i]；i=i-h；

p[i+h]=t；

)

h=h/2；

return；

3.3.3简单选择排序与堆排序

1.简单选择排序

原序列8921564885161947

第1遍选择|16|21564885891947

第2遍选择16|19|564885;8921：47

第3遍选择1619|21|4885895647

第4遍选择161921|47|85895648

第5遍选择1619:2147|48|895685

第6遍选择1619：214748|56|8985

第7遍选择161921474856|15|89

输入：无序序列P(Ln)o

输出：有序序列P(Ln)o

PROCEDUDESELESORT(P,n)

FORi=lTOn-1DO

{k=i

FORj=i+lTOnDO

IFP(j)<P(k)THENk=j

IF(kWi)THEN

{d=P⑴;P(i)=P(k)；P(k)=d}

RETURN

selesort(intp口，intn)

{inti,j,k；

intd；

for(i=0；i<=n—2；i=i+l)

{k=i；

for(j=i+l；j<=n—1；j=j+1)

if(ptj]<p[k])k=j；

if(k!=i){d=p[i]；p[i]=p[k]；p

return；

2.堆排序

堆的定义：

具有n个元素的序列(％,h2,hn),

当且仅当满足

hh

li^21+l

(i=l,2,n/2)时称之为堆。

由堆的定义可以看出，堆顶元素

(即第一个元素)必为最大项。

具有n个元素的序列(%,h2,

h1,

当且仅当满足

‘3Vh2i

<

、儿-

h2i+i

(i=b2,n/2)时称之为堆。

实际处理时，可以用一维数组H(l:n)来存储堆序列中

的元素，也可以用完全二叉树来直观表示堆的结构。

序列(91,85,53,36,47,30,24,12)是一个堆

调整建堆

在一棵具有n个结点的完全二叉树(用一维数组

H(Ln)表示)中，假设结点H(m)的左右子树均

为堆，现要将以H(m)为根结点的子树也调整为堆

co

调整建堆

输入：完全二叉树数组H(l：n)o其中结点H(m)的左右子树均为堆。

输出：以H(m)为根结点的子树为堆。

PROCEDURESIFT(H,n,m)

t=H(m)；j=2m

WHILE(jWn)DO

{IF(j<n)and(H(j)<H(j+l))THENj=j+l

IF(t<H(j))THEN

{H(m)=H(j)；m=j；j=2m}

elsej=n+1

)

H(m)=t

RETURN

根据堆的定义，可以得到堆排序的方法：

（1）首先将一个无序序列建成堆。

⑵然后将堆顶元素（序列中的最大项）与堆中最

后一个元素交换（最大项应该在序列的最后）。

不考虑已经换到最后的那个元素，只考虑前

n—1个元素构成的子序列，显然，该子序列已

不是堆，但左、右子树仍为堆，可以将该子序

列调整为堆。

反复做第⑵步，直到剩下的子序列为空为止。

堆排序

输入：无序序列H(Ln)o

输出：无序序列H(Ln)o

PROCEDUREHEAPSORT(H,n)

k=n/2

FORi=kTO1BY-1DO

SIFT(H,n,i)［无序序列建堆］

FORi=nTO2BY-1DO

{t=H⑴;H(l)=H(i)；H(i)=t［堆顶元素换到最后］

SIFT(H,i-1,1)［调整建堆］

RETURN

heapsort(intp[],intn)

{inti,k；

intt；

k=n/2；

for(i=k—1；i>=0；i---)

sift(p,n—1,i)；/*无序序列建堆*/

for(i=n—1；i>=l；i---)

{t=p[0]；p[0]=p[i]；p[i]=t；/*堆顶元素换到最后*/

sift(p,i—1,0)；/*调整建堆*/

return；

staticsift(inth口，intn,intm)

{intj；

ETt；

t=h[m]；j=2*(m+l)—1；

while(j<=n)

{if((j<n)&&(h[j]<h[j+l]))j=j+1；

if(t<h[j])

{h[m]=h[j]；m=j；j=2*(m+1)—1；

elsej=n+1；

)

h[m]=t；

return；

334其他排序方法简介

1.归并排序

将两个或两个以上的有序表合并成一个新的有序表。

设线性表L(l：n)中的某段L(low：high)已经部分有序,

即它的两个子装L(low：mid)与L(mid+1：high)(其

中lowSmidWhigh)已经有序，现要将这两个有序子表

归并成一个有序子表L(low：high)o

实现上述两个子表归并的基本做法如下：

(1)开辟一个与线性表L同样大小的表空间A。

⑵设置三个指针i,j,k,其初始状态分别指向两个有序子

表的首部及表空间A中与L中需要进行排序段相对应空间

的首部。即i=low,j=mid+l,k=low0

⑶沿两个有序子表扫描：

若L⑴WL(j),则A(k)=L⑴，且i与k指针均加1；

否则A(k)=L(j),且j与k指针均加1。

如此反复，直到有一个子表的指针已经指到末端(即子

表内的元素已经取空)为止。

(4)将未取空的子表中的剩余元素依次放入表空间A中。

(5)将A中的对应段复制到L中。

两个相邻有序子表的合并

输入：两个相邻有序子表L(low：mid)与L(mid+Lhigh)

(其中lowWmidWhigh)；工作数组A(low：high)o

输出：有序子表L(low：high)o

PROCEDUREMERGE(L,low,mid,high,A)

i=low,j=mid+l,k=low

WHILE(i^mid)and(jChigh)DO

{IFL(i)<L(j)THEN{A(k)=L(i)；i=i+l}

ELSE{A(k)=L(j)；j=j+1}

k=k+l

IF(iCmid)THEN

{FORj=iTOmidDO{A(k)=L(j)；k=k+l}

ELSE

{IF(jWhigh)THEN

FORi=jTOhighDO

{A(k)=L(i)；k=k+l}

}

FORi=lowTOhighDOL(i)=A(i)

RETURN

排序前(⑼(⑶(05)如(01)⑸⑶)(⑹

II4I

(⑶⑼95,27)(0326)(旧31)

II

(053339,27)91,16」26,31)

I

(01,05,13,16i19,26,27J31)

,,••.1•|•*\•.•,-'-.••••***4»*•/.

归并排序的非递归算法

输入：无序序列P(Ln)o

输出：有序序列P(Ln)o

PROCEDUREMERGSORT(P,n)

定义工作数组A(1：n)

m=1

WHILE(m<n)DO

{k=2m

FORj=lTOnBYkDO

{low=j；high=j+k—1；mid=j+m—1

IF(high>n)THENhigh=n

IF(high>mid)THEN

MERGE(P,low,mid,high,A)

}

m=k

RETURN

ttinclude〃stdlib.h〃

mergsort(intp口，intn)

{intm,k,j,low,high,mid；

ET*a；

a=malloc(n*sizeof(int))；

m=1；

while(m<n)

{k=2*m；

for(j=l；j<=n；j=j+k)

{low=j；high=j+k—1；mid=j+m—1；

if(high>n)high=n；

if(high>mid)

merge(p,low,mid,high,a)；

}

m=k；

free(a)；

return；

staticmerge(intp口，intlow,intmid,inthigh,inta口)

{inti,j,k；

i=low；j=mid+l；k=low；

while((i<=mid)&&(j<=high))

{if(p[i—1]<=p[j—1])

{a[k—1]=p[i­1]；i=i+l；}

else

{a[k-1]=p[j-1]；j=j+1；}

k=k+l；

if(i<=mid)

for(j=i；j<=mid；j++)

{a[k—1]=p[j—1]；k=k+l；}

else

{if(j<=high)

{for(i=j；i<=high；i++)

{a[k—1]=p[i­1]；k=k+l；

}

)

for(i=low；i<=high；i++)

p[i—1]=a[i—1]；

return；

2基数排序

设线性表中各元素的关键字具有k位有效数字,

则基数排序的基本思想是：

从有效数字的最低位开始直到最高位，对于每

一位有效数字对线性表进行重新排列，其调整

的原则为：

(1)将线性表依当前位的有效数字为序排列；

(2)当前位的有效数字相同时，按原次序排歹人

这种基数排序法称为最低位优先法

(LSD---LeastSignificantDigitfirst)

排序前按末位排序连接按首位排序连接

19(0)01(0)01,02,05,0901

13(1)01,31,11,2131(1)11,13,16,1902

05C2)0211(2)21,26,2T05

27(3),1321(3)31'09

01(4工02:⑷11

•IS.V-*

26⑸0513；(5)；13

31(6)26,1605(6)16

16CT)2726CT)19

02(8)：16：(8)：21

09(9)19,0927(9)；26

1119”；27

210931

基数排序的最高位优先法

(MSD----MostSignificantDigitfirst)。

在这种方法中，是从有效数字的最高位开始直

到最低位进行调整。在这种情况下，必须将线

性表按有效位从高到低逐层分割成若干子表，

然后对各子表独立进行排序。

冒泡排序n(n—1)/2

快速排序n(n—1)/2

简单插入排序n(n—1)/2

希尔排序0(nL5