查找排序实验报告

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

目录HYPERLINK一、需求分析…………………31.任务规定……………………32.软件功能分析………………33.数据准备……………………3HYPERLINK二、概要设计…………………31.功能模块图………………42.模块间调用关系…………43.主程序模块………………54.抽象数据类型描述…………5HYPERLINK三、详细设计…………………61.存储构造定义………………62.各功能模块的详细设计……………………7HYPERLINK四、实现和调试………………71.重要的算法………………72.重要问题及处理…………83.测试执行及成果……………8HYPERLINK五、改善………………………9HYPERLINK六、附录……………………9HYPERLINK1.查找源程序………………9HYPERLINK2.排序源程序………………9

目录1

需求分析

1.1

任务规定

对于从键盘随机输入的一种序列的数据，存入计算机内，给出多种查找算法的实现；以及多种排序算法的实现。1.2

软件功能分析 任意输入n个正整数，该程序可以实现各类查找及排序的功能并将成果输出。1.3

数据准备 任意输入了5个正整数如下：12234556782

概要设计（假如2，3合并可以省略2.4）

2.1

功能模块图（注：含功能阐明）2.2

模块间调用关系

2.3

主程序模块

2.4

抽象数据类型描述 存储构造：数据构造在计算机中的表达（也称映像）叫做物理构造。又称为存储构造。数据类型（datatype）是一种“值”的集合和定义在此集合上的一组操作的总称。3

详细设计3.1

存储构造定义查找：typedefintElemType;//次序存储构造typedefstruct{ ElemType*elem;//数据元素存储空间基址，建表时按实际长度分派，号单元留空 intlength;//表的长度}SSTable;排序：typedefstruct{//定义记录类型 intkey;//关键字项}RecType;typedefRecTypeSeqList[Max+1];//SeqList为次序表，表中第0个元素作为哨兵3.2

各功能模块的详细设计查找：voidCreate(SSTable*table,intlength); //构建次序表voidFillTable(SSTable*table)//无序表的输入intSearch_Seq(SSTable*table,ElemTypekey); //哨兵查找算法 voidSort(SSTable*table)//排序算法intSearch_Bin(SSTable*table,ElemTypekey)//二分法查找（非递归） 排序：voidInsertSort(SeqListR)//对次序表R中的记录R[1‥n]按递增序进行插入排序voidBubbleSort(SeqListR)//自下向上扫描对R做冒泡排序intPartition(SeqListR,inti,intj)//对R[i‥j]做一次划分，并返回基准记录的位置voidQuickSort(SeqListR,intlow,inthigh)//R[low..high]迅速排序voidSelectSort(SeqListR)//直接选择排序voidHeapify(SeqListR,intlow,inthigh)//大根堆调整函数voidMergePass(SeqListR,intlength)//归并排序4

实现和调试4.1

重要的算法查找：①建立次序存储构造，构建一种次序表，实现次序查找算法。typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分派，号单元留空intlength;//表的长度}SSTable;②对次序表先排序后，实现行二分法查找有关操作。③定义二叉树节点，根据节点的值进行查找，并且实现节点的插入，删除等操作。typedefstructBiTnode{//定义二叉树节点 intdata;//节点的值 structBiTnode*lchild,*rchild;}BiTnode,*BiTree;④定义哈希表以及要查找的节点元素，创立哈希表，实现其有关查找操作。typedefstruct{intnum; }Elemtype;//定义查找的结点元素typedefstruct{Elemtype*elem;//数据元素存储基址 intcount;//数据元素个数 intsizeindex;}HashTable;//定义哈希表排序：2.排序有关试验内容及环节。①定义记录类型。typedefstruct{intkey;//关键字项}RecType;②实现直接插入排序：每次将一种待排序的记录，按其关键字大小插入到前面已排序好的子文献中的合适位置，直到所有记录插入完毕为止。③实现冒泡排序：设想被排序的记录数组R[1‥n]垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（互换），如此反复进行，直到最终任意两个气泡都是轻者在上，重者在下为止。④实现迅速排序：在待排序的n个记录中任取一种记录（一般取第一种记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别反复上述过程，直到每部分只有一种记录为止。⑤实现直接选择排序：第i趟排序开始时，目前有序区和无序辨别别为R[1‥i-1]和R[i‥n]（1≤i≤n-1），该趟排序则是从目前无序区中选择出关键字最小的记录R[k]，将它与无序区的的第一种记录R[i]互换，有序区增长一种记录，使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。⑥实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R[1‥n]当作是一种完全二叉树的次序存储构造，运用完全二叉树中双亲结点和孩子结点之间的内在关系，在目前无序区中选择关键字最大（或最小）的记录。即：把待排序文献的关键字寄存在数组R[1‥n]子中，将R当作是一棵二叉树，每个结点表达一种记录，源文献的第一种记录R[1]作为二叉树的根，如下各记录R[2‥n]依次逐层从左到右排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]。⑦实现二路归并排序：假设初始序列n个记录，则可当作是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此反复，直到一种长度为n的有序序列为止。4.2

重要问题及处理 在试验前对于多种查找和排序的算法不是很熟悉，因此花了某些时间去复习。有些代码反复测试还是找不出错误，最终也是翻阅了书本并仔细思索才改善了算法并成功测试出了成果。这次试验大大提高了我对排序算法及查找算法的纯熟程度。4.3

测试执行及成果 查找算法：任意输入若干正整数并测试如下：排序算法：任意输入数字并测试如下：5

改善 根据提醒的代码，通过一系列调试后最终出了成果。在一开始运行时总是出错，尤其是二叉树的测试，代码有些小错误导致测试的时候程序总是出错。最终改动了一下提高了程序的稳定性并成功运行出了成果。6附录【附录1----查找源程序】#include"iostream"#include"stdlib.h"#include"stdio.h"#include"malloc.h"#defineMAX11usingnamespacestd;typedefintElemType;//次序存储构造typedefstruct{ ElemType*elem;//数据元素存储空间基址，建表时按实际长度分派，号单元留空 intlength;//表的长度}SSTable;voidCreate(SSTable*table,intlength); voidDestroy(SSTable*table);intSearch_Seq(SSTable*table,ElemTypekey); voidTraverse(SSTable*table,void(*visit)(ElemTypeelem));voidCreate(SSTable**table,intlength)//构建次序表{ SSTable*t=(SSTable*)malloc(sizeof(SSTable));//分派空间 t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1)); t->length=length; *table=t;}voidFillTable(SSTable*table)//无序表的输入{ ElemType*t=table->elem; for(inti=0;i<table->length;i++)//for循环，输入各个元素 { t++; scanf("%d",t);//输入元素 getchar(); }}voidDestroy(SSTable*table)//销毁表{ free(table->elem);//释放元素空间 free(table);//释放表的空间}voidPrintTable(SSTable*table)//打印查找表{inti;//定义变量 ElemType*t=table->elem; for(i=0;i<table->length;i++)//进入循环，依次打印表中元素 { t++; printf("%d",*t);//打印输出 } printf("\n");}intSearch_Seq(SSTable*table,ElemTypekey)//哨兵查找算法{ table->elem[0]=key;//设置哨兵 intresult=0;//找不届时，返回 inti; for(i=table->length;i>=1;i--) {if(table->elem[i]==key) { result=i; break; } } returnresult;//返回成果}voidprintSeq(){ SSTable*table;//先设置几种变量 intr; int n; ElemTypekey; printf("请输入元素个数:");scanf("%d",&n);//输入元素个数 Create(&table,n);//建立表 printf("请输入");cout<<n;printf("个值："); FillTable(table);//输入无序表的值 printf("您输入的%d个值是：\n",n); PrintTable(table);//打印无序表 printf("请输入关键字的值:"); scanf("%d",&key); printf("\n"); printf("次序查找法运行成果如下：\n\n"); Search_Seq(table,key);//哨兵查找算法 r=Search_Seq(table,key); if(r>0) { printf("关键字%d在表中的位置是：%d\n",key,r);//打印关键字在表中的位置 printf("\n"); } else//查找失败 { printf("查找失败，表中无此数据。\n\n"); }}voidSort(SSTable*table)//排序算法{ inti,j; ElemTypetemp; for(i=table->length;i>=1;i--)//从前去后找 {for(j=1;j<i;j++) { if(table->elem[j]>table->elem[j+1]) { temp=table->elem[j]; table->elem[j]=table->elem[j+1]; table->elem[j+1]=temp; } } }}intSearch_Bin(SSTable*table,ElemTypekey)//二分法查找（非递归）{ intlow=1; inthigh=table->length; intresult=0;//找不届时，返回 while(low<=high)//low不不小于high时 { intmid=(low+high)/2; if(table->elem[mid]==key)//假如找到 { result=mid; break; } elseif(key<table->elem[mid])//假如关键字不不小于mid对应的值 { high=mid-1; } else { low=mid+1; } } returnresult;//返回成果}voidprintBin(){ SSTable*table;//申明变量 intr; int n; ElemTypekey; printf("请输入元素个数:"); scanf("%d",&n); Create(&table,n);//建立表 printf("请输入");cout<<n;printf("个值："); FillTable(table);//输入无序表的值 printf("您输入的%d个值是：\n",n); PrintTable(table);//打印无序表 printf("请输入关键字的值:"); scanf("%d",&key); printf("\n"); Sort(table);//对无序表进行排序 printf("数据排序后的次序如下：\n\n"); PrintTable(table);//打印有序表 printf("\n"); printf("二分查找法的运行成果如下：\n\n"); r=Search_Bin(table,key);//二分（非递归）查找算法 if(r>0) printf("关键字%d在表中的位置是：%d\n",key,r); else { printf("查找失败，表中无此数据。\n\n"); }}//二叉排序树typedefstructBiTnode//定义二叉树节点{ intdata;//节点的值 structBiTnode*lchild,*rchild;//节点的左孩子，节点的右孩子}BiTnode,*BiTree;//查找（根据节点的值查找）返回节点指针BiTreesearch_tree(BiTreeT,intkeyword,BiTree*father){ BiTreep;//临时指针变量 *father=NULL;//先设其父亲节点指向空 p=T;//p赋值为根节点（从根节点开始查找） while(p&&p->data!=keyword)//假如不是p不指向空且未找到相似值的节点 { *father=p;//先将父亲指向自己（注意：这里传过来的father是二级指针） if(keyword<p->data)//假如要找的值不不小于自己的值 p=p->lchild;//就向自己的左孩子开始找 else p=p->rchild;//否则向自己的右孩子开始查找 } returnp;//假如找到了则返回节点指针}BiTreecreat_tree(intcount){ BiTreeT,p;//设置两个临时变量T,p inti=1; while(i<=count) { if(i==1)//假如i=1，阐明还是空树 { p=(BiTnode*)malloc(sizeof(BiTree));//使p指向新分派的节点 if(!p)//分派未成功 returnNULL; T=p;//分派成功,T=p(这里实际上T就是根节点) scanf("%d",&p->data);//输入p指向节点的值 p->lchild=p->rchild=NULL;//p的左孩子和右孩子都指向空 i++; } else { inttemp;//假如不是空树 scanf("%d",&temp);//输入节点的值 search_tree(T,temp,&p);//查找节点要插入的位置。（T是根节点，插入的节点的值，父亲节点的地址） if(temp<p->data)//假如插入的值不不小于父亲节点的值 { p->lchild=(BiTnode*)malloc(sizeof(BiTnode));//那么就为父亲节点的左孩子分派一种节点空间，并指向这个空间 if(!p->lchild) returnNULL; p=p->lchild;//分派成功，p指向自己的左孩子 } else//假如插入的值不小于父亲节点的值 { p->rchild=(BiTnode*)malloc(sizeof(BiTnode)); if(!p->rchild) returnNULL;//分派不成功，退出 p=p->rchild;//p指向自己的右孩子 } p->data=temp;//新分派的节点的值赋值为插入的值 p->lchild=p->rchild=NULL;//使其左右节点均为NULL i++; } } returnT;//返回根节点}voidInOrder(BiTreeT){ if(T) { InOrder(T->lchild); printf("%d",T->data); InOrder(T->rchild); }}intinsert_tree(BiTree*T,intelem)//插入（根节点，插入的值）返回-1和,-1代表插入失败，代表成功{ BiTrees,p,father; s=(BiTnode*)malloc(sizeof(BiTnode));//s指向新开辟一种节点 if(!s)//为开辟成功 return-1;//返回值-1 s->data=elem;//新节点的值赋值为插入的值 s->lchild=s->rchild=NULL;//其左右孩子为空 p=search_tree(*T,elem,&father);//p赋值为要插入的节点 if(!p) return-1;//未开辟成功，返回-1 if(father==NULL)//假如父亲节点指向空，阐明是空树 *T=s;//让根节点指向s elseif(elem<father->data)//否则假如插入的值不不小于父亲的值 father->lchild=s;//父亲的左孩子赋值为s else father->rchild=s;//否则父亲的右孩子赋值为s return0;//返回}intdelete_tree(BiTree*T,intelem)//删除树结点的操作{ BiTrees,p,q,father;//申明变量 p=search_tree(*T,elem,&father);//查找 if(!p) return-1; if(!p->lchild)//假如p的左孩子为空 { if(father==NULL) { *T=p->rchild;//T指向左孩子 free(p);//释放p return0; } if(p==father->lchild)//假如p和father的左孩子相等 father->lchild=p->rchild;//将p的左孩子的值赋给father的左孩子 else father->rchild=p->rchild;//将p的左孩子的值赋给father的右孩子 free(p);//释放p return0; } else if(!p->rchild) { if(father==NULL)//假如father为空 { *T=p->lchild;//将p的左孩子赋给T free(p);//释放p return0; } if(p==father->lchild)//假如p等于father的左孩子的值 father->lchild=p->lchild;//将p的左孩子的值赋给father的左孩子 else father->rchild=p->lchild;//将p的左孩子的值赋给father的右孩子 free(p); return0; } else { q=p; s=p->lchild;//将p的左孩子赋给s while(s->rchild) { q=s; s=s->rchild; } p->data=s->data;//将s的值赋给p if(q!=p)//假如q不等于p q->rchild=s->lchild;//将s的左孩子值赋给p的右孩子 else q->lchild=s->lchild;//将s的左孩子值赋给p的右孩子 free(s);//释放s return0; }}voidprint1()//定义print1（）以便调用{ printf("\t**********************\n"); printf("\t1,输出中序遍历\n"); printf("\t2,插入一种结点\n"); printf("\t3,删除一种结点\n"); printf("\t4,查找一种结点\n"); printf("\t5,返回主菜单\n"); printf("\t**********************\n");}voidprintTree(){ BiTreeT,p;//申明变量 T=NULL; int i,n; ElemTypekey; printf("请输入结点个数：\n"); scanf("%d",&n);//输入值 printf("请输入");cout<<n;printf("个值："); T=creat_tree(n);//建立树 print1(); scanf("%d",&i);//输入各个值 while(i!=5)//i不等于5时 { switch(i) { case1: printf("中序遍历二叉树成果如下：\n"); InOrder(T);//中序遍历 break; case2: printf("请输入要插入的结点值："); scanf("%d",&key);//输入要查找的关键字 if(insert_tree(&T,key))//假如插入成功 printf("插入成功！"); else printf("已存在此元素！"); break; case3: printf("请输入要删除的结点值："); scanf("%d",&key);//输入要删除的关键字 if(!(delete_tree(&T,key)))//假如删除成功 printf("删除成功！"); else printf("不存在此元素！"); break; case4: printf("请输入要查找的结点值："); scanf("%d",&key);//输入要查找的关键字 if(search_tree(T,key,&p))//假如查找成功 printf("查找成功！"); else printf("不存在此元素！"); break; default: printf("按键错误！"); } printf("\n"); print1(); scanf("%d",&i); }}//哈希表typedefstruct{ intnum;}Elemtype;//定义查找的结点元素typedefstruct{ Elemtype*elem;//数据元素存储基址 intcount;//数据元素个数 intsizeindex;}HashTable;//定义哈希表intHash(intnum){ intp; p=num%11; returnp;}//定义哈希函数//冲突处理函数，采用二次探测再散列法处理冲突intcollision(intp,int&c){ inti,q; i=c/2+1; while(i<MAX) { if(c%2==0) { c++; q=(p+i*i)%MAX; if(q>=0)returnq; elsei=c/2+1; } else { q=(p-i*i)%MAX; c++; if(q>=0) returnq; else i=c/2+1; } } return0;}voidInitHash(HashTable*H)//创立哈希表{ inti;H->elem=(Elemtype*)malloc(MAX*sizeof(Elemtype)); H->count=0; H->sizeindex=MAX; for(i=0;i<MAX;i++) H->elem[i].num=0;//初始化，使SearHash函数能判断究竟有无元素在里面}intSearHash(HashTableH,intkey,int*p)//查找函数{ *p=Hash(key); while(H.elem[*p].num!=key&&H.elem[*p].num!=0) *p=*p+1; if(H.elem[*p].num==key) return1; else return0;}voidInsertHash(HashTable*H,Elemtypee){//假如查找不到就插入元素 intp; SearHash(*H,e.num,&p);//查找 H->elem[p]=e; ++H->count;}voidprintHash()//调用哈希表{ HashTableH; intp,key,i,n; Elemtypee; InitHash(&H); printf("输入数据个数(<11):"); scanf("%d",&n); printf("请输入各个值："); for(i=0;i<n;i++) {//输入n个元素 scanf("%d",&e.num);//输入数字 if(!SearHash(H,e.num,&p)) { InsertHash(&H,e);//插入元素 } else printf("已经存在\n");//否则就表达元素的数字已经存在 } printf("输入查找的数字:"); scanf("%d",&key);//输入要查找的数字 if(SearHash(H,key,&p))//能查找成功 { printf("查找成功！");//输出位置 } else printf("不存在此元素！");}voidprint(){ printf("\t**********************\n"); printf("\t1,次序查找\n"); printf("\t2,二分查找\n"); printf("\t3,二叉排序树\n"); printf("\t4,哈希查找\n"); printf("\t5,退出\n"); printf("\t**********************\n"); printf("请选择查找方式：\n");}//主函数intmain(intargc,char*argv[]){ inti;//定义变量 print(); scanf("%d",&i);//输入要数字选择要使用的查找措施 while(i!=5)//i不等于5时 { switch(i) { case1://i=1时 printf("次序查找法：\n"); printSeq();//次序查找法 break;//跳出循环} case2: printf("二分查找法：\n"); printBin();//二分查找法 break;//跳出循环 case3: printf("二叉排序树：\n"); printTree();//二叉排序树 break;//跳出循环 case4: printf("哈希查找法：\n"); printHash();//哈希查找法 break;//跳出循环 default: printf("按键错误！"); } printf("\n"); print();//调用函数print() scanf("%d",&i); } return0;//返回0}【附录2----排序源程序】#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMax100typedefstruct{//定义记录类型 intkey;//关键字项}RecType;typedefRecTypeSeqList[Max+1];//SeqList为次序表，表中第0个元素作为哨兵intn;//次序表实际的长度//1、直接插入排序的基本思想：每次将一种待排序的记录，按其关键字大小插入到前面已排序好的子文献中的合适位置，直到所有记录插入完毕为止。//==========直接插入排序法======voidInsertSort(SeqListR)//对次序表R中的记录R[1‥n]按递增序进行插入排序{ inti,j; for(i=2;i<=n;i++)//依次插入R[2]，……，R[n] if(R[i].key<R[i-1].key) {//若R[i].key不小于等于有序区中所有的keys，则R[i]留在原位 R[0]=R[i];j=i-1;//R[0]是R[i]的副本 do {//从右向左在有序区R[1‥i-1]中查找R[i]的位置 R[j+1]=R[j];//将关键字不小于R[i].key的记录后移 j--; }while(R[0].key<R[j].key);//当R[i].key≥R[j].key是终止 R[j+1]=R[0];//R[i]插入到对的的位置上 }}//2、冒泡排序的基本思想：设想被排序的记录数组R[1‥n]垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"（互换），如此反复进行，直到最终任意两个气泡都是轻者在上，重者在下为止。//==========冒泡排序=======typedefenum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1voidBubbleSort(SeqListR){//自下向上扫描对R做冒泡排序 inti,j;Booleanexchange;//互换标志 for(i=1;i<n;i++) {//最多做n-1趟排序 exchange=FALSE;//本趟排序开始前，互换标志应为假 for(j=n-1;j>=i;j--)//对目前无序区R[i‥n]自下向上扫描 if(R[j+1].key<R[j].key) {//两两比较，满足条件互换记录 R[0]=R[j+1];//R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE;//发生了互换，故将互换标志置为真 } if(!exchange)//本趟排序未发生互换，提前终止算法 return; }}//3、迅速排序的基本思想：在待排序的n个记录中任取一种记录（一般取第一种记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别反复上述过程，直到每部分只有一种记录为止。//1.========一次划分函数=====intPartition(SeqListR,inti,intj)//对R[i‥j]做一次划分，并返回基准记录的位置{ RecTypepivot=R[i];//用第一种记录作为基准 while(i<j) {//从区间两端交替向中间扫描，直到i=j while(i<j&&R[j].key>=pivot.key)//基准记录pivot相称与在位置i上 j--;//从右向左扫描，查找第一种关键字不不小于pivot.key的记录R[j] if(i<j)//若找到的R[j].key<pivot.key，则 R[i++]=R[j];//互换R[i]和R[j]，互换后i指针加1 while(i<j&&R[i].key<=pivot.key)//基准记录pivot相称与在位置j上 i++;//从左向右扫描，查找第一种关键字不不小于pivot.key的记录R[i] if(i<j)//若找到的R[i].key>pivot.key，则 R[j--]=R[i];//互换R[i]和R[j]，互换后j指针减1 } R[i]=pivot;//此时，i=j，基准记录已被最终定位 returni;//返回基准记录的位置}//2.=====迅速排序===========voidQuickSort(SeqListR,intlow,inthigh)//R[low..high]迅速排序{ intpivotpos;//划分后基准记录的位置 if(low<high) {//仅当区间长度不小于1时才排序 pivotpos=Partition(R,low,high);//对R[low..high]做一次划分，得到基准记录的位置 QuickSort(R,low,pivotpos-1);//对左区间递归排序 QuickSort(R,pivotpos+1,high);//对右区间递归排序 }}//4、直接选择排序的基本思想：第i趟排序开始时，目前有序区和无序辨别别为R[1‥i-1]和R[i‥n]（1≤i≤n-1），该趟排序则是从目前无序区中选择出关键字最小的记录R[k]，将它与无序区的的第一种记录R[i]互换，有序区增长一种记录，使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。//=====直接选择排序========voidSelectSort(SeqListR){ inti,j,k; for(i=1;i<n;i++) {//做第i趟排序（1≤i≤n-1） k=i; for(j=i+1;j<=n;j++)//在目前无序区R[i‥n]中选key最小的记录R[k] if(R[j].key<R[k].key) k=j;//k记下目前找到的最小关键字所在的位置 if(k!=i) {//互换R[i]和R[k] R[0]=R[i];R[i]=R[k];R[k]=R[0]; } }}//5、堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将R[1‥n]当作是一种完全二叉树的次序存储构造，运用完全二叉树中双亲结点和孩子结点之间的内在关系，在目前无序区中选择关键字最大（或最小）的记录。即：把待排序文献的关键字寄存在数组R[1‥n]子中，将R当作是一棵二叉树，每个结点表达一种记录，源文献的第一种记录R[1]作为二叉树的根，如下各记录R[2‥n]依次逐层从左到右排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：//R[i].key≤R[2i].key并且R[i].key≤R[2i+1].key称小堆根//或R[i].key≥R[2i].key并且R[i].key≥R[2i+1].key称大堆根//==========大根堆调整函数=======voidHeapify(SeqListR,intlow,inthigh)//将R[low..high]调整为大根堆，除R[low]外，其他结点均满足堆性质{ intlarge;//large指向调整结点的左、右孩子结点中关键字较大者 RecTypetemp=R[low];//暂存调整结点 for(large=2*low;large<=high;large*=2) {//R[low]是目前调整结点//若large>high,则表达R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子 if(large<high&&R[large].key<R[large+1].key) large++;//若R[low]的右孩子存在且关键字不小于左兄弟，则令large指向//目前R[large]是调整结点R[low]的左右孩子结点中关键字较大者 if(temp.key>=R[large].key)//temp一直对应R[low] break;//目前调整结点不不不小于其孩子结点的关键字，结束调整 R[low]=R[large];//相称于互换了R[low]和R[large] low=large;//令low指向新的调整结点，相称于temp已筛下到large的位置 } R[low]=temp;//将被调整结点放入最终位置上}//==========构造大根堆==========voidBuildHeap(SeqListR)//将初始文献R[1..n]构造为堆{ inti; for(i=n/2;i>0;i--) Heapify(R,i,n);//将R[i..n]调整为大根堆}//==========堆排序===========voidHeapSort(SeqListR)//对R[1..n]进行堆排序，不妨用R[0]做暂存单元{ inti; BuildHeap(R);//将R[1..n]构造为初始大根堆 for(i=n;i>1;i--) {//对目前无序区R[1..i]进行堆排序，共做n-1趟。 R[0]=R[1];R[1]=R[i];R[i]=R[0];//将堆顶和堆中最终一种记录互换 Heapify(R,1,i-1);//将R[1..i-1]重新调整为堆，仅有R[1]也许违反堆性质。 }}//6、二路归并排序的基本思想：假设初始序列n个记录，则可当作是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此反复，直到一种长度为n的有序序列为止。//=====将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]==voidMerge(SeqListR,intlow,intm,inthigh){ inti=low,j=m+1,p=0;//置初始值 RecType*R1;//R1为局部量 R1=(RecType*)malloc((high-low+1)*sizeof(RecType));//申请空间 while(i<=m&&j<=high)//两个子序列非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++]; while(i<=m)//若第一种子序列非空，则复制剩余记录到R1 R1[p++]=R[i++]; while(j<=high)//若第二个子序列非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p];//归并完毕后将成果复制回R[low..high]}//=========对R[1..n]做一趟归并排序========voidMergePass(SeqListR,intlength){ inti; for(i=1;i+2*length-1<=n;i=i+2*length) Merge(R,i,i+length-1,i+2*length-1);//归并长度为length的两个相邻的子序列