3. 查找和排序

3.1 顺序表的查找
3.2 有序表的折半查找
3.3 查找实验
3.4 哈希表
3.5 二叉排序树
3.6 插入排序和快速排序
3.7 选择排序和归并排序
3.8 排序实验
3.9 算法复杂性分析方法

对应的教材章节

第4章 群体类 线性群体 非线性群体 算法分析 顺序查找与折半查找 基本的顺序表类	2	一般要求
第14章 群体数据的组织 14．1 数组排序的基本算法 14．2 快速排序 14．3 哈希法 14．4 哈希表类 14．5 搜索方法的性能	3	一般要求

3.1 顺序表的查找

教学目的： 掌握查找的基本概念，顺序表查找的性能分析
教学重点： 查找的基本概念
教学难点： 顺序表查找的性能分析
授课内容：
一、查找的基本概念

一些约定：
 

典型的关键字类型说明：

typedef float KeyType;//实型 typedef int KeyType;//整型 typedef char *KeyType;//字符串型

数据元素类型定义为：

typedef struct{ KeyType key; // 关键字域 ... }ElemType;

对两个关键字的比较约定为如下的宏定义：

对数值型关键字 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) 对字符串型关键字 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b))<=0)

二、静态查找表
静态查找表的类型定义：

ADT StaticSearchTable{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： Create(&ST,n); 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(&ST); 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search(ST,key); 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。 操作结果：若ST中在在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 Traverse(ST,Visit()); 初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。 操作结果：按某种次序对ST的每个元素调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。 }ADT StaticSearchTable

三、顺序表的查找
静态查找表的顺序存储结构
typedef struct {
ElemType *elem;
int length;
}SSTable;

顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。
int Search_Seq(SSTable ST,KeyType key){
ST.elme[0].key=key;
for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
return i;
}

查找操作的性能分析：
查找算法中的基本操作是将记录的关键字和给定值进行比较，，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量依据。

平均查找长度：
为确定记录在查找表中的位置，需用和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。

	其中：Pi为查找表中第i个记录的概率，且； Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。
	等概率条件下有：
假设查找成功与不成功的概率相同：

四、总结
什么是查找表
顺序表的查找过程

3.2 有序表的折半查找

教学目的： 掌握有序表的折半查找法
教学重点： 折半查找
教学难点： 折半查找
授课内容：
一、折半查找的查找过程
以有序表表示静态查找表时，Search函数可用折半查找来实现。
先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。

二、折半查找的查找实现
int Search_Bin(SSTable ST,KeyType key){
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1 ;
}
return 0;
}//Search_Bin;
三、折半查找的性能分析
折半查找在查找成功时和给定值进行比较的关键字个数至多为

3.3 查找实验

实验 查找
教学目的： 练习顺序查找、折半查找及二叉排序树的实现
教学重点：
教学难点：
授课内容：
顺序查找
折半查找

顺序查找及折半查找示例
#include <stdio.h>
typedef int KeyType;
typedef struct{
KeyType key;
int maths;
int english;
}ElemType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct {
ElemType *elem;
int length;
}SSTable;
int Search_Seq(SSTable ST,KeyType key)
{
int i;
ST.elem[0].key=key;
for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
return i;
}
int Search_Bin(SSTable ST,KeyType key)
{
int low,mid,high;
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1;
}
}
getdata(SSTable * t)
{
FILE *fp;
int i=1;
fp=fopen("stu.txt","r");
fscanf(fp,"%d",&(t->length));
while(i<=t->length)
{
fscanf(fp,"%d %d %d",&(t->elem[i].key),
&(t->elem[i].maths),&(t->elem[i].english) );
i++;
}
fclose(fp);
}
main()
{
ElemType stu[50];
SSTable class;
int i,j,k;
long time;
class.elem=stu;
getdata(&class);
printf("This class has %d students.\n",class.length);
printf("Input stuno you want search:\n");
scanf("%d",&k);
i=Search_Seq(class,k);
j=Search_Bin(class,k);
printf("Maths English\n");
printf("%d %d\n",class.elem[i].maths,class.elem[i].english);
printf("%d %d\n",class.elem[j].maths,class.elem[j].english);
for(i=1;i<=4;i++)
{j=stu[i].maths+stu[i].english;
printf("%d\n",j);
}
}
二叉排序树
示例
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}

3.4 哈希表

教学目的： 掌握哈希表的概念作用及意义，哈希表的构造方法
教学重点： 哈希表的构造方法
教学难点： 哈希表的构造方法
授课内容：
一、哈希表的概念及作用
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...
如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26

刘丽	刘宏英	吴军	吴小艳	李秋梅	陈伟	...
姓名中各字拼音首字母	ll	lhy	wj	wxy	lqm	cw	...
用所有首字母编号值相加求和	24	46	33	72	42	26	...
最小值可能为3 最大值可能为78 可放75个学生

用上述得到的数值作为对应记录在表中的位置，得到下表：

		成绩一	成绩二...
3	...
...	...
24	刘丽	82	95
25	...
26	陈伟
...	...
33	吴军
...	...
42	李秋梅
...	...
46	刘宏英
...	...
72	吴小艳
...	...
78	...

上面这张表即哈希表。
如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：
李秋梅:lqm 12+17+13=42 取表中第42条记录即可。
问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？
这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。

二、哈希表的构造方法
１、直接定址法
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

２、数字分析法
有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
３、平方取中法
取关键字平方后的中间几位为哈希地址。
４、折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：

5864	5864
4220	0224
+)04	+)04
-----------	-----------
10088	6092
H(key)=0088	H(key)=6092
(a)移位叠加	(b)间界叠加

５、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
６、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
三、总结
哈希表的优缺点
四、作业
预习如何处理冲突及哈希表的查找。

哈希表（二）

教学目的： 掌握哈希表处理冲突的方法及哈希表的查找算法
教学重点： 哈希表处理冲突的方法
教学难点： 开放定址法
授课内容：
一、复习上次课内容
什么是哈希表？如何构造哈希表？
提出问题：如何处理冲突？
二、处理冲突的方法

如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：

１、开放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m为表长，di为增量序列
如果di值可能为1,2,3,...m-1，称线性探测再散列。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：

(a)插入前

0	1	2	3	4	5	6	7	8	9	10
					60	17	29	38

(b)线性探测再散列

0	1	2	3	4	5	6	7	8	9	10
					60	17	29

(c)二次探测再散列

0	1	2	3	4	5	6	7	8	9	10
			38		60	17	29

(d)伪随机探测再散列

伪随机数列为 9,5,3,8,1... ２、再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
３、链地址法
将所有关键字为同义词的记录存储在同一线性链表中。

 

４、建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
三、哈希表的查找
//开放定址哈希表的存储结构
int hashsize[]={997,...};
typedef struct{
ElemType *elem;
int count;
int sizeindex;
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
Status SearchHash(HashTable H,KeyType K,int &p,int &c){
p=Hash(K);
while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
collision(p,++c);
if(EQ(K,H.elem[p].key)
return SUCCESS;
else return UNSUCCESS;
}
Status InsertHash(HashTable &H,EleType e){
c=0;
if(SearchHash(H,e.key,p,c))
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2){
H.elem[p]=e; ++H.count; return OK;
}
else RecreateHashTable(H);
}
四、总结
处理冲突的要求是什么？

3.5 二叉排序树

教学目的： 掌握二叉排序树的实现方法
教学重点： 二叉排序树的实现
教学难点： 构造二叉排序树的方法
授课内容：
一、动态查找表的定义
动态查找表的特点是：
表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。以政是动态查找表的定义：
ADT DymanicSearchTable{
数据对象Ｄ：Ｄ是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。
数据关系Ｒ：数据元素同属一个集合。
基本操作Ｐ：
InitDSTable(&DT);
DestroyDSTable(&DT);
SearchDSTable(DT,key);
InsertDSTable(&DT,e);
DeleteDSTable(&DT,key);
TraverseDSTable(DT,Visit());
}ADT DynamicSearchTable
二、二叉排序树及其查找过程
二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：
１、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
２、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
３、它的左、右子树了分别为二叉排序树。
如果取二叉链表作为二叉排序树的存储结构，则上述查找过程如下：
BiTree SearchBST(BiTree T,KeyType key){
if(!T)||EQ(key,T->data.key)) return (T);
else if LT(key,T->data.key) return (SearchBST(T->lchild,key));
else return (SearchBST(T->rchild.key));
}//SearchBST
三、二叉排序树的插入和删除
二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){
if(!T) {p=f;return FALSE;}
else if EQ(key,T->data.key){ p=T;return TRUE;}
else if LT(key,T->data.key) SearchBsT(T->lchild,key,T,p);
else SearchBST(T->rchild,key,T,p);
}//SearchBST
插入算法：
Status InsertBST(BiTree &T,ElemType e){
if(!SearchBST(T,e.key,NULL,p){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;s->lchild=s->rchild=NULL;
if(!p) T=s;
else if (LT(e.key,p->data.key) p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}//InsertBST
在二叉排序树中删除一个节点的算法：
Status DeleteBST(BiTree &T,KeyType key){
if(!T) return FALSE;
else{
if EQ(key,T->data.key) Delete(T);
else if LT(key,T->data.key) DeleteBST(T->lchild,key);
else DeleteBST(T->rchild,key);
return TRUE;
}
}
void Delete(BiTree &p){
if(!p->rchild){
q=p; p=p->lchild; free(q);
}
else if(!p->lchild){
q=p;p=p->rchild; free(q);
}
else{
//方法一：如图示

q=p;s=p->lchild;
while(s->rchild){q=s;s=s->rchild}//转左，然后向右到尽头
p->data=s->data; //s指向被删结点的"前驱"
if(q!=p)q->rchild=s->lchild; //重接*q的右子树
else q->lchild=s->lchild;//重接*q的左子树 （方法一结束）
//或可用方法二：
//q=s=(*p)->l;
//while(s->r) s=s->r;
//s->r=(*p)->r;
//free(*p);
//(*p)=q;

}
}
请看一个示例源程序。
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
BiNode * new()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}
四、总结

3.6 插入排序和快速排序

第三十四课
本课主题： 插入排序，快速排序
教学目的： 掌握排序的基本概念，插入排序、快速排序的算法
教学重点： 插入排序、快速排序的算法
教学难点： 快速排序算法
授课内容：
一、排序概述
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。

姓名	年龄	体重
1李由	57	62
2王天	54	76
3七大	24	75
4张强	24	72
5陈华	24	53

上表按年龄无序，如果按关键字年龄用某方法排序后得到下表：

姓名	年龄	体重
3七大	24	75
4张强	24	72
5陈华	24	53
2王天	54	76
1李由	57	62

注意反色的三条记录保持原有排列顺序，则称该排序方法是稳定的！
如果另一方法排序后得到下表：

姓名	年龄	体重
4张强	24	72
3七大	24	75
5陈华	24	53
2王天	54	76
1李由	57	62

原3,4,5记录顺序改变，则称该排序方法是不稳定的！
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、插入排序
1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：

38

49

65

97

76

13

27

49

...

38

49

65

76

97

13

27

49

...

13

38

49

65

76

97

27

49

...

13

27

38

49

65

76

97

49

...

13

27

38

49

49

65

76

97

...

2、折半插入排序
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。
3、2－路插入排序
为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：

49

38

65

97

78

13

27

49

...

三、快速排序
1、起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。

2、快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

初始关键字	49	38	65	97	76	13	27	49
	i						j	j
1次交换之后	27	38	65	97	76	13		49
	i		i				j
2次交换之后	27	38		97	76	13	65	49
			i			j	j
3次交换之后	27	38	13	97	76		65	49
			i	i		j
4次交换之后	27	38	13		76	97	65	49
				ij		j
完成一趟排序	27	38	13	49	76	97	65	49
初始状态	49	38	65	97	76	13	27	49
一次划分	27	38	13	49	76	97	65	49
分别进行	13	27	38
	结束		结束		49	65	76	97
					49	65		结束
						结束
有序序列	13	27	38	49	49	65	76	97

四、总结
几种排序的简单分析与比较。（时间、空间复杂度）
五、作业
实现直接插入排序、起泡排序、快速排序算法。

3.7 选择排序和归并排序

教学目的： 掌握选择排序，归并排序算法
教学重点： 选择排序之堆排序，归并排序算法
教学难点： 堆排序算法
授课内容：
一、选择排序
每一趟在n-i+1(i=1,2,...n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
二、简单选择排序
算法：
Smp_Selecpass(ListType &r,int i)
{
k=i;
for(j=i+1;j<n;i++)
if (r[j].key<r[k].key)
k=j;
if (k!=i)
{ t=r[i];r[i]=r[k];r[k]=t;}
}
Smp_Sort(ListType &r)
{
for(i=1;i<n-1;i++)
Smp_Selecpass(r,i);
}
三、树形选择排序
又称锦标赛排序，首先对n个记录的关键字进行两两比较，然后在其中一半较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。
四、堆排序
只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
什么是堆？n个元素的序列{k1,k2,...,kn}当且仅当满足下列关系时，称之为堆。关系一：ki<=k2i 关系二：ki<=k2i+1（i=1,2,...,n/2)
堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
问题2的解决方法：

sift(ListType &r,int k,int m)
{
i=k;j=2*i;x=r[k].key;finished=FALSE;
t=r[k];
while((j<=m)&&(!finished))
{
if ((j<m)&&(r[j].key>r[j+1].key)) j++;
if (x<=r[j].key)
finished:=TRUE;
else {r[i]=r[j];i=j;j=2*i;}
}
r[i]=t;
}
HeapSort(ListType &r)
{
for(i=n/2;i>0;i--) sift(r,i,n);
for(i=n;i>1;i--){
r[1]<->r[i];
sift(r,i,i-1)
}
}
五、归并排序
将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。
假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复。

merge(ListType r,int l,int m,int n,ListType &r2)
{
i=l;j=m+1;k=l-1;
while(i<=m) and(j<n) do
{
k=k+1;
if (r[i].key<=r[j].key) {r2[k]=r[i];i++;}
else {r2[i]=r[j];j++}
}
if (i<=m) r2[k+1..n]=r[i..m];
if (j<=n) r2[k+1..n]=r[j..n];
}
mergesort(ListType &r,ListType &r1,int s,int t)
{
if (s==t)
r1[s]=r[s];
else
{
mergesort(r,r2,s,s+t/2);
mergesort(r,r2,s+t/2+1,t);
merge(r2,s,s+t/2,t,r1);
}
]
六、总结

3.8 排序实验

教学目的： 掌握简单插入排序、快速排序、堆排序的算法并加以应用。
教学重点：
教学难点：
授课内容：
实现下述三种算法，并用以下无序序列加以验证：
49，38，65，97，76，13，27，49
一、简单插入排序
二、快速排序
三、堆排序
以上算法的C源程序。
#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef int InfoType;
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList;
void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;++i)
if(LT(L->r[i].key,L->r[i-1].key)){
L->r[0]=L->r[i];
for(j=i-1; LT(L->r[0].key,L->r[j].key); --j)
L->r[j+1]=L->r[j];
L->r[j+1]=L->r[0];
}
}
void BInsertSort(SqList *L)
{
int i,j;
int low,high,m;
for(i=2;i<=L->length;++i){
L->r[0]=L->r[i];
low=1;high=i-1;
while(low<=high){
m=(low+high)/2;
if (LT(L->r[0].key,L->r[m].key))
high=m-1;
else low=m+1;
}
for(j=i-1;j>=high+1;--j)
L->r[j+1]=L->r[j];
L->r[high+1]=L->r[0];
}
}
/* QuickSort related function */
int Partition(SqList *L,int low,int high)
{
int pivotkey;
L->r[0]=L->r[low];
pivotkey=L->r[low].key;
while(low<high){
while(low<high&&L->r[high].key>=pivotkey) --high;
L->r[low]=L->r[high];
while(low<high&&L->r[low].key<=pivotkey) ++low;
L->r[high]=L->r[low];
}
L->r[low]=L->r[0];
return low;
}
void QSort(SqList *L,int low,int high)
{
int pivotloc;
if(low<high){
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList *L)
{
QSort(L,1,L->length);
} /* End QuickSort related function*/
/*SelectSort related function */
int SelectMinKey(SqList L,int i)
{
int k;
int j;
k=i;
for(j=i;j<L.length+1;j++)
if(L.r[k].key>L.r[j].key)
k=j;
return k;
}
void SelectSort(SqList *L)
{
RedType t;
int i,j;
for(i=1;i<L->length;++i){
j=SelectMinKey(*L,i);
if(i!=j) {
t=L->r[i];
L->r[i]=L->r[j];
L->r[j]=t;
}
}
} /*End SelectSort related function */
typedef SqList HeapType;
void HeapAdjust(HeapType *H,int s,int m)
{
RedType rc;
int j;
rc=H->r[s];
for(j=2*s;j<=m;j*=2){
if(j<m&&LT(H->r[j].key,H->r[j+1].key)) ++j;
if(!LT(rc.key,H->r[j].key)) break;
H->r[s]=H->r[j];
s=j;
}
H->r[s]=rc;
}
void HeapSort(HeapType *H)
{
RedType t;
int i;
for(i=H->length/2;i>0;--i)
HeapAdjust(H,i,H->length);
for(i=H->length;i>1;--i){
t=H->r[1];
H->r[1]=H->r[i];
H->r[i]=t;
HeapAdjust(H,1,i-1);
}
}
main()
{
int a[]={49,38,65,97,76,13,27,49};
int i,k;
SqList s;
printf("\nThe record to be sort:\n");
for(i=1;i<9;i++)
{
s.r[i].key=a[i-1];
printf("%d ",a[i-1]);
}
s.length=i-1;
printf("\n\t1,InsertSort\n\t2,BInsertSort\n\t3,QuickSort\n\t4,SelectSort\n");
printf("\t5,HeapSort\n\tPress 1..5 to select a function\n");
scanf("%d",&k);
switch(k){
case 1:
InsertSort(&s);
break;
case 2:
BInsertSort(&s);
break;
case 3:
QuickSort(&s);
break;
case 4:
SelectSort(&s);
break;
case 5:
HeapSort(&s);
break;
default:printf("No function which you select.\n");
}
printf("\nThe records be sorted:\n");
for(i=1;i<9;i++)
printf("%d ",s.r[i].key);
printf("\n\n\tPress any key to exit.\n");
getch();
}

3.9 算法复杂性分析方法

第四课
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。

程序在计算机上运行所需时间的影响因素
算法本身选用的策略
问题的规模	规模越大，消耗时间越多
书写程序的语言	语言越高级，消耗时间越多
编译产生的机器代码质量
机器执行指令的速度

综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）

T(n)= O(f(n))
上示表示 随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的 渐近时间复杂度，简称 时间复杂度。

求4*4矩阵元素和，T(4)=O(f(4)) f=n*n;	sum(int num[4][4]) { int i,j,r=0; for(i=0;i<4;i++) for(j=0;j<4;j++) r+=num[i][j]; /*原操作*/ return r; }
最好情况： T（4）=O（0） 最坏情况： T（4）=O（n*n）	ispass(int num[4][4]) { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1) return 0; return 1; }

原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。

语句	频度	时间复杂度
{++x;s=0;}	1	O(1)
for(i=1;i<=n;++i) {++x;s+=x;}	n	O(n)
for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;}	n*n	O(n*n)
O(log n)

二、算法的存储空间需求
类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。
记作：

S(n)= O( f(n))
若额外空间相 对于输入数据量来说是常数，则称此算法为 原地工作。
如果所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。

三、总结
渐近时间复杂度
空间复杂度