实验五 查找及排序

实验五 查找及排序

实验课程名： 数据结构与算法

一、实验目的及要求

1、掌握查找的不同方法，并能用高级语言实现查找算法。

2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法。

3、掌握常用的排序方法，并能用高级语言实现排序算法。

4、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。

5、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验内容

任务一：顺序表的顺序查找。 有序表的折半查找。

完成下列程序，该程序实现高考成绩表（如下表所示）的顺序查找，在输出结果中显示查找成功与查找不成功信息。

解答：

（1）源代码：#include // EOF(=^Z 或F6),NULL #include // atoi() #include // eof()

#include // floor(),ceil(),abs() #include // exit() #include // cout,cin // 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define INFEASIBLE -1

// #define OVERFLOW -2 因为在math.h 中已定义OVERFLOW 的值为3,故去掉

此行

typedef int Status; // Status 是函数的类型,其值是函数结果状态代码，

如OK 等

typedef int Boolean; // Boolean 是布尔类型,其值是TRUE 或FALSE #define MAX_LENGTH 100 #include

准考证号 姓名 各科成绩 总分

政治

语文 外语 数学 物理 化学 生物 179328 何芳芳 85 89 98 100 93 80 47 592 179325 陈红 85 86 88 100 92 90 45 586 179326 陆华 78 75 90 80 95 88 37 543 179327 张平 82 80 78 98 84 96 40 558 179324

赵小怡

76 85 94 57 77

69 44

502

#include

#include // malloc()等

#include // INT_MAX等

#include // EOF(=^Z或F6),NULL

#include // atoi()

#include // eof()

#include // floor(),ceil(),abs()

#include // exit()

#include // cout,cin

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

#define N 5 // 数据元素个数

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

typedef long KeyType; // 设关键字域为长整型

#define key number // 定义关键字为准考证号

struct ElemType // 数据元素类型(以教科书图9.1高考成绩为例)

{

long number; // 准考证号，与关键字类型同

char name[9]; // 姓名(4个汉字加1个串结束标志)

int politics; // 政治

int Chinese; // 语文

int English; // 英语

int math; // 数学

int physics; // 物理

int chemistry; // 化学

int biology; // 生物

int total; // 总分

};

typedef struct {

ElemType *elem; // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空

int length; // 表长度

}SSTable;

void Creat_Seq(SSTable &ST,ElemType r[],int n)

{ // 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST

int i;

ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType)); // 动态生成n+1个数据元素空间(0号单元不用)

if(!ST.elem)

exit(ERROR);

for(i=1;i<=n;i++)

ST.elem[i]=r[i-1]; // 将数组r的值依次赋给ST

ST.length=n;

}

void Ascend(SSTable &ST)

{ // 重建静态查找表为按关键字非降序排序

int i,j,k;

for(i=1;i

{

k=i;

ST.elem[0]=ST.elem[i]; // 待比较值存[0]单元

for(j=i+1;j<=ST.length;j++)

if LT(ST.elem[j].key,ST.elem[0].key)

{

k=j;

ST.elem[0]=ST.elem[j];

}

if(k!=i) // 有更小的值则交换

{

ST.elem[k]=ST.elem[i];

ST.elem[i]=ST.elem[0];

}

}

}

void Creat_Ord(SSTable &ST,ElemType r[],int n)

{ // 操作结果：由含n个数据元素的数组r构造按关键字非降序查找表ST Creat_Seq(ST,r,n); // 建立无序的查找表ST

Ascend(ST); // 将无序的查找表ST重建为按关键字非降序查找表

}

Status Destroy(SSTable &ST)

{ // 初始条件：静态查找表ST存在。操作结果：销毁表ST

free(ST.elem);

ST.elem=NULL;

ST.length=0;

return OK;

int Search_Seq(SSTable ST,KeyType key)

{ // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则返回

// 该元素在表中的位置，否则返回0。算法9.1

int i;

ST.elem[0].key=key; // 哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i); // 从后往前找

return i; // 找不到时，i为0

}

void Traverse(SSTable ST,void(*Visit)(ElemType))

{ // 初始条件：静态查找表ST存在，Visit()是对元素操作的应用函数

// 操作结果：按顺序对ST的每个元素调用函数Visit()一次且仅一次

ElemType *p;

int i;

p=++ST.elem; // p指向第一个元素

for(i=1;i<=ST.length;i++)

Visit(*p++);

}

void print(ElemType c) // Traverse()调用的函数

{

printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5d\n",c.number,https://www.wendangku.net/doc/5916922634.html,

,c.politics,

c.Chinese,c.English,c.math,c.physics,c.chemistry,c.biology,c

.total);

}

int main()

{

ElemType r[N]={{179328,"何芳芳",85,89,98,100,93,80,47},

{179325,"陈红",85,86,88,100,92,90,45},

{179326,"陆华",78,75,90,80,95,88,37},

{179327,"张平",82,80,78,98,84,96,40},

{179324,"赵小怡",76,85,94,57,77,69,44}}; // 数组不按关键字有序

SSTable st;

int i;

long s;

for(i=0;i

r[i].total=r[i].politics+r[i].Chinese+r[i].English+r[i].math

+r[i].physics+

r[i].chemistry+r[i].biology;

Creat_Seq(st,r,N); // 由数组r产生顺序静态查找表st

printf("准考证号姓名政治语文外语数学物理化学生物总分\n");

Traverse(st,print); // 按顺序输出静态查找表st

printf("请输入待查找人的考号: ");

scanf("%ld",&s);

i=Search_Seq(st,s); // 顺序查找

if(i)

print(st.elem[i]);

else

printf("没找到\n");

Destroy(st);

return 0;

}

（2）运行结果：

（3）运行结果分析：

运用顺序结构完成查询。

任务二：哈希表的开放定址法算法。在输出结果中显示查找成功与查找不成功信息。

解答：

（1）源代码：#include

#include

#include // malloc()等

#include // INT_MAX等

#include // EOF(=^Z或F6),NULL

#include // atoi()

#include // eof()

#include // floor(),ceil(),abs()

#include // exit()

#include // cout,cin

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

#define N 11 // 数据元素个数

#define SUCCESS 1

#define UNSUCCESS 0

#define DUPLICATE -1

#define NULL_KEY 0 // 0为无记录标志

#define N 10 // 数据元素个数

typedef int KeyType; // 设关键字域为整型

struct ElemType // 数据元素类型

{

KeyType key;

int ord;

};

int hashsize[]={11,19,29,37}; // 哈希表容量递增表，一个合适的素数序列

int m=0; // 哈希表表长，全局变量

struct HashTable

{

ElemType *elem; // 数据元素存储基址，动态分配数组

int count; // 当前数据元素个数

int sizeindex; // hashsize[sizeindex]为当前容量

};

void InitHashTable(HashTable &H)

{ // 操作结果：构造一个空的哈希表

int i;

H.count=0; // 当前元素个数为0

H.sizeindex=0; // 初始存储容量为hashsize[0]

m=hashsize[0];

H.elem=(ElemType*)malloc(m*sizeof(ElemType));

if(!H.elem)

exit(OVERFLOW); // 存储分配失败

for(i=0;i

H.elem[i].key=NULL_KEY; // 未填记录的标志

}

void DestroyHashTable(HashTable &H)

{ // 初始条件：哈希表H存在。操作结果：销毁哈希表H

free(H.elem);

H.elem=NULL;

H.count=0;

H.sizeindex=0;

}

unsigned Hash(KeyType K)

{ // 一个简单的哈希函数(m为表长，全局变量)

return K%m;

}

void collision(int &p,int d) // 线性探测再散列

{ // 开放定址法处理冲突

p=(p+d)%m;

}

Status SearchHash(HashTable H,KeyType K,int &p,int &c)

{ // 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据

// 元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回UNSUCCESS

// c用以计冲突次数，其初值置零，供建表插入时参考。算法9.17

p=Hash(K); // 求得哈希地址

while(H.elem[p].key!=NULL_KEY&&!EQ(K,H.elem[p].key))

{ // 该位置中填有记录．并且关键字不相等

c++;

if(c

collision(p,c); // 求得下一探查地址p

else

break;

}

if EQ(K,H.elem[p].key)

return SUCCESS; // 查找成功，p返回待查数据元素位置

else

return UNSUCCESS;

// 查找不成功(H.elem[p].key==NULL_KEY)，p返回的是插入位置

}

Status InsertHash(HashTable &,ElemType); // 对函数的声明

void RecreateHashTable(HashTable &H)

{ // 重建哈希表

int i,count=H.count;

ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));

p=elem;

printf("重建哈希表\n");

for(i=0;i

if((H.elem+i)->key!=NULL_KEY) // 该单元有数据

*p++=*(H.elem+i);

H.count=0;

H.sizeindex++; // 增大存储容量

m=hashsize[H.sizeindex];

p=(ElemType*)realloc(H.elem,m*sizeof(ElemType));

if(!p)

exit(OVERFLOW); // 存储分配失败

H.elem=p;

for(i=0;i

H.elem[i].key=NULL_KEY; // 未填记录的标志(初始化)

for(p=elem;p

InsertHash(H,*p);

}

Status InsertHash(HashTable &H,ElemType e)

{ // 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；

// 若冲突次数过大，则重建哈希表，算法9.18

int c,p;

c=0;

if(SearchHash(H,e.key,p,c)) // 表中已有与e有相同关键字的元素

return DUPLICATE;

else if(c

{ // 插入e

H.elem[p]=e;

++H.count;

return OK;

}

else

{

RecreateHashTable(H); // 重建哈希表

return UNSUCCESS;

}

}

void TraverseHash(HashTable H,void(*Vi)(int,ElemType))

{ // 按哈希地址的顺序遍历哈希表

printf("哈希地址0～%d\n",m-1);

for(int i=0;i

if(H.elem[i].key!=NULL_KEY) // 有数据

Vi(i,H.elem[i]);

}

Status Find(HashTable H,KeyType K,int &p)

{ // 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据

// 元素在表中位置，并返回SUCCESS；否则，返回UNSUCCESS

int c=0;

p=Hash(K); // 求得哈希地址

while(H.elem[p].key!=NULL_KEY&&!EQ(K,H.elem[p].key))

{ // 该位置中填有记录．并且关键字不相等

c++;

if(c

collision(p,c); // 求得下一探查地址p

else

return UNSUCCESS; // 查找不成功(H.elem[p].key==NULL_KEY)

}

if EQ(K,H.elem[p].key)

return SUCCESS; // 查找成功，p返回待查数据元素位置

else

return UNSUCCESS; // 查找不成功(H.elem[p].key==NULL_KEY)

}

void print(int p,ElemType r)

{

printf("address=%d (%d,%d)\n",p,r.key,r.ord);

}

int main()

{

ElemType

r[N]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{6

0,9},{13,10}};

HashTable h;

int i,p;

Status j;

KeyType k;

InitHashTable(h);

for(i=0;i

{ // 插入前N-1个记录

j=InsertHash(h,r[i]);

if(j==DUPLICATE)

printf("表中已有关键字为%d的记录，无法再插入记录(%d,%d)\n",r[i].key,r[i].key,r[i].ord);

}

printf("按哈希地址的顺序遍历哈希表:\n");

TraverseHash(h,print);

printf("请输入待查找记录的关键字: ");

scanf("%d",&k);

j=Find(h,k,p);

if(j==SUCCESS)

print(p,h.elem[p]);

else

printf("没找到\n");

j=InsertHash(h,r[i]); // 插入第N个记录

if(j==ERROR) // 重建哈希表

j=InsertHash(h,r[i]); // 重建哈希表后重新插入

printf("按哈希地址的顺序遍历重建后的哈希表:\n");

TraverseHash(h,print);

printf("请输入待查找记录的关键字: ");

scanf("%d",&k);

j=Find(h,k,p);

if(j==SUCCESS)

print(p,h.elem[p]);

else

printf("没找到\n");

DestroyHashTable(h);

return 0;

}

（2）运行结果：

（3）运行结果分析：

运用哈希表开放定地址算法实现。

任务三：各种插入排序算法的实现。

解答：

（1）源代码：#include

#include

#include // malloc()等

#include // INT_MAX等

#include // EOF(=^Z或F6),NULL #include // atoi()

#include // eof()

#include // floor(),ceil(),abs() #include // exit()

#include // cout,cin

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等

typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE

typedef int InfoType; // 定义其它数据项的类型

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

#define MAX_SIZE 20 // 一个用作示例的小顺序表的最大长度

typedef int KeyType; // 定义关键字类型为整型

struct RedType // 记录类型

{

KeyType key; // 关键字项

InfoType otherinfo; // 其它数据项，具体类型在主程中定义

};

struct SqList // 顺序表类型

{

RedType r[MAX_SIZE+1]; // r[0]闲置或用作哨兵单元

int length; // 顺序表长度

};

void InsertSort(SqList &L)

{ // 对顺序表L作直接插入排序。

int i,j;

for(i=2;i<=L.length;++i)

if LT(L.r[i].key,L.r[i-1].key) // "<",需将L.r[i]插入有序子表

{

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)

{ // 对顺序表L作折半插入排序。

int i,j,m,low,high;

for(i=2;i<=L.length;++i)

{

L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0]

low=1;

high=i-1;

while(low<=high)

{ // 在r[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]; // 插入

}

}

void P2_InsertSort(SqList &L)

{ // 2_路插入排序

int i,j,first,final;

RedType *d;

d=(RedType*)malloc(L.length*sizeof(RedType)); // 生成L.length个记录的临时空间

d[0]=L.r[1]; // 设L的第1个记录为d中排好序的记录(在位置[0])

first=final=0; // first、final分别指示d中排好序的记录的第1个和最后1个记录的位置

for(i=2;i<=L.length;++i) // 依次将L的第2个～最后1个记录插入d 中

if(L.r[i].key

{ // 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素)

first=(first-1+L.length)%L.length; // 设d为循环向量

d[first]=L.r[i];

}

else if(L.r[i].key>d[final].key)

{ // 待插记录大于d中最大值，插到d[final]之后(不需移动d数组的元素)

final=final+1;

d[final]=L.r[i];

}

else

{ // 待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素)

j=final++; // 移动d的尾部元素以便按序插入记录

while(L.r[i].key

{

d[(j+1)%L.length]=d[j];

j=(j-1+L.length)%L.length;

}

d[j+1]=L.r[i];

}

for(i=1;i<=L.length;i++) // 把d赋给L.r

L.r[i]=d[(i+first-1)%L.length]; // 线性关系

}

void print(SqList L)

{

int i;

for(i=1;i<=L.length;i++)

printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);

printf("\n");

}

#define N 8

int main()

{

RedType

d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8

}};

SqList l1,l2,l3;

int i;

for(i=0;i

l1.r[i+1]=d[i];

l1.length=N;

l2=l3=l1; // 复制顺序表l2、l3与l1相同

printf("排序前:\n");

print(l1);

InsertSort(l1);

printf("直接插入排序后:\n");

print(l1);

BInsertSort(l2);

printf("折半插入排序后:\n");

print(l2);

P2_InsertSort(l3);

printf("2_路插入排序后:\n");

print(l3);

return 0;

}

（2）运行结果：

（3）运行结果分析

运用直插、折半插、路插的方法编写。

三、实验小结

通过本次实验我知道了查找的不同方法，并能用高级语言实现查找算法，并且掌握顺序表的查找方法和有序顺序表的折半查找算法，了解了常用的排序方法，并能用高级语言实现排序算法。

《数据结构》实验报告——排序.docx

《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1. 插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i 趟直接插入排序的操作为：在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后，变成含有i 个记录的有序子序列r[1..i ]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r [0]处设置哨兵。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 （通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线，将序列{L.r[s] ，… ，L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针lOw 和high ，他们的初值分别为lOw 和high ，设枢轴记录的关键字为PiVOtkey ，则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换，然后从lOw 所指位置起向后搜索，找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至low=high 为止。 具体实现上述算法是，每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上，

(完整word版)查找、排序的应用 实验报告

实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1．总成绩要求自动计算； 2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）； 3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义，哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。

四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 a、折半查找 设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较， 若key==r[mid].key，查找成功 若keyr[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败 b、顺序查找 从表的一端开始逐个进行记录的关键字和给定值的比较。在这里从表尾开始并把下标为0的作为哨兵。 void chaxun(SqList &ST) //查询信息 { cout<<"\n************************"<=1;j--) if(ST.r[j].xuehao

算法排序问题实验报告

《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的， 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一 部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0]小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小的记录移到低端 while low

实验报告-排序与查找

电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间： 5月20日 2014-2015-2学期 信息与软件工程学院

实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key

动态查找表实验报告材料

动态查找表实验报告 一. 1 、实验概要 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 实验计划学时: 6 2、实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 实验要求如下： 1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。 2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。 3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。 4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。 所用软件环境或工具：DEV-C++5可视化编程环境. 3.动态查找表的抽象数据类型 ADT DynamicSearchTable { 数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一 标识数据元素。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(&DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT); 初始条件：动态查找表DT存在； 操作结果：销毁动态查找表DT。 SearchDSTable(DT, key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值； 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的

查找与排序实验报告

实验四：查找与排序 【实验目的】 1.掌握顺序查找算法的实现。 2.掌握折半查找算法的实现。 【实验内容】 1.编写顺序查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 2.编写折半查找程序，对以下数据查找37所在的位置。 5，13，19，21，37，56，64，75，80，88，92 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。 至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4．写好代码 5．编译－＞链接－＞调试 #include "stdio.h" #include "malloc.h" #define OVERFLOW -1 #define OK 1 #define MAXNUM 100 typedef int Elemtype; typedef int Status; typedef struct {

Elemtype *elem; int length; }SSTable; Status InitList(SSTable &ST ) { int i,n; ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW); printf("输入元素个数和各元素的值:"); scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&ST.elem[i]); } ST.length = n; return OK; } int Seq_Search(SSTable ST,Elemtype key) { int i; ST.elem[0]=key; for(i=ST.length;ST.elem[i]!=key;--i); return i; } int BinarySearch(SSTable ST,Elemtype key) { int low,high,mid; low=1; high=ST.length;

排序操作实验报告

数据结构与算法设计 实验报告 （2016 — 2017 学年第1 学期） 实验名称： 年级： 专业： 班级： 学号： 姓名： 指导教师： 成都信息工程大学通信工程学院

一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 （1）从键盘读入一组无序数据，按输入顺序先创建一个线性表。 （2）用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。 三、实验步骤 1、创建工程（附带截图说明） 2、根据算法编写程序（参见第六部分源代码） 3、编译 4、调试 四、实验结果图 图1-直接输入排序

图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡

排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。 六、源代码 要求：粘贴个人代码，以便检查。 #include #define MAXSIZE 100 typedef int KeyType; typedef int DataType; typedef struct{ KeyType key; DataType data; }SortItem,SqList[MAXSIZE]; /*******直接插入顺序表*******/ void InsertSort(SqList L,int n) { int i,j,x; SortItem p; for(i=1;i

顺序表的查找、插入与删除实验报告

《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);

河南工业大学实验报告——查找和排序(排序)——张伟龙

河南工业大学实验报告 课程名称数据结构实验项目实验三查找和排序(二)——排序院系信息学院计科系专业班级计科1203 姓名张伟龙学号 201216010313 指导老师范艳峰日期 2013.6.5 批改日期成绩 一实验目的 掌握希尔排序、快速排序、堆排序的算法实现。 二实验内容及要求 实验内容：1．实现希尔排序。 2．实现快速排序。 3. 实现堆排序。 （三选一） 实验要求：1. 根据所选题目，用C语言编写程序源代码。 2. 源程序必须编译调试成功，独立完成。 三实验过程及运行结果 选择第三题： Source Code： #include #include using namespace std; void HeapAdjust(int *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号

int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i是叶节点就不用进行调整 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(a[i],a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(int *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } }

《数据结构》实验报告查找

实验四——查找 一、实验目的 1.掌握顺序表的查找方法，尤其是折半查找方法； 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表，用顺序查找的方法对其实施查找； 2.建立一个有序表，用折半查找的方法对其实施查找； 3.建立一个二叉排序树，根据给定值对其实施查找； 4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有：结构体typedef struct，插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main(). 四、上机实验 实验一： 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<

查找排序实验报告

《编程实训》 实验报告书 专业：计算机科学与技术 班级：151班 学号： 姓名： 指导教师： 日期：2016年6月30日

目录 一、需求分析 (3) 1.任务要求 (3) 2.软件功能分析 (3) 3.数据准备 (3) 二、概要设计 (3) 1.功能模块图 (4) 2.模块间调用关系 (4) 3.主程序模块 (5) 4.抽象数据类型描述 (5) 三、详细设计 (6) 1.存储结构定义 (6) 2.各功能模块的详细设计 (7) 四、实现和调试 (7) 1.主要的算法 (7) 2.主要问题及解决 (8) 3.测试执行及结果 (8) 五、改进 (9) 六、附录 (9) 1.查找源程序 (9) 2.排序源程序 (9)

目录 1 需求分析 1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现； 以及各种排序算法的实现。 1.2 软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。 1.3 数据准备 任意输入了5个正整数如下： 12 23 45 56 78 2 概要设计（如果2，3合并可以省略2.4） 2.1 功能模块图（注：含功能说明） 2.2 模块间调用关系 2.3 主程序模块 2.4 抽象数据类型描述 存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）是一个“值”的集合和定义在此集合上的一组操作的总称。 3 详细设计 3.1 存储结构定义 查找： typedef int ElemType ; //顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; //表的长度

各种排序实验报告

【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为："<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {

temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："<

二叉排序树实验报告

二叉排序树的实现 实验内容与要求 1) 实现二叉排序树，包括生成、插入，删除； 2) 对二叉排序树进行先根、中根、和后根非递归遍历； 3) 每次对树的修改操作和遍历操作的显示结果都需要在屏 幕上用树的形状表示出来。 实验方案 1. 选择链表的方式来构造节点，存储二叉排序树的节点。// 树的结构struct BSTNode { // 定义左右孩子指针 struct BSTNode *lchild,*rchild; // 节点的关键字 TElemType key; }; int depth=0; // 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree; 2. 对树的操作有如下方法： // 创建二叉排序树 Tree CreatTree(Tree T) ； // 二叉树的深度，返回一个int 值为该树的深度 int TreeDepth(Tree T) // 树状输出二叉树，竖向输出 void PrintTree(Tree T , int layer) ； // 查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点 Status SearchBST(Tree T , TElemType key , Tree f,Tree &p) ； // 向树中插入节点 Status InsertBST(Tree &T , TElemType e) ； // 删除节点 Status Delete(Tree &T) ；

// 删除指定节点，调用Delete(Tree &T) 方法 Status DeleteData(Tree &T , TElemType key) ； // 非递归先序遍历void x_print(Tree T); // 非递归中序遍历 Void z_print(Tree T ); // 非递归后序遍历 void h_print(Tree T); 3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现 // 自定义类型以SElemType 作为栈中指针返回的值的类型 // 也就是要返回一个节点的指针 typedef Tree SElemType; // 栈的结构 struct Stack { // 栈底指针SElemType *base; // 栈顶指针SElemType *top; // 栈的容量 int stacksize; }; 4. 栈的操作方法： // 创建一个空栈 Status InitStack(Stack &S) // 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack &S,SElemType &elem) // 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType &elem) // 删除栈顶元素 Status DeleteTop(Stack &S) // 往栈中压入数据 Status Push(Stack &S,SElemType elem) // 判断栈是否为空 Status IsEmpty(Stack S) 三、代码实现 #include #include using namespace std;

查询与排序 实验报告

学院专业班学号 协作者_____________教师评定_________________ 实验题目查询与排序 综合实验评分表

实验报告 一、实验目的与要求 1、掌握散列表的构造及实现散列查找； 2、掌握堆排序的算法； 3、综合比较各类排序算法的性能。 二、实验容 #include"stdio.h" #include"stdlib.h" #include"string.h" #include"windows.h" #define MAX 20 typedef struct{ unsigned long key; int result; char name[30];}RNode; RNode t[MAX],r[MAX]; int h(unsigned long k) /*散列函数*/ { return((k-3109005700)%11); } void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/ {

int i,j=0; i=h(x.key); while((j0)) j++; if(j==MAX) printf("full\n"); i=(i+j)%MAX; if(t[i].key==0) {t[i]=x;} else { if(t[i].key==x.key) printf("记录已存在!\n"); } } int search(RNode t[],unsigned long k) /*插入函数，以线性探查方法解决冲突*/ { int i,j=0; i=h(k); while((j

河南工业大学实验报告_实验三 查找和排序(一)——查找

xxx大学实验报告 课程名称数据结构实验项目实验三查找和排序(一)——查找 院系信息学院计类系专业班级计类1501 姓名学号 指导老师日期 批改日期成绩 一实验目的 1．掌握哈希函数——除留余数法的应用； 2. 掌握哈希表的建立； 3. 掌握冲突的解决方法； 4. 掌握哈希查找算法的实现。 二实验内容及要求 实验内容：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希 函数定义为：H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列，并 计算平均查找长度（设每个记录的查找概率相等）。 实验要求：1. 哈希表定义为定长的数组结构；2. 使用线性探测再散列或链 地址法解决冲突；3. 散列完成后在屏幕上输出数组内容或链表；4. 输出等概率 查找下的平均查找长度；5. 完成散列后，输入关键字完成查找操作，要分别测 试查找成功与不成功两种情况。 注意：不同解决冲突的方法会使得平均查找长度不同，可尝试使用不同解决 冲突的办法，比较平均查找长度。（根据完成情况自选，但至少能使用一种方法 解决冲突） 三实验过程及运行结果 #include #include #include #define hashsize 16

#define q 13 int sign=2; typedef struct Hash { int date; //值域 int sign; //标记 }HashNode; void compare(HashNode H[],int p,int i,int key[]) //线性冲突处理{ p++; if(H[p].sign!=0) { sign++; compare(H,p,i,key); } else { H[p].date=key[i]; H[p].sign=sign; sign=2; } } void Hashlist(HashNode H[],int key[]) { int p; for(int i=0;i<12;i++) { p=key[i]%q; if(H[p].sign==0) { H[p].date=key[i]; H[p].sign=1; } else compare(H,p,i,key); } } int judge(HashNode H[],int num,int n) //查找冲突处理 {

数据结构内排序实验报告

一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序e xp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序 过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include #define MAXE 20 //线性表中最多元素个数 typedef int KeyType; typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i=0 && temp.key

数据结构各种排序实验报告

目录 1.引言............................................................................................................................ 错误！未定义书签。 2.需求分析 (2) 3.详细设计 (2) 3.1 直接插入排序 (2) 3.2折半排序 (2) 3.3 希尔排序 (4) 3.4简单选择排序 (4) 3.5堆排序 (4) 3.6归并排序 (5) 3.7冒泡排序 (7) 4.调试 (8) 5.调试及检验 (9) 5.1 直接插入排序 (9) 5.2折半插入排序 (9) 5.3 希尔排序 (10) 5.4简单选择排序 (10) 5.5堆排序 (11) 5.6归并排序 (12) 5.7冒泡排序 (12) 6.测试与比较................................................................................................................ 错误！未定义书签。 6.1调试步骤......................................................................................................... 错误！未定义书签。 6.2结论 (13) 7.实验心得与分析 (13) 8.附录 (15) 8.1直接插入排序 (15) 8.2折半插入排序 (16) 8.3希尔排序 (18) 8.4简单选择排序 (20) 8.5堆排序 (21) 8.6归并排序 (24) 8.7冒泡排序 (27) 8.8主程序 (28)

查询与排序实验报告

_________ 学院_________ 专业____________ 班学号_______________ 姓名___________ 协作者______________ 师评定____________________ 实验题目查询与排序 综合实验评分表

实验报告 实验目的与要求 1、掌握散列表的构造及实现散列查找; 2、掌握堆排序的算法； 3、综合比较各类排序算法的性能。 二、实验内容 #include "stdio.h" #include "stdlib.h" #include "string.h" #include "windows.h" #define MAX 20 typedef struct{ unsigned long key; int result; char name[30]; }RNode; RNode t[MAX],r[MAX]; int h( unsigned long k) /* 散列函数*/ { return ((k - 3109005700)%11); } void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/ { int i,j =0; i =h(x. key); while ((j 0)) j ++; if (j ==MAX) printf( "full\n"); i =(i +j) %/IAX; if (t[i] . key==0) {t[i] =x;} else { if (t[i] . key==x. key) printf( "记录已存在!\n"); } } int search(RNode t[], unsigned long k) /*插入函数，以线性探查方法解决冲突*/ {

实验报告_排序与查找

电子科技大学信息与软件工程学院实验报告 电子科技大学实验报告 课程名称：数据结构与算法 学生姓名： 学号： 点名序号： 指导教师： 实验地点：基础实验大楼 实验时间：5月20日 2014-2015-2 学期 信息与软件工程学院

实验报告（二） 学生姓名学号：指导教师： 实验地点：基础实验大楼实验时间：5月20日 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时： 4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的 所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快 速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1] ?? A[N]，首先任意选取一个数据（通常选用第一个数据） 作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、 J，排序开始的时候I ：=1， J： =N 2）以第一个数组元素作为关键数据，赋值给X ，即 X ：=A[1] ； 3）从 J 开始向前搜索，即（J：=J-1），找到第一个小于X 的值，两者交换； 4）从 I 开始向后搜索，即（I ： =I+1 ），找到第一个大于X 的值，两者交换； 5）重复第 3、 4 步，直到I=J 。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置： mid= （ low+high ）/2 min 代表区间中间的结点的位置，low 代表区间最左结点位置，high 代表区间最右结点位置 （2）将待查 a 值与结点 mid 的关键字（下面用 R[mid].key ）比较，若相等，则查找成功，否则确定新的查找区间： A) 如果 R[mid].key>a ，则由表的有序性可知，R[mid].key 右侧的值都大于a，所以等于 a 的关键字如果存在，必然在R[mid].key 左边的表中 ,这时 high=mid-1; B) 如果 R[mid].key