第3章查找与排序技术大字黑体

第3章查找与排序技术3.1基本的查找技术3.2哈希表技术3.3基本的排序技术3.4二叉排序树及其查找3.5多层索引树及其查找3.6拓扑分类13.1基本的查找技术3.1.1顺序查找3.1.2有序表的对分查找3.1.3分块查找2

所谓查找是指在一个给定的数据结构中查找某个指定的元素。查找的效率将直接影响到数据处理的效率。通常，根据不同的数据结构，应采用不同的查找方法。33.1.1顺序查找顺序查找又称顺序搜索。其基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示查找成功；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，即查找失败。4算法3.1：在顺序表中顺序查找元素X的下标K输入：线性表长度n

线性表的存储空间V；被查找的元素x。输出：元素x在线性表中的序号k。如果表中不存在元素x，则k＝－1。5算法：顺序表的顺序查找PROCEDURESERCH(V，n，x，k)k＝1

WHILE(k≤n)and(V(k)≠x)DOk＝k＋1IF(k＝n＋1)THENk＝－1RETURN6C语言描述：顺序表的顺序查找/*函数返回被查找元素x在线性表中的序号，如果在线性表中不存在元素值x，则返回－1*/int

serch(ETv[]，intn，ETx){intk＝0；

while((k＜n)&&(v[k]≠x))k＝k＋1；

if(k＝＝n)k＝－1；

return(k)；}7算法3.2：链表的顺序查找输入：线性链表头指针HEAD

存储空间V、NEXT；被查找的元素x。输出：元素x的结点在线性链表中的存储序号k。如果链表中不存在元素x

的结点，则k＝－1。

8链表的顺序查找PROCEDURELSERCH(V，NEXT，HEAD，x，k)k＝HEAD

WHILE(k≠0)and(V(k)≠x)DOk＝NEXT(k)IF(k＝0)THENk＝－1RETURN9C描述：链表的顺序查找/*函数返回被查找元素x所在结点的存储地址，如果在线性链表中不存在元素值为x的结点，则返回NULL*/structnode{ETd；

structnode*next；}；structnode*lserch(head，x)structnode*head；ETx；10C描述：链表的顺序查找{structnodek；

k＝head；

while((k≠NULL)&&(k－>d≠x))k＝k－>next；

return(k)；}11对顺序查找法的分析在平均情况下，在线性表中顺序查找一个元素，大约要与线性表中一半的元素进行比较。对于大的线性表来说，顺序搜索的效率是很低的。但在下列两种情况下，只能采用顺序查找：12必须采用顺序查找的两种情况：(1)如果线性表为无序表（即表中元素的排列是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。133.1.2有序表的对分查找对分查找只适用于顺序存储的有序表。本书所说的有序表均指元素按值非递减排列的线性表。非递减排列即从小到大排列，但允许相邻元素相等。14对分查找算法：设有序表长度为n，被查元素为x。将X与线性表的中间项进行比较，分为三种情况：（1）若x等于中间项的值，则说明查到，查找结束；（2）若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；15对分查找算法：（3）若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。

16对分查找法的效率对分查找的效率比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，对分查找只需比较log2n次，而顺序查找需比较n次。17算法3.3有序线性表在顺序存储结构下的对分查找输入：有序线性表长度n

线性表的存储空间V；被查找的元素x。输出：被查找元素x在有序线性表中的序号k。如果在线性表中不存在元素x，则输出k＝－1。18算法3.3有序线性表在顺序存储结构下的对分查找PROCEDUREBSERCH(V，n，x，k)i＝1；j＝nWHILE(i＜＝j)DO{k＝(i＋j)/2IF(V(k)＝x)THENRETURN

IF(V(k)＞x)THENj＝k－1；

ELSEi＝k＋1；}IF(i＞j)THENk＝－1RETURN19算法3.3的C语言描述：

/*函数返回被查找元素x在线性表中的序号,如果在线性表中不存在元素值x，则返回－1*/20算法3.3的C语言描述：int

bserch(ETv[]，n，ETx){inti，j，k；

i＝1；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＋1；}return(－1)；}21m=（L+h）/2；if(key

>a[m].key)L=m+1；elseif(key<

a[m].key)h=m–1；elsefinditem,break;mLh223.1.3分块查找分块查找又称索引顺序查找。它是一种顺序查找的改进方法，用于在分块有序表中进行查找。23分块有序表将长度为n线性表分成m个子表（即分块），各子表的长度可以相等，也可以互相不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素（有序）。24分块有序表的结构

分块有序表的结构可分为两部分：(1)线性表本身,采用顺序存储结构。(2)索引表。在索引表中，为线性表的每个子表建立一个索引结点，索引结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，指示对应子表的元素在整个线性表中的第一个存储位置。25

下图是将一个长度为n＝18的线性表,分成m＝3个子表的

分块有序表示意图。26分块有序表的查找过程：分块有序表的查找过程可分为两步进行：(1)首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的，因此可以采用对分查找。(2)然后在相应的子表中用顺序查找法进行具体的查找。27算法分析：分块查找法在索引表中使用对分查找法，在最坏情况下需要查找log2(m＋1)次。在子表中用顺序查找法，在最坏情况下需要查找n/m（假设各子表长度相等）次；而在平均情况下需要查找n/(2m)次。28算法分析：分块查找法（续）因此，分块查找的工作量为：在最坏情况下需要查找log2(m＋1)＋n/m次，平均情况下大约需要查找log2(m＋1)＋n/(2m)次。29分析：分块查找法（续）当m＝1时，线性表L为一般的无序表，分块查找即为顺序查找。当m＝n时，线性表L即为有序表，分块查找即为对分查找分块查找的效率介于对分查找和顺序查找之间。303.2哈希表技术3.2.1Hash表的基本概念3.2.2几种常用的Hash表313.2.1Hash表的基本概念前述顺序查找、二分查找、分块查找等查找方法，都是通过比较达到查找的目的。本节介绍的哈希（Hash）表技术的基本思想是通过对被查元素的关键字做某种运算后直接确定所要查找的项目在表中的位置。在介绍hash表之前，先了解“直接查找表”。321.直接查找技术设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足以下条件：

(1)1≤i≤n；

(2)对于任意的元素关键字

k1≠k2，恒存在i(k1)≠i(k2)。

则称此表为直接查找表。其中函数i＝i(k)称为关键字k的映象函数。33(1)直接查找表的填入

对直接查找表的数据操作主要有两种：填入和取出。要将关键字为k的元素填入到直接查找表，只需做以下两步：

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

2)将关键字k及有关元素信息填入到表的第i项。34(2)直接查找表的取出要在直接查找表中取出关键字k的元素，也只需做以下两步：

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

2)检查表中第i项：

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

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

35元素存储位置的冲突：在直接查找表中，提出了要求：若k1≠k2，则恒存在i(k1)≠i(k2)

。即不允许元素的存储位置发生冲突。

但这一要求往往很难满足。36冲突根源：从较大的关键字空间映射到较小的地址空间元素冲突的例子：例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)

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

映象函数为i＝INT(k/3)＋1。372.Hash表

Hash表技术是直接查找技术的推广，其主要目标是提高查找效率。在Hash表中允许冲突存在。Hash表技术的关键就是要处理好表中元素的冲突问题。38Hash表的定义：设表的长度为n。如果存在一个函数i＝i(k)，对于表中的任意一个元素的关键字k，满足1≤i≤n，则称此表为Hash表。其中映像函数i＝i(k)称为关键字k的Hash码。39Hash表技术的关键：

Hash表技术的关键就是要处理好表中元素的冲突问题，包括两方面的工作：(1)构造合适的Hash码，以便尽量减少表中元素冲突的次数。即Hash码的均匀性要比较好。(2)当表中元素发生冲突时，要进行适当的处理。403.Hash码的构造在设计Hash码时，要考虑两个方面的因素：(1)使各关键字尽可能均匀地分布在Hash表中，即Hash码的均匀性要好，以便减少冲突发生的机会。(2)Hash码的计算要尽量简单，以减轻查找时的计算工作量，提高查找效率。（矛盾统一于追求效率）41构造Hash码的一些简单方法(1)截段法：截取关键字数字串的一段（一般选低几位）作为该关键字的Hash码。(2)分段叠加法：将关键字的编码串分割成若干段，叠加后再进行截段。(3)除法：i＝mod(k，n)均匀性较好，但需做一次除法。(4)乘法：关键字与常数φ相乘后用除法i＝mod(k*φ，n)，或用截段法。φ一般取0.618033988747，或0.6125423371，或0.6161616161。42构造Hash码构造Hash码的方法很多，用户可根据具体情况自行设计。再经过反复的试验、修改，从而得到均匀性好、计算简单的Hash码。

433.2.2几种常用的Hash表当元素发生冲突时，采用不同的处理方法就得到不同的Hash表。

1.线性Hash表

是一种最简单的Hash表。当线性Hash表发生冲突时，首先考虑紧邻的下一个存储位置。44(1)线性Hash表的填入将关键字k及有关信息填入线性Hash表的步骤如下：1)计算关键字k的Hash码i＝i(k)。2)检查表中第i项的内容：若第i项为空，则将关键字k及有关信息填入该项；若第i项不空，则令i＝mod(i＋1，n)，转2)继续检查。只要Hash表尚未填满，最终总可以找到一个空项，将关键字k及有关信息填入到Hash表中。45(2)线性Hash表的取出要取出关键字k的元素，其步骤如下：1)计算关键字k的Hash码i＝i(k)。2)检查表中第i项的内容：若第i项登记着关键字k，则取出该项元素即可；若第i项为空，则表示在Hash表中没有该键字的信息；若第i项不空，且登记的不是关键字k，则令i＝mod(i＋1，n)转2)继续检查。46例将关键字序列

(09，31，26，19，01，13，

02，11，27，16，05，21)

依次填入长度为n＝12的线性Hash表中。设Hash码为i＝INT(k/3)＋1。47线性Hash表的缺点：1)在线性Hash表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当Hash码的冲突较多时，在线性Hash表中会存在“堆聚”现象，即许多关键字被连续登记在一起，从而会降低查找效率。2)在线性Hash表的填入过程中，处理冲突时会带来新的冲突。482.随机Hash表如果发生元素冲突时，表项序号i的改变不采用“加1取模”的方法，而是加上某种伪随机数，这样就形成了随机Hash表。49

伪随机数序列RN[j]按下列方法产生：（j为冲突次数）

R＝1FORj＝1TOnDO

{R＝mod(5*R，4n)

RN[j]＝INT(R/4)

}

随机Hash表的填入和取出应采用同一个伪随机序列。50例将关键字序列(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。513.溢出Hash表前述的线性Hash表和随机Hash表均存在一个缺点：在填入过程中不顾后效，冲突的元素仍然被填入到Hash表的存储空间中，而又无法预测被占用的空间以后是否有元素正常填入，从而填入过程中冲突的机会不断增多。52溢出Hash表如果将冲突的元素安排在另外的空间里，而不占用hash表本身的空间，则就不会产生新的冲突。这就是溢出Hash表。53溢出Hash表溢出Hash表包括Hash表和溢出表两部分。

在Hash表的填入过程中，将冲突的元素顺序填入溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。

溢出表是一个顺序查找表。54例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的溢出Hash表中。设Hash码为i＝INT(k/3)＋1。55溢出Hash表的效率在Hash码比较均匀、冲突不多的情况下，溢出表中实际上只有很少几项，即使采用顺序查找，效率也不会很低。564.拉链Hash表拉链Hash表是一种最常用又最有效的Hash表。拉链Hash表可由Hash表及表外结点组成。在Hash表内存放的并不是关键字K及相关信息，而是指针。57拉链Hash表所有的关键字K及有关信息分别被存储在表外各结点中。每一个表外结点还含有一个指针域，用以链接Hash码相同的其他结点，形成单链表。

Hash表内第i项存放的指针，指向所有关键字的hash码为i的表外结点组成的单链表。58例将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为n＝12的外链Hash表中。设Hash码为i＝INT(k/3)＋1。59新的结点链接到链头在填入关键字k及有关信息的过程中，一般总是将新的结点链接到相应链表的链头，而不是链接到链尾。这样处理的优点是速度快，并且在实际应用中，往往是后填入的结点使用频率比先填入的高，因此，这种处理也能提高查找效率。603.3基本的排序技术3.3.1冒泡排序与快速排序3.3.2简单插入排序与希尔排序3.3.3简单选择排序与堆排序3.3.4其他排序方法简介61什么是排序？排序也是数据处理的重用内容。所谓排序是指将一个无序序列整理成按值递增（或递减）排列的有序序列。排序可以在各种存储结构上实现。本节介绍的排序对象一般认为是顺序存储的线性表，在程序设计语言上就是一维数组。62排序算法一般的评价依据平均的比较次数元素搬移的次数需要的辅助空间算法的稳定性：

对相同排序码的元素之间相对位置的维持12，10，11，10，1510，10，11，12，1510，10，11，12，15633.3.1冒泡排序与快速排序冒泡排序与快速排序属于互换类的排序方法。

所谓互换排序是指借助数据元素之间的互相交换进行排序的一种方法。641.冒泡排序基本思想：逐个交换次序不当的相邻表项，多趟扫描后得到排序表319241310交换192交换194交换13191019交换65冒泡排序的基本过程(1)首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大小。若前面的元素大于后面的元素，则将它们互换，称之为消去一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。这也是线性表中最大元素应有的位置。66冒泡排序的基本过程(2)然后从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。67冒泡排序的基本过程(3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。在上述排序过程中，对线性表的每一次来回扫描，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名（又称下沉排序）。68算法3.5对无序序列P(1:n）

进行冒泡排序输入：无序序列P(1：n)。输出：有序序列P(1：n)。

69PROCEDUREBUBSORT(P，n)[双向冒泡排序]k＝1；m＝n[子表为P(k,m)]WHILE(k＜m)DO[子表未空就循环下去]{j＝m－1；m＝0FORi＝kTOjDO[从前往后扫描子表]

IF(p(i)＞p(i＋1))THEN[发现逆序进行交换]

{d＝p(i)；p(i)＝p(i＋1)；p(i＋1)＝d；m＝i}

j＝k＋1；k＝n

[技巧:进一步减小运算量↑↓]

FORi＝mTOjBY－1DO[从后往前扫描子表]

IF(p(i－1)＞p(i))THEN[发现逆序进行交换]

{d＝p(i)；p(i)＝p(i－1)；p(i－1)＝d；k＝i}

}[endwhile]

RETURN70有方框的位置表示扫描过程中最后一次发生交换的位置。71bubsort(p，n)/*双向冒泡排序程序*/intn；ETp[]；{intm，k，j，i；

ETd；

k＝0；m＝n－1；

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

{j＝m－1；m＝0；

for(i＝k；i＜＝j；i＋＋)/*从前往后扫描*/

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

{d＝p[i]；p[i]＝p[i+1]；p[i+1]＝d；

m＝i；}j＝k＋1；k＝n－1；//书上印错为k＝0

for(i＝m；i＞＝j；i－－)/*从后往前扫描*/

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

{d＝p[i]；p[i]＝p[i-1]；p[i-1]＝d；k＝i；}

}

return；

}72冒泡排序的效率分析假设线性表长度为n，则在最坏情况下，冒泡排序需要经过n/2遍从前往后的扫描以及n/2遍从后往前的扫描，需要的比较次数为n(n-1)/2。

一般情况下要小于这个工作量。对于基本有序的序列，效率较高。如图3.3所示的例子只用了两遍扫描就完成了。732.快速排序快速排序也是一种互换式的排序方法，又称为分区交换排序。由于它比冒泡排序速度快，因此称为快速排序。74理解:快速排序思想kki

<kk<kjk两端的子表不一定有序基本思想：从表中任意选取一个元素(一般取第一个)，把它放在排序表中它应该在的位置。75112942420ijT：13611快速排序过程演示76快速排序快速排序的基本思想如下：从线性表中选取一个元素，设为T。然后将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处。这个过程称为分割。77快速排序

分割后以T为分界线，将线性表分成了前后两个子表，且前面子表的所有元素均不大于T，而后面子表中的所有元素均不小于T。对分割后的各子表再按上述原则进行分割，直到所有子表为空为止，此时线性表就变成了有序表。78快速排序过程图解79实际分割的步骤：首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。（第一个位置为“空”。）

然后设置两个指针i和j分别指向表的起始与最后的位置。80实际分割的步骤：反复作以下两步：(1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)＜T为止，将P(j)移到P(i)的位置上。(2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)＞T为止，将P(i)移到P(j)的位置上。81实际分割的步骤：上述两个操作交替进行，直到指针i与j指向同一个位置（即i＝j）为止，此时将T移到P(i)的位置上。至此完成一次分割。

82112942420ijT：13611快速排序过程演示83算法：线性表的分割算法（自学）输入：待分割的子表P(m：n)。

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

PROCEDURESPLIT(P，m，n，i)

选取P(k)其中m≤k≤n

T＝P(k)；P(k)＝P(m)

i＝m；j＝n84WHILE(i≠j)DO{WHILE(P(j)≥T)and(i＜j)DOj＝j－1

IF(i＜j)THEN

{P(i)＝P(j)；i＝i＋1

WHILE(P(i)≤T)and(i＜j)DOi＝i＋1

IF(i＜j)THEN

{P(j)＝P(i)；j＝j－1}

}}

P(i)＝TRETURN85快速排序的递归算法

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

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

PROCEDUREQKSORT1(P，m，n)

IF(n＞m)THEN[子表不空]

{SPLIT(P，m，n，i)；[分割]

QKSORT1(P，m，i－1)；[对前面子表进行快速排序]

QKSORT1(p，i＋1，n)；[对后面子表进行快速排序]

}

RETURN86

qksort1(p，m，n)

intm，n；ETp[]；

{inti；

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

{i＝split(p，m，n)；/*分割*/

qksort1(p，m，i－1)；/*对前子表进行快速排序*/

qksort1(p，i＋1，n)；/*对后子表进行快速排序*/

}

return；

}87

staticintsplit(p，m，n)/*返回分界线位置*/

intm，n；ETp[]；

{inti，j，k，u；

ETt；

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]；88while(i!＝j)

{while((i＜j)&&(p[j]＞＝t))j＝j－1；

if(i＜j)

{p[i]＝p[j]；i＝i＋1；

while((i＜j)&&(p[i]＜＝t))i＝i＋1；

if(i＜j)

{p[j]＝p[i]；j＝j－1；}

}

}

p[i]＝t；return(i)；

}89快速排序的非递归算法输入：待排序的子表P(m：n)。输出：有序子表P(m：n)。

PROCEDUREQKSORT2(P，m，n)

建立一个栈，并初始化[栈中每一个元素有两个数据项：子表第一个元素下标与最后一个元素下标]

将下标m与n进栈[子表进栈]

WHILE栈非空

DO[还有子表需要分割]

{从栈中退出两个下标m与n[从栈中退出一个子表进行分割]

WHILE(n＞m)DO[子表不空]

{SPLIT(P，m，n，i)[进行分割]

将下标i＋1与n进栈[将分割出的后一个子表进栈]

n＝i－1[对分割出前一个子表继续进行分割]

}

}

RETURN90性能分析：快速排序从平均时间性能来看，快速排序最佳，其时间复杂度为O(nlog2n)。但在最坏情况下，即对几乎是排好序的输入序列，该算法的效率很低，近似为O(n2)。另外，该算法对较大的n值效果较好。在对于关键值无序时的多种排序方法中，快速排序被认为是一种最好的排序方法。913.3.2简单插入排序与希尔排序

插入排序的基本思想是：每步将一个待排序序列的元素按其关键字的大小插入到已经排好序的序列中的适当位置，直到全部记录插入完毕为止。常用的插入排序方法有简单插入排序、折半插入排序、希尔排序等。921.简单插入排序线性表中，仅仅包含第1个元素的子表显然是有序表。然后，从第2个元素开始直到最后一个元素，逐次把每个元素插入到前面已经有序的子表中，就完成了排序。31429351731694286

↑j＝215731694286

↑j＝3157

31694286

↑j＝413571694286

↑j＝511357694286

↑j＝611356794286

↑j＝711356794286

↑j＝811345679286

↑j＝99411234567986

↑j＝1011234567896

↑j＝1111234566789如果寻找在有序表中的插入位置时，使用二分查找，就形成了改进的插入排序方法：折半插入排序95算法3.9简单插入排序输入：待排序序列P(1：n)。

输出：有序序列P(1：n)。

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＋1}

P(k＋1)＝T

}

RETURN96C语言描述：简单插入排序

insort(p，n)

intn；ETp[]；

{intj，k；

ETt；

for(j＝1；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＋1]＝t；

}

return；

}97算法分析：简单插入排序在简单插入排序中，每一次比较后最多去掉一个逆序，因此，这种排序方法的效率与冒泡排序相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。从空间来看，只需占用一个元素的附加空间。O(1)982.希尔排序（缩小增量排序法）基本思想是：在整个无序序列中，将相隔增量h的元素构成一个子序列，在每个子序列分别进行插入排序。然后减小增量h的值，重复以上过程。直到增量h减为1时，所有元素合成一组，再进行一次插入排序，排序完成。增量序列可取hk＝n/2K，

k＝1,2,3，…

其中n为待排序序列的长度。99希尔排序示意图100算法：3.10希尔排序（自学）输入：待排序序列P(1：n)。

输出：有序序列P(1：n)。

PROCEDURESHLSORT(P，n)

h＝n/2WHILE(h＞0)DO

{FORj＝h＋1TOnDO

{t＝P(j)；i＝j－h

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

{P(i＋h)＝P(i)；i＝i－h}

P(i＋h)＝t

}

h＝h/2

}

RETURN101C语言描述：希尔排序算法（自学）

shlsort(p，n)

intn；ETp[]；

{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；

}102算法分析：希尔排序在希尔排序中，在子表中进行的每一次比较都有可能去除掉整个线性表的多个逆序，从而改善了整个排序的性能。103算法分析：希尔排序希尔排序是一个复杂问题，到目前为止还没有找到一种最好的增量序列。通过大量试验证实，希尔排序的时间复杂度为O(nlog2n)。其空间复杂度仍为O(1)。1043.3.3简单选择排序与堆排序1.简单选择排序基本思想：从无序表中选出最小的元素，把它交换到表的最前面，然后对剩下的子表采用相同的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n－1遍。3142已排序子表未排序子表105简单选择排序例子106算法3.11对无序序列P(1:n)进行简单选择排序输入：无序序列P(1：n)。输出：有序序列P(1：n)。

PROCEDUDESELESORT(P，n)

FORi＝1TOn－1DO

{k＝i

FORj＝i＋1TOnDO

IFP(j)＜P(k)THENk＝j

IF(k≠i)THEN{d＝P(i)；P(i)＝P(k)；P(k)＝d}

}

RETURN107C语言描述：简单选择排序算法

selesort(p，n)

intn；ETp[]；

{inti，j，k；

ETd；

for(i＝0；i＜＝n－2；i＝i＋1)

{k＝i；

for(j＝i＋1；j＜＝n－1；j＝j＋1)

if(p[j]＜p[k])k＝j；

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

[k]＝d；}

}

return；

}108算法分析：简单选择排序简单选择排序算法的主要部分是二重for循环，需要比较n(n-1)/2次，时间复杂度为O(n2)。简单选择算法简单、直观，对于小规模的无序表是一种很常用的排序方法。109简单插入与简单选择算法比较：简单插入算法搬移元素的次数较多。简单选择算法比较元素的次数较多，但搬移次数少。对于一个基本有序的表，倾向使用

算法对于一个顺序混乱的表，倾向使用

算法简单插入简单选择例：1234576110堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。503845402836322018281.大根堆的根结点是所有结点的最大者。2.较大结点靠近根结点，但不绝对。2.堆排序（自学）111首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。需解决的关键问题?⑴如何由一个无序序列建成一个堆（即初始建堆）？⑵如何处理堆顶记录？⑶如何调整剩余记录，成为一个新堆（即重建堆）？堆排序基本思想1123.3.4其他排序方法简介1.归并排序

是将两个或两个以上有序序列合并成一个有序序列的过程。

基本思想：若序列有n个元素，则看成n个子序列，先将每相邻的两个子序列合并，得到n/2个子序列，再两两合并，如此反复，直到最后合成一个有序序列。1131142.基数排序基本思想是：设线性表中各元素的关键字具有k位有效数字，从有效数字的最低位开始直到最高位，按每一位有效数字对线性表进行重新排列。115116应该从以下几个方面综合考虑：⑴时间复杂性；⑵空间复杂性；⑶稳定性；⑷算法简单性；⑸待排序记录个数n的大小；⑹记录本身信息量的大小；⑺关键码的分布情况。各种排序方法的比较117排序方法最坏情况平均情况最好情况直接插入排序O(n2)O(n2)O(n)希尔排序O(n2)O(nlog2n)O(n1.3)起泡排序O(n2)O(n2)O(n)快速排序O(n2)O(nlog2n)O(nlog2n)简单选择排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)归并排序O(nlog2n)O(nlog2n)O(nlog2n)时间复杂度比较118排序方法辅助空间直接插入排序O(1)希尔排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)简单选择排序O(1)堆排序O(1)归并排序O(n)空间复杂度比较119所有排序方法可分为两类，（1）一类是稳定的，包括直接插入排序、起泡排序、直接选择排序和归并排序；（2）另一类是不稳定的，包括希尔排序、快速排序和堆排序。稳定性比较120从算法简单性看，（1）一类是简单算法，包括直接插入排序、直接选择排序和起泡排序，（2）另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。算法简单性比较121从待排序的记录个数n的大小看，n越小，采用简单排序方法越合适，n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。待排序的记录个数比较122排序方法最好情况最坏情况平均情况直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)直接选择排序0O(n)O(n)记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。记录本身信息量比较1233.4二叉排序树及其查找3.4.1二叉排序树及其构造3.4.2二叉排序树查找124二叉排序树的作用：前面提到，对分查找的效率比顺序查找高，但是只能用于顺序存储的有序表。本节介绍一种对于无序表的查找方法，当采用了一种合适的存储结构后，其查找效率与有序表的对分查找基本接近，这就是二叉排序树查找。1253.4.1二叉排序树及其构造所谓二叉排序树是指满足下列条件的二叉树：

(1)左子树上的所有结点值均小于根结点值；

(2)右子树上的所有结点值均不小于根结点值；

(3)左、右子树也满足上述两个条件。126例如：结点值为数字的二叉排序树127例如：结点值为字母的二叉排序树128构造二叉排序树

依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根结点；(2)若读入的元素值小于根结点值，则将元素插入到左子树中；(3)若读入的元素值不小于根结点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。129例：二叉排序树的构造如学生成绩分别为71、65、40、88、67、90、60、70、77……，建立二叉排序树。716540886790607077130注意：构造形态不唯一对于同一组元素，如果读入的顺序不同，构造出的二叉排序树形态也不同。（第一个读入的就是根结点）131二叉排序树的特性：中序遍历二叉排序树可以得到有序序列。因此，由无序序列构造二叉排序树的过程，实际上就是将一个无序序列变成有序序列的过程。由于插入的新结点都是叶子结点，所以在插入运算时不需要移动其他结点，效率较高。132算法：由无序序列构造二叉排序树（自学）输入：长度为n的无序序列A(1：n)。输出：二叉排序树的头指针BT。PROCEDUREINBSORT(A，n，BT)BT＝0FORk＝1TOnDO{NEW(p)[取得一个新结点]V(p)＝A(k)；L(p)＝0；R(p)＝0j＝BTIF(j＝0)THENBT＝p[若二叉排序树为空]ELSE[二叉排序树不空]133

{WHILE(L(j)≠p)and(R(j)≠p)DO[未到叶子结点]{IF(A(k)＜V(j))THEN[插入到左子树]{IF(L(j)≠0)THENj＝L(j)ELSEL(j)＝p}ELSE[插入到右子树]{IF(R(j)≠0)THENj＝R(j)ELSER(j)＝p}}}}RETURN134#include"stdlib.h"/*malloc

函数需要包含头文件stdlib.h*/struct

btnode