当 α 比较小时，关键字碰撞的几率比较小，一般情况下只要按照散列函数计算出的结果能 够 1 次性就找到相应结点，因此它的平均查找时间接近于 1.

3．画出对长度为 18 的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功 的平均查找长度，以及查找失败时所需的最多的关键字比较次数。
 
答：如图：

 

答：请看题图。 等概率情况下，查找成功的平均查找长度为
： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556
也可以用公式代，大约为：ASL=(18+1)lg(18+1)/18-1=3.346 查找失 败时，最多的关键字比较次树不超过判定树的深度，此处为 5.

六、内部排序

大纲要求：

（一） 排序的基本概念
（二） 插入排序
1. 直接插入排序
2. 折半插入排序
（三） 起泡排序（bubble sort）
（四） 简单选择排序
（五） 希尔排序（shell sort）
（六） 快速排序
（七） 堆排序
（八） 二路归并排序（merge sort）
（九） 基数排序
（十） 各种内部排序算法的比较
（十一） 内部排序算法的应用 知识点：
 
1．插入类排序的基本思想是假定待排序文件第一个记录有序，然后从第二个记录起，依 次插入到排好序的有序子文件中，直到整个文件有序。从减少比较次数和移动次数进行 了各种改进，在插入排序中有直接插入、折半插入、希尔排序。直接插入是依次寻找，折 半插入是折半寻找，希尔排序是通过控制每次参与排序的数的总范围“由小到大”的 增量来实现排序效率提高的目的。
2．交换类排序基于相邻记录比较，若逆序则进行交换。起泡排序和快速排序是交换排序 的例子，在起换排序的基础上改进得到快速排序，快速排序是目前最好的内部排序法。 快速排序的思想：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模” 这个概念上，与希尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理 的规模降低，最终达到排序的目的。
3．选择类排序，可以分为：简单选择排序、堆排序。这两种方法的不同点是，根据什么规 则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；堆排序，是利用 堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶 堆排序较为重要，其最差性能比快速排序的最差性能好。
4．归并排序是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的 数据集合才可能实现归并，算法思想比较简单。
5．基数排序，是一种特殊的排序方法，分为两种：多关键字的排序（扑克牌排序），链 式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模 规范、变小，在排序的过程中，只要按照基数排序的思想，是不用进行关键字比较的， 这样得出的最终序列就是一个有序序列。
6．掌握各种排序方法的算法思想以及算法实现。掌握在最好、最坏、平均情况下各种排序 方法的性能分析。归并排序、基数排序及时间复杂度为 O(n2)的排序是稳定排序，而希尔 排序、快速排序、堆排序等时间性能好的排序方法是不稳定排序（但特别注意，简单选 择排序是不稳定排序）。 各种排序方法的综合比
较
（1）时间性能
●按平均的时间性能来分，有三类排序方法：
时间复杂度为 O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为 最好；
时间复杂度为 O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入 为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为 O(n)的排序方法只有，基数排序。
●当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到 O(n)的时间复杂 度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为 O(n2)，因此是应该 尽量避免的情况。
●简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
（2）空间性能：指的是排序过程中所需的辅助空间大小。
●所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为
O(1)；
●快速排序为 O(logn)，为栈所需的辅助空间;
●归并排序所需辅助空间最多，其空间复杂度为 O(n);
●链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。
（3）排序方法的稳定性能
 
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排 序之前和经过排序之后，没有改变。
当对多关键字的记录序列进行 LSD 方法排序时，必须采用稳定的排序方法。 对于不稳定的 排序方法，只要能举出一个实例说明即可。 快速排序和堆排序是不稳定的排序方法。

练习题：

（一）选择题：

1.    下列四个序列中，哪一个是堆（ C ）
A. 75,65,30,15,25,45,20,10    B. 75,65,45,10,30,25,20,15
C. 75,45,65,30,15,25,20,10    D. 75,45,65,10,25,30,20,15
2.    下列排序算法中，在最好情况下，时间复杂度为 O(n)的算法是（    D    ）。
A．选择排序    B．归并排序
C．快速排序        D．冒泡排序 3.    下述排序算法中，稳定的是（ B    ）。
A. 直接选择排序    B．基数排序
C．快速排序    D．堆排序
4.    下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是
（    D    ）
A．归并排序    B．直接插入排序
C．快速排序    D．冒泡排序
5.         如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用（    D    ）方法最 快。
A．起泡排序    B．快速排序
C．堆排序    D．直接选择排序
6.    下面给出的 4 种排序方法中，排序过程中的比较次数与初始排序次序无关的是（A）。
A．选择排序法    B．插入排序法
C．快速排序法    D．堆排序法

（二）应用题

1. 一个堆积可以表示为一棵完全二叉树，请分别叙述堆积与二叉排序树的区别。 答：
若将堆积表示为一棵完全二叉树，则该二叉树中任意分支结点的值都大于或者等于其 孩 子结点（以大顶堆积为例），并且根结点具有最大值。而在二叉排序树中，要求所有左 子树 中的结点的值均小于根结点的值，所有右子树中的结点的值均大于或等于根结点的值， 根结 点不一定具有最大值。因此，堆积与二叉排序树不是同一回事。

（三）算法设计题 1.荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列

，请编写一个时
间复杂度为 O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。函
 
数原型如下：
typedef enum{RED,WHITE,BLUE} color; void Flag(color a[],int n);

答：
typedef enum{RED,WHITE,BLUE} color; void Flag(color a[],int n)
{
i=0;j=0;k=n-1;
while(j<=k)
switch(a[j])
{
case RED:
a[i]<->a[j]; i++;j++;break;
case WHITE：
j++;break; case BLUE:
a[j]<->a[k]; k-
-;
}
}

2． 可按如下所述实现归并排序：假设序列中有 k 个长度为小于等于 n 的有序子序列。利用 过程 merge 对它们进行两两归并，得到 k/2 个长度小于等于 2n 的有序子序列（ 表示 取整），称为一趟归并排序。反复调用一趟归并排序过程，使有序子序列的长度自 n=1 开始 成倍地增加，直至使整个序列成为一个有序序列。试采用链表存储结构实现上述归并排序 的非递归算法。函数原型如下：
void Linked_Mergesort(LinkedList &L);    //链表结构上的归并排序非递归算
法
void Linked_Merge(LinkedList &L, LNode *p, Lnode *e1,Lnode *e2);
//对链表上的子序列进行归并，第一个子序列是从 p->next 到 e1,第二个是从 e1->next 到
e2
答：
void Linked_Mergesort(LinkedList &L);
{
for(l=1;l<L.length;l*=2)
for(p=L->next,e2=p; p->next; p=e2)
{
for(i=1,q=p; i<=l && q->next; i++,q=q->next) e1=q;
for(i=1; i<=l && q->next; i++,q=q->next) e2=q;    //求两个待归并子序列的尾指针
 
if(e1!=e2)
Linked_Merge(L,p,e1,e2);
}
}

void Linked_Merge(LinkedList &L, LNode *p, Lnode *e1,Lnode *e2);
{
q=p->next;    //q 和 r 为两个子序列的起始位置
r=e1->next;
while(q!=e1->next && r!=e2->next)
{
if(q->data < r->data)
{
p->next=q; p=q;
q=q->next;
}
else
{
p->next=r; p=r;
r=r->next;
}
}
while(q!=e1->next)
{
p->next=q; p=q;
q=q->next;
}
while(r!=e2->next)
{
p->next=r; p=r;
r=r->next;
}
}

3.有一种简单的排序算法,叫做计数排序。这种排序算法对一个待排序的表(用数组表示)进 行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互 不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录 的关键字比该记录的关键字小。假设对某一个记录,统计出数值为 c,那么这个记录在新的有 序表中的合适的存放位置即为 c。
(1)给出适用于计数排序的数据表定义。
 
(2)编写实现计数排序的算法。 (3)对于 有 n 个记录的表,比较次数是多少?
(4)与直接选择排序相比,这种方法是否更好?为什么?
解:
(1)    typedef struct
{
ElemType data; KeyType key;
}listtype;
(2)    void countsort(listtype a[],listtype b[],int n)
{
int i,j,count; for(i=0;i<n;i++)
{
count=0; for(j=0;j<n;j++)
if(a[j].key<a[i].key) count++; b[count]=a[i];
}
}
(3) 对于有 n 个记录的表，关键字比较的次数是 n2. (4)直接选择排序比这种计数排序好， 因为直接选择排序的比较次数为 n*(n-1)/2，且可在 原地进行排序（稳定排序），而计数 排序为不稳定排序，需要辅助空间多，为 O(n).

4．快速排序算法中，如何选取一个界值（又称为轴元素），影响着快速排序的效率，而 且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素 的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
解： 题目解析：保存划分的第一个元素。以平均值作为枢轴，进行普通的快速排序，最后 枢轴 的位置存入已保存的第一个元素，若此关键字小于平均值，则它属于左半部，否则属 于右 半部。
int partition (RecType r[],int l,h)
{
int i=l,j=h,avg=0; for(;i<=h;i++)    avg+=R[i].key; i=l;
avg=avg/(h-l+1); while (i<j)