查找排序?qū)嶒?yàn)報(bào)告

《編程實(shí)訓(xùn)》試驗(yàn)匯報(bào)書專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：151班學(xué)號：姓名：指導(dǎo)教師：日期：6月30日

目錄HYPERLINK一、需求分析…………………31.任務(wù)規(guī)定……………………32.軟件功能分析………………33.數(shù)據(jù)準(zhǔn)備……………………3HYPERLINK二、概要設(shè)計(jì)…………………31.功能模塊圖………………42.模塊間調(diào)用關(guān)系…………43.主程序模塊………………54.抽象數(shù)據(jù)類型描述…………5HYPERLINK三、詳細(xì)設(shè)計(jì)…………………61.存儲構(gòu)造定義………………62.各功能模塊的詳細(xì)設(shè)計(jì)……………………7HYPERLINK四、實(shí)現(xiàn)和調(diào)試………………71.重要的算法………………72.重要問題及處理…………83.測試執(zhí)行及成果……………8HYPERLINK五、改善………………………9HYPERLINK六、附錄……………………9HYPERLINK1.查找源程序………………9HYPERLINK2.排序源程序………………9

目錄1

需求分析

1.1

任務(wù)規(guī)定

對于從鍵盤隨機(jī)輸入的一種序列的數(shù)據(jù)，存入計(jì)算機(jī)內(nèi)，給出多種查找算法的實(shí)現(xiàn)；以及多種排序算法的實(shí)現(xiàn)。1.2

軟件功能分析 任意輸入n個正整數(shù)，該程序可以實(shí)現(xiàn)各類查找及排序的功能并將成果輸出。1.3

數(shù)據(jù)準(zhǔn)備 任意輸入了5個正整數(shù)如下：12234556782

概要設(shè)計(jì)（假如2，3合并可以省略2.4）

2.1

功能模塊圖（注：含功能闡明）2.2

模塊間調(diào)用關(guān)系

2.3

主程序模塊

2.4

抽象數(shù)據(jù)類型描述 存儲構(gòu)造：數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的表達(dá)（也稱映像）叫做物理構(gòu)造。又稱為存儲構(gòu)造。數(shù)據(jù)類型（datatype）是一種“值”的集合和定義在此集合上的一組操作的總稱。3

詳細(xì)設(shè)計(jì)3.1

存儲構(gòu)造定義查找：typedefintElemType;//次序存儲構(gòu)造typedefstruct{ ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表時按實(shí)際長度分派，號單元留空 intlength;//表的長度}SSTable;排序：typedefstruct{//定義記錄類型 intkey;//關(guān)鍵字項(xiàng)}RecType;typedefRecTypeSeqList[Max+1];//SeqList為次序表，表中第0個元素作為哨兵3.2

各功能模塊的詳細(xì)設(shè)計(jì)查找：voidCreate(SSTable*table,intlength); //構(gòu)建次序表voidFillTable(SSTable*table)//無序表的輸入intSearch_Seq(SSTable*table,ElemTypekey); //哨兵查找算法 voidSort(SSTable*table)//排序算法intSearch_Bin(SSTable*table,ElemTypekey)//二分法查找（非遞歸） 排序：voidInsertSort(SeqListR)//對次序表R中的記錄R[1‥n]按遞增序進(jìn)行插入排序voidBubbleSort(SeqListR)//自下向上掃描對R做冒泡排序intPartition(SeqListR,inti,intj)//對R[i‥j]做一次劃分，并返回基準(zhǔn)記錄的位置voidQuickSort(SeqListR,intlow,inthigh)//R[low..high]迅速排序voidSelectSort(SeqListR)//直接選擇排序voidHeapify(SeqListR,intlow,inthigh)//大根堆調(diào)整函數(shù)voidMergePass(SeqListR,intlength)//歸并排序4

實(shí)現(xiàn)和調(diào)試4.1

重要的算法查找：①建立次序存儲構(gòu)造，構(gòu)建一種次序表，實(shí)現(xiàn)次序查找算法。typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表時按實(shí)際長度分派，號單元留空intlength;//表的長度}SSTable;②對次序表先排序后，實(shí)現(xiàn)行二分法查找有關(guān)操作。③定義二叉樹節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)的值進(jìn)行查找，并且實(shí)現(xiàn)節(jié)點(diǎn)的插入，刪除等操作。typedefstructBiTnode{//定義二叉樹節(jié)點(diǎn) intdata;//節(jié)點(diǎn)的值 structBiTnode*lchild,*rchild;}BiTnode,*BiTree;④定義哈希表以及要查找的節(jié)點(diǎn)元素，創(chuàng)立哈希表，實(shí)現(xiàn)其有關(guān)查找操作。typedefstruct{intnum; }Elemtype;//定義查找的結(jié)點(diǎn)元素typedefstruct{Elemtype*elem;//數(shù)據(jù)元素存儲基址 intcount;//數(shù)據(jù)元素個數(shù) intsizeindex;}HashTable;//定義哈希表排序：2.排序有關(guān)試驗(yàn)內(nèi)容及環(huán)節(jié)。①定義記錄類型。typedefstruct{intkey;//關(guān)鍵字項(xiàng)}RecType;②實(shí)現(xiàn)直接插入排序：每次將一種待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文獻(xiàn)中的合適位置，直到所有記錄插入完畢為止。③實(shí)現(xiàn)冒泡排序：設(shè)想被排序的記錄數(shù)組R[1‥n]垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（互換），如此反復(fù)進(jìn)行，直到最終任意兩個氣泡都是輕者在上，重者在下為止。④實(shí)現(xiàn)迅速排序：在待排序的n個記錄中任取一種記錄（一般取第一種記錄），把該記錄作為支點(diǎn)（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別反復(fù)上述過程，直到每部分只有一種記錄為止。⑤實(shí)現(xiàn)直接選擇排序：第i趟排序開始時，目前有序區(qū)和無序辨別別為R[1‥i-1]和R[i‥n]（1≤i≤n-1），該趟排序則是從目前無序區(qū)中選擇出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的的第一種記錄R[i]互換，有序區(qū)增長一種記錄，使R[1‥i],和R[i+1‥n]分別為新的有序區(qū)和新的無序區(qū)。如此反復(fù)進(jìn)行，直到排序完畢。⑥實(shí)現(xiàn)堆排序：它是一種樹型選擇排序，特點(diǎn)是：在排序的過程中，將R[1‥n]當(dāng)作是一種完全二叉樹的次序存儲構(gòu)造，運(yùn)用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在目前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?。即：把待排序文獻(xiàn)的關(guān)鍵字寄存在數(shù)組R[1‥n]子中，將R當(dāng)作是一棵二叉樹，每個結(jié)點(diǎn)表達(dá)一種記錄，源文獻(xiàn)的第一種記錄R[1]作為二叉樹的根，如下各記錄R[2‥n]依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R[i/2]。⑦實(shí)現(xiàn)二路歸并排序：假設(shè)初始序列n個記錄，則可當(dāng)作是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n/2]個長度為2或1的有序子序列；再兩兩歸并，……，如此反復(fù)，直到一種長度為n的有序序列為止。4.2

重要問題及處理 在試驗(yàn)前對于多種查找和排序的算法不是很熟悉，因此花了某些時間去復(fù)習(xí)。有些代碼反復(fù)測試還是找不出錯誤，最終也是翻閱了書本并仔細(xì)思索才改善了算法并成功測試出了成果。這次試驗(yàn)大大提高了我對排序算法及查找算法的純熟程度。4.3

測試執(zhí)行及成果 查找算法：任意輸入若干正整數(shù)并測試如下：排序算法：任意輸入數(shù)字并測試如下：5

改善 根據(jù)提醒的代碼，通過一系列調(diào)試后最終出了成果。在一開始運(yùn)行時總是出錯，尤其是二叉樹的測試，代碼有些小錯誤導(dǎo)致測試的時候程序總是出錯。最終改動了一下提高了程序的穩(wěn)定性并成功運(yùn)行出了成果。6附錄【附錄1----查找源程序】#include"iostream"#include"stdlib.h"#include"stdio.h"#include"malloc.h"#defineMAX11usingnamespacestd;typedefintElemType;//次序存儲構(gòu)造typedefstruct{ ElemType*elem;//數(shù)據(jù)元素存儲空間基址，建表時按實(shí)際長度分派，號單元留空 intlength;//表的長度}SSTable;voidCreate(SSTable*table,intlength); voidDestroy(SSTable*table);intSearch_Seq(SSTable*table,ElemTypekey); voidTraverse(SSTable*table,void(*visit)(ElemTypeelem));voidCreate(SSTable**table,intlength)//構(gòu)建次序表{ 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循環(huán)，輸入各個元素 { 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++)//進(jìn)入循環(huán)，依次打印表中元素 { t++; printf("%d",*t);//打印輸出 } printf("\n");}intSearch_Seq(SSTable*table,ElemTypekey)//哨兵查找算法{ table->elem[0]=key;//設(shè)置哨兵 intresult=0;//找不屆時，返回 inti; for(i=table->length;i>=1;i--) {if(table->elem[i]==key) { result=i; break; } } returnresult;//返回成果}voidprintSeq(){ SSTable*table;//先設(shè)置幾種變量 intr; int n; ElemTypekey; printf("請輸入元素個數(shù):");scanf("%d",&n);//輸入元素個數(shù) Create(&table,n);//建立表 printf("請輸入");cout<<n;printf("個值："); FillTable(table);//輸入無序表的值 printf("您輸入的%d個值是：\n",n); PrintTable(table);//打印無序表 printf("請輸入關(guān)鍵字的值:"); scanf("%d",&key); printf("\n"); printf("次序查找法運(yùn)行成果如下：\n\n"); Search_Seq(table,key);//哨兵查找算法 r=Search_Seq(table,key); if(r>0) { printf("關(guān)鍵字%d在表中的位置是：%d\n",key,r);//打印關(guān)鍵字在表中的位置 printf("\n"); } else//查找失敗 { printf("查找失敗，表中無此數(shù)據(jù)。\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])//假如關(guān)鍵字不不小于mid對應(yīng)的值 { high=mid-1; } else { low=mid+1; } } returnresult;//返回成果}voidprintBin(){ SSTable*table;//申明變量 intr; int n; ElemTypekey; printf("請輸入元素個數(shù):"); scanf("%d",&n); Create(&table,n);//建立表 printf("請輸入");cout<<n;printf("個值："); FillTable(table);//輸入無序表的值 printf("您輸入的%d個值是：\n",n); PrintTable(table);//打印無序表 printf("請輸入關(guān)鍵字的值:"); scanf("%d",&key); printf("\n"); Sort(table);//對無序表進(jìn)行排序 printf("數(shù)據(jù)排序后的次序如下：\n\n"); PrintTable(table);//打印有序表 printf("\n"); printf("二分查找法的運(yùn)行成果如下：\n\n"); r=Search_Bin(table,key);//二分（非遞歸）查找算法 if(r>0) printf("關(guān)鍵字%d在表中的位置是：%d\n",key,r); else { printf("查找失敗，表中無此數(shù)據(jù)。\n\n"); }}//二叉排序樹typedefstructBiTnode//定義二叉樹節(jié)點(diǎn){ intdata;//節(jié)點(diǎn)的值 structBiTnode*lchild,*rchild;//節(jié)點(diǎn)的左孩子，節(jié)點(diǎn)的右孩子}BiTnode,*BiTree;//查找（根據(jù)節(jié)點(diǎn)的值查找）返回節(jié)點(diǎn)指針BiTreesearch_tree(BiTreeT,intkeyword,BiTree*father){ BiTreep;//臨時指針變量 *father=NULL;//先設(shè)其父親節(jié)點(diǎn)指向空 p=T;//p賦值為根節(jié)點(diǎn)（從根節(jié)點(diǎn)開始查找） while(p&&p->data!=keyword)//假如不是p不指向空且未找到相似值的節(jié)點(diǎn) { *father=p;//先將父親指向自己（注意：這里傳過來的father是二級指針） if(keyword<p->data)//假如要找的值不不小于自己的值 p=p->lchild;//就向自己的左孩子開始找 else p=p->rchild;//否則向自己的右孩子開始查找 } returnp;//假如找到了則返回節(jié)點(diǎn)指針}BiTreecreat_tree(intcount){ BiTreeT,p;//設(shè)置兩個臨時變量T,p inti=1; while(i<=count) { if(i==1)//假如i=1，闡明還是空樹 { p=(BiTnode*)malloc(sizeof(BiTree));//使p指向新分派的節(jié)點(diǎn) if(!p)//分派未成功 returnNULL; T=p;//分派成功,T=p(這里實(shí)際上T就是根節(jié)點(diǎn)) scanf("%d",&p->data);//輸入p指向節(jié)點(diǎn)的值 p->lchild=p->rchild=NULL;//p的左孩子和右孩子都指向空 i++; } else { inttemp;//假如不是空樹 scanf("%d",&temp);//輸入節(jié)點(diǎn)的值 search_tree(T,temp,&p);//查找節(jié)點(diǎn)要插入的位置。（T是根節(jié)點(diǎn)，插入的節(jié)點(diǎn)的值，父親節(jié)點(diǎn)的地址） if(temp<p->data)//假如插入的值不不小于父親節(jié)點(diǎn)的值 { p->lchild=(BiTnode*)malloc(sizeof(BiTnode));//那么就為父親節(jié)點(diǎn)的左孩子分派一種節(jié)點(diǎn)空間，并指向這個空間 if(!p->lchild) returnNULL; p=p->lchild;//分派成功，p指向自己的左孩子 } else//假如插入的值不小于父親節(jié)點(diǎn)的值 { p->rchild=(BiTnode*)malloc(sizeof(BiTnode)); if(!p->rchild) returnNULL;//分派不成功，退出 p=p->rchild;//p指向自己的右孩子 } p->data=temp;//新分派的節(jié)點(diǎn)的值賦值為插入的值 p->lchild=p->rchild=NULL;//使其左右節(jié)點(diǎn)均為NULL i++; } } returnT;//返回根節(jié)點(diǎn)}voidInOrder(BiTreeT){ if(T) { InOrder(T->lchild); printf("%d",T->data); InOrder(T->rchild); }}intinsert_tree(BiTree*T,intelem)//插入（根節(jié)點(diǎn)，插入的值）返回-1和,-1代表插入失敗，代表成功{ BiTrees,p,father; s=(BiTnode*)malloc(sizeof(BiTnode));//s指向新開辟一種節(jié)點(diǎn) if(!s)//為開辟成功 return-1;//返回值-1 s->data=elem;//新節(jié)點(diǎn)的值賦值為插入的值 s->lchild=s->rchild=NULL;//其左右孩子為空 p=search_tree(*T,elem,&father);//p賦值為要插入的節(jié)點(diǎn) if(!p) return-1;//未開辟成功，返回-1 if(father==NULL)//假如父親節(jié)點(diǎn)指向空，闡明是空樹 *T=s;//讓根節(jié)點(diǎn)指向s elseif(elem<father->data)//否則假如插入的值不不小于父親的值 father->lchild=s;//父親的左孩子賦值為s else father->rchild=s;//否則父親的右孩子賦值為s return0;//返回}intdelete_tree(BiTree*T,intelem)//刪除樹結(jié)點(diǎn)的操作{ 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（）以便調(diào)用{ printf("\t**********************\n"); printf("\t1,輸出中序遍歷\n"); printf("\t2,插入一種結(jié)點(diǎn)\n"); printf("\t3,刪除一種結(jié)點(diǎn)\n"); printf("\t4,查找一種結(jié)點(diǎn)\n"); printf("\t5,返回主菜單\n"); printf("\t**********************\n");}voidprintTree(){ BiTreeT,p;//申明變量 T=NULL; int i,n; ElemTypekey; printf("請輸入結(jié)點(diǎn)個數(shù)：\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("請輸入要插入的結(jié)點(diǎn)值："); scanf("%d",&key);//輸入要查找的關(guān)鍵字 if(insert_tree(&T,key))//假如插入成功 printf("插入成功！"); else printf("已存在此元素！"); break; case3: printf("請輸入要刪除的結(jié)點(diǎn)值："); scanf("%d",&key);//輸入要刪除的關(guān)鍵字 if(!(delete_tree(&T,key)))//假如刪除成功 printf("刪除成功！"); else printf("不存在此元素！"); break; case4: printf("請輸入要查找的結(jié)點(diǎn)值："); scanf("%d",&key);//輸入要查找的關(guān)鍵字 if(search_tree(T,key,&p))//假如查找成功 printf("查找成功！"); else printf("不存在此元素！"); break; default: printf("按鍵錯誤！"); } printf("\n"); print1(); scanf("%d",&i); }}//哈希表typedefstruct{ intnum;}Elemtype;//定義查找的結(jié)點(diǎn)元素typedefstruct{ Elemtype*elem;//數(shù)據(jù)元素存儲基址 intcount;//數(shù)據(jù)元素個數(shù) intsizeindex;}HashTable;//定義哈希表intHash(intnum){ intp; p=num%11; returnp;}//定義哈希函數(shù)//沖突處理函數(shù)，采用二次探測再散列法處理沖突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)//創(chuàng)立哈希表{ 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函數(shù)能判斷究竟有無元素在里面}intSearHash(HashTableH,intkey,int*p)//查找函數(shù){ *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()//調(diào)用哈希表{ HashTableH; intp,key,i,n; Elemtypee; InitHash(&H); printf("輸入數(shù)據(jù)個數(shù)(<11):"); scanf("%d",&n); printf("請輸入各個值："); for(i=0;i<n;i++) {//輸入n個元素 scanf("%d",&e.num);//輸入數(shù)字 if(!SearHash(H,e.num,&p)) { InsertHash(&H,e);//插入元素 } else printf("已經(jīng)存在\n");//否則就表達(dá)元素的數(shù)字已經(jīng)存在 } printf("輸入查找的數(shù)字:"); scanf("%d",&key);//輸入要查找的數(shù)字 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");}//主函數(shù)intmain(intargc,char*argv[]){ inti;//定義變量 print(); scanf("%d",&i);//輸入要數(shù)字選擇要使用的查找措施 while(i!=5)//i不等于5時 { switch(i) { case1://i=1時 printf("次序查找法：\n"); printSeq();//次序查找法 break;//跳出循環(huán)} case2: printf("二分查找法：\n"); printBin();//二分查找法 break;//跳出循環(huán) case3: printf("二叉排序樹：\n"); printTree();//二叉排序樹 break;//跳出循環(huán) case4: printf("哈希查找法：\n"); printHash();//哈希查找法 break;//跳出循環(huán) default: printf("按鍵錯誤！"); } printf("\n"); print();//調(diào)用函數(shù)print() scanf("%d",&i); } return0;//返回0}【附錄2----排序源程序】#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMax100typedefstruct{//定義記錄類型 intkey;//關(guān)鍵字項(xiàng)}RecType;typedefRecTypeSeqList[Max+1];//SeqList為次序表，表中第0個元素作為哨兵intn;//次序表實(shí)際的長度//1、直接插入排序的基本思想：每次將一種待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文獻(xiàn)中的合適位置，直到所有記錄插入完畢為止。//==========直接插入排序法======voidInsertSort(SeqListR)//對次序表R中的記錄R[1‥n]按遞增序進(jìn)行插入排序{ inti,j; for(i=2;i<=n;i++)//依次插入R[2]，……，R[n] if(R[i].key<R[i-1].key) {//若R[i].key不小于等于有序區(qū)中所有的keys，則R[i]留在原位 R[0]=R[i];j=i-1;//R[0]是R[i]的副本 do {//從右向左在有序區(qū)R[1‥i-1]中查找R[i]的位置 R[j+1]=R[j];//將關(guān)鍵字不小于R[i].key的記錄后移 j--; }while(R[0].key<R[j].key);//當(dāng)R[i].key≥R[j].key是終止 R[j+1]=R[0];//R[i]插入到對的的位置上 }}//2、冒泡排序的基本思想：設(shè)想被排序的記錄數(shù)組R[1‥n]垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"（互換），如此反復(fù)進(jìn)行，直到最終任意兩個氣泡都是輕者在上，重者在下為止。//==========冒泡排序=======typedefenum{FALSE,TRUE}Boolean;//FALSE為0，TRUE為1voidBubbleSort(SeqListR){//自下向上掃描對R做冒泡排序 inti,j;Booleanexchange;//互換標(biāo)志 for(i=1;i<n;i++) {//最多做n-1趟排序 exchange=FALSE;//本趟排序開始前，互換標(biāo)志應(yīng)為假 for(j=n-1;j>=i;j--)//對目前無序區(qū)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;//發(fā)生了互換，故將互換標(biāo)志置為真 } if(!exchange)//本趟排序未發(fā)生互換，提前終止算法 return; }}//3、迅速排序的基本思想：在待排序的n個記錄中任取一種記錄（一般取第一種記錄），把該記錄作為支點(diǎn)（又稱基準(zhǔn)記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別反復(fù)上述過程，直到每部分只有一種記錄為止。//1.========一次劃分函數(shù)=====intPartition(SeqListR,inti,intj)//對R[i‥j]做一次劃分，并返回基準(zhǔn)記錄的位置{ RecTypepivot=R[i];//用第一種記錄作為基準(zhǔn) while(i<j) {//從區(qū)間兩端交替向中間掃描，直到i=j while(i<j&&R[j].key>=pivot.key)//基準(zhǔn)記錄pivot相稱與在位置i上 j--;//從右向左掃描，查找第一種關(guān)鍵字不不小于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)//基準(zhǔn)記錄pivot相稱與在位置j上 i++;//從左向右掃描，查找第一種關(guān)鍵字不不小于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，基準(zhǔn)記錄已被最終定位 returni;//返回基準(zhǔn)記錄的位置}//2.=====迅速排序===========voidQuickSort(SeqListR,intlow,inthigh)//R[low..high]迅速排序{ intpivotpos;//劃分后基準(zhǔn)記錄的位置 if(low<high) {//僅當(dāng)區(qū)間長度不小于1時才排序 pivotpos=Partition(R,low,high);//對R[low..high]做一次劃分，得到基準(zhǔn)記錄的位置 QuickSort(R,low,pivotpos-1);//對左區(qū)間遞歸排序 QuickSort(R,pivotpos+1,high);//對右區(qū)間遞歸排序 }}//4、直接選擇排序的基本思想：第i趟排序開始時，目前有序區(qū)和無序辨別別為R[1‥i-1]和R[i‥n]（1≤i≤n-1），該趟排序則是從目前無序區(qū)中選擇出關(guān)鍵字最小的記錄R[k]，將它與無序區(qū)的的第一種記錄R[i]互換，有序區(qū)增長一種記錄，使R[1‥i],和R[i+1‥n]分別為新的有序區(qū)和新的無序區(qū)。如此反復(fù)進(jì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++)//在目前無序區(qū)R[i‥n]中選key最小的記錄R[k] if(R[j].key<R[k].key) k=j;//k記下目前找到的最小關(guān)鍵字所在的位置 if(k!=i) {//互換R[i]和R[k] R[0]=R[i];R[i]=R[k];R[k]=R[0]; } }}//5、堆排序的基本思想：它是一種樹型選擇排序，特點(diǎn)是：在排序的過程中，將R[1‥n]當(dāng)作是一種完全二叉樹的次序存儲構(gòu)造，運(yùn)用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在目前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?。即：把待排序文獻(xiàn)的關(guān)鍵字寄存在數(shù)組R[1‥n]子中，將R當(dāng)作是一棵二叉樹，每個結(jié)點(diǎn)表達(dá)一種記錄，源文獻(xiàn)的第一種記錄R[1]作為二叉樹的根，如下各記錄R[2‥n]依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R[i/2]。對這棵完全二叉樹的結(jié)點(diǎn)進(jìn)行調(diào)整，使各結(jié)點(diǎn)的關(guān)鍵字滿足下列條件：//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稱大堆根//==========大根堆調(diào)整函數(shù)=======voidHeapify(SeqListR,intlow,inthigh)//將R[low..high]調(diào)整為大根堆，除R[low]外，其他結(jié)點(diǎn)均滿足堆性質(zhì){ intlarge;//large指向調(diào)整結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)中關(guān)鍵字較大者 RecTypetemp=R[low];//暫存調(diào)整結(jié)點(diǎn) for(large=2*low;large<=high;large*=2) {//R[low]是目前調(diào)整結(jié)點(diǎn)//若large>high,則表達(dá)R[low]是葉子，調(diào)整結(jié)束；否則先令large指向R[low]的左孩子 if(large<high&&R[large].key<R[large+1].key) large++;//若R[low]的右孩子存在且關(guān)鍵字不小于左兄弟，則令large指向//目前R[large]是調(diào)整結(jié)點(diǎn)R[low]的左右孩子結(jié)點(diǎn)中關(guān)鍵字較大者 if(temp.key>=R[large].key)//temp一直對應(yīng)R[low] break;//目前調(diào)整結(jié)點(diǎn)不不不小于其孩子結(jié)點(diǎn)的關(guān)鍵字，結(jié)束調(diào)整 R[low]=R[large];//相稱于互換了R[low]和R[large] low=large;//令low指向新的調(diào)整結(jié)點(diǎn)，相稱于temp已篩下到large的位置 } R[low]=temp;//將被調(diào)整結(jié)點(diǎn)放入最終位置上}//==========構(gòu)造大根堆==========voidBuildHeap(SeqListR)//將初始文獻(xiàn)R[1..n]構(gòu)造為堆{ inti; for(i=n/2;i>0;i--) Heapify(R,i,n);//將R[i..n]調(diào)整為大根堆}//==========堆排序===========voidHeapSort(SeqListR)//對R[1..n]進(jìn)行堆排序，不妨用R[0]做暫存單元{ inti; BuildHeap(R);//將R[1..n]構(gòu)造為初始大根堆 for(i=n;i>1;i--) {//對目前無序區(qū)R[1..i]進(jìn)行堆排序，共做n-1趟。 R[0]=R[1];R[1]=R[i];R[i]=R[0];//將堆頂和堆中最終一種記錄互換 Heapify(R,1,i-1);//將R[1..i-1]重新調(diào)整為堆，僅有R[1]也許違反堆性質(zhì)。 }}//6、二路歸并排序的基本思想：假設(shè)初始序列n個記錄，則可當(dāng)作是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到[n/2]個長度為2或1的有序子序列；再兩兩歸并，……，如此反復(fù)，直到一種長度為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)//若第一種子序列非空，則復(fù)制剩余記錄到R1 R1[p++]=R[i++]; while(j<=high)//若第二個子序列非空，則復(fù)制剩余記錄到R1中 R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p];//歸并完畢后將成果復(fù)制回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的兩個相鄰的子序列