計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---dijkstra算法和排序器

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程論文</b></p><p>　　設(shè)計(jì)題目：Dijkstra算法和排序器（排序算法驗(yàn)證及評(píng)價(jià)）</p><p>　　圖的Dijkstra算法</p><p><b>　　一、課題內(nèi)容和要求</b></p><p>　　Dijkstra算法的實(shí)現(xiàn)和演示。<

2、;/p><p><b>　　二、設(shè)計(jì)思路分析</b></p><p>　　Dijkstra算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào) (dj, pj)，其中dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長(zhǎng)度 (從頂點(diǎn)到其本身的最短路徑是零路(沒(méi)有弧的路)，其長(zhǎng)度等于零)；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過(guò)程如下：　　1) 初始化。起源

3、點(diǎn)設(shè)置為：① ds=0, ps為空;② 所有其他點(diǎn): di=∞, pi=?;③ 標(biāo)記起源點(diǎn)s，記k=s,其他所有點(diǎn)設(shè)為未標(biāo)記的?！　?) 檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：</p><p>　　dj=min［dj, dk+lkj］</p><p>　　式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。　　3) 選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj 中最小的一

4、個(gè)i：</p><p>　　di=min［dj, 所有未標(biāo)記的點(diǎn)j］</p><p>　　點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。　　4) 找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前一點(diǎn),設(shè)置：</p><p><b>　　i=j*</b></p><p>　　5) 標(biāo)記點(diǎn)i。如果所有點(diǎn)已

5、標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2) 再繼續(xù)。</p><p><b>　　三、概要設(shè)計(jì) </b></p><p>　　算法流程圖如下圖所示：</p><p>　　CGraph類的聲明部分如下所示：</p><p>　　#define maxPoint 100</p><p>　　cla

6、ss CGraph</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　CGraph(void);</p><p>　　~CGraph(void);</p><p>　　bool SetGraph( double g

7、[maxPoint][maxPoint] , int startPoint , int size );</p><p>　　bool Dijkstra();</p><p>　　void Display();</p><p>　　int GetStartPoint();</p><p>　　bool setStart(int start);&

8、lt;/p><p>　　void ChangeMatix(double (*p)[maxPoint]);</p><p>　　double GetBestWay( int dest , int path[] , int &pathLen );</p><p><b>　　private:</b></p><p>　　

9、bool solved;//標(biāo)志當(dāng)前圖是否已經(jīng)求解</p><p>　　double graph[maxPoint][maxPoint];//當(dāng)前圖布局</p><p>　　int size;//地圖大小</p><p>　　int startPoint;//起點(diǎn)</p><p>　　double dist[maxPoint];//當(dāng)前圖的解

10、</p><p>　　int prev[maxPoint];</p><p><b>　　};</b></p><p><b>　　四、詳細(xì)設(shè)計(jì)</b></p><p>　　// Dijkstra2.cpp : Defines the entry point for the console appl

11、ication.</p><p><b>　　//</b></p><p>　　#include "stdafx.h"</p><p>　　#include "Graph.h"</p><p>　　// Dijkstra.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。</p>

12、<p>　　void DisplayMessage()</p><p><b>　　{</b></p><p>　　printf( "☆☆☆☆☆☆最短路徑算法Dijkstra演示☆☆☆☆☆☆☆☆\n\n" );</p><p>　　printf("△1.連接矩陣顯示\n\n");</p

13、><p>　　printf("△2.修改連接矩陣\n\n");</p><p>　　printf("△3.求解最短路徑\n\n");</p><p>　　printf("△4.清空屏幕\n\n");</p><p>　　printf("△5.退出\n\n");<

14、/p><p>　　printf("請(qǐng)您輸入選項(xiàng)");</p><p><b>　　}</b></p><p>　　//求解最短路徑函數(shù)</p><p>　　void computerDijkstra(CGraph g,int dest,int size,int path[],int pathlen)<

15、;/p><p><b>　　{</b></p><p>　　printf( "----------------------------------------\n" );</p><p>　　double distanceLenth=0;</p><p>　　for( dest = 0 ; dest &l

16、t; size ; dest++ )</p><p><b>　　{</b></p><p>　　distanceLenth = g.GetBestWay( dest , path , pathlen );</p><p>　　printf( "從 %d 到 %d 的最短路徑長(zhǎng) %.f\n" , g.GetStartPoin

17、t() , dest , distanceLenth );</p><p>　　printf( "所經(jīng)結(jié)點(diǎn)為:\n" );</p><p>　　for( int i = 0 ; i < pathlen ; i++ )</p><p>　　printf( "%3d" , path[i] );</p><

18、p>　　printf( "\n----------------------------------------\n" );</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//主函數(shù)</b></p>&

19、lt;p>　　void main()</p><p><b>　　{</b></p><p>　　//連接矩陣可以修改</p><p>　　double graph[][maxPoint] =</p><p><b>　　{</b></p><p>　　{ 0 , 1

20、0 , -1 , 30 , 100 } ,</p><p>　　{ -1 , 0 , 50 , -1 , -1 } ,</p><p>　　{ -1 , -1 , 0 , -1 , 10 } ,</p><p>　　{ -1 , -1 , 20 , 0 , 60 } ,</p><p>　　{ -1 , -1 , -1 , -1 , 0 }&

21、lt;/p><p><b>　　};</b></p><p>　　int size = 5;</p><p>　　int start = 0;</p><p>　　int dest = 1;</p><p>　　int pathlen=0;</p><p>　　int path

22、[maxPoint];</p><p>　　double dist=0;</p><p><b>　　CGraph g;</b></p><p>　　double (*p)[maxPoint]=graph;</p><p>　　g.SetGraph(graph,start,size);</p><p&

23、gt;<b>　　while (1)</b></p><p><b>　　{</b></p><p>　　char InPutFlag;</p><p>　　DisplayMessage();</p><p>　　InPutFlag=getchar();</p><p>　　

24、switch (InPutFlag)</p><p><b>　　{</b></p><p><b>　　case '1':</b></p><p>　　g.Display();</p><p><b>　　break;</b></p><p

25、><b>　　case '2':</b></p><p>　　g.ChangeMatix(p);</p><p><b>　　break;</b></p><p><b>　　case '3':</b></p><p>　　computer

26、Dijkstra(g,dest,size,path,pathlen);</p><p><b>　　break;</b></p><p><b>　　case '4':</b></p><p>　　system("cls");</p><p><b>　

27、　break;</b></p><p><b>　　case '5':</b></p><p><b>　　exit(0);</b></p><p><b>　　break;</b></p><p><b>　　}</b><

28、;/p><p>　　cout<<"回車?yán)^續(xù)"<<endl;</p><p>　　getchar();</p><p>　　getchar();</p><p><b>　　}</b></p><p><b>　　}</b></p&

29、gt;<p>　　// Graph.cpp</p><p>　　#include "stdafx.h"</p><p>　　#include "Graph.h"</p><p><b>　　//構(gòu)造函數(shù)</b></p><p>　　CGraph::CGraph(voi

30、d)</p><p><b>　　{</b></p><p>　　for( int i = 0 ; i < maxPoint ; i++ )</p><p><b>　　{</b></p><p>　　for( int j = 0 ; j < maxPoint ; j++ )</p

31、><p>　　graph[i][j] = -1;</p><p><b>　　}</b></p><p>　　startPoint = -1;</p><p>　　size = -1;</p><p>　　solved = false; //當(dāng)前圖還沒(méi)有求解</p><p>&

32、lt;b>　　}</b></p><p>　　CGraph::~CGraph(void)</p><p><b>　　{</b></p><p><b>　　}</b></p><p><b>　　//設(shè)置起始位置</b></p><p&g

33、t;　　bool CGraph::setStart(int start)</p><p><b>　　{</b></p><p>　　startPoint = start;</p><p>　　return true;</p><p><b>　　}</b></p><p>

34、　　//設(shè)置求解矩陣和初始參數(shù)</p><p>　　bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )</p><p><b>　　{</b></p><p>　　for( int i = 0 ; i < size ; i++

35、)</p><p><b>　　{</b></p><p>　　for( int j = 0 ; j < size ; j++ )</p><p>　　graph[i][j] = g[i][j];</p><p><b>　　}</b></p><p>　　this-&

36、gt;startPoint = startPoint;</p><p>　　this->size = size;</p><p>　　solved = false;</p><p>　　Dijkstra();</p><p>　　return true;</p><p><b>　　}</b>

37、;</p><p><b>　　//求解最短路徑</b></p><p>　　bool CGraph::Dijkstra()</p><p><b>　　{</b></p><p>　　bool s[maxPoint];</p><p>　　for( int j = 0 ;

38、j < size ; j++ )</p><p><b>　　{</b></p><p>　　dist[j] = graph[startPoint][j];</p><p>　　s[j] = false;</p><p>　　if( dist[j] < 0 ) //dist[i]<0，表示沒(méi)有路徑連接

39、結(jié)點(diǎn)startPoint 與 結(jié)點(diǎn)j</p><p>　　prev[j] = 0;</p><p><b>　　else</b></p><p>　　prev[j] = startPoint;</p><p><b>　　}</b></p><p><b>　　//

40、從起點(diǎn)出發(fā)</b></p><p>　　dist[startPoint] = 0;</p><p>　　s[startPoint] = true;</p><p>　　for( int i = 0 ; i < size ; i++ )</p><p><b>　　{</b></p><

41、;p>　　double temp;</p><p>　　int u = startPoint;</p><p>　　bool flag = false;</p><p>　　for( int j = 0 ; j < size ; j++ )</p><p><b>　　{</b></p><

42、;p>　　if( !s[j] )</p><p><b>　　{</b></p><p>　　//如果不是第一次比較，temp、u，都已經(jīng)賦值，則</p><p>　　if( flag )</p><p><b>　　{</b></p><p>　　if( dist[j

43、] > 0 && dist[j] < temp )</p><p><b>　　{</b></p><p><b>　　u = j;</b></p><p>　　temp = dist[j];</p><p><b>　　}</b></p>

44、;<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　u = j;</b></p><p>　　temp = dist[j];</p>

45、<p>　　flag = true;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　s[u] = true;</p><p>　　for( j =

46、0 ; j < size ; j++ )</p><p><b>　　{</b></p><p>　　if( !s[j] && graph[u][j] > 0 )</p><p><b>　　{</b></p><p>　　double newDist = dist[u]

47、 + graph[u][j];</p><p>　　if( dist[j] < 0 || newDist < dist[j] )</p><p><b>　　{</b></p><p>　　dist[j] = newDist;</p><p>　　prev[j] = u;</p><p&g

48、t;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　solved = true;</p><p>　　return

49、true;</p><p><b>　　}</b></p><p>　　//顯示連接矩陣數(shù)據(jù)</p><p>　　void CGraph::Display()</p><p><b>　　{</b></p><p>　　printf( " 當(dāng)前地圖的鄰接矩

50、陣\n" );</p><p>　　for( int i = 0 ; i < size ; i++ )</p><p><b>　　{</b></p><p>　　for( int j = 0 ; j < size ; j++ )</p><p><b>　　{</b><

51、/p><p>　　printf( "%5.f" , graph[i][j] );</p><p><b>　　}</b></p><p>　　printf( "\n" );</p><p><b>　　}</b></p><p><b

52、>　　}</b></p><p>　　//修改連接矩陣數(shù)據(jù)</p><p>　　void CGraph::ChangeMatix(double (*p)[maxPoint])</p><p><b>　　{</b></p><p>　　printf( "修改連接矩陣的參數(shù)，一次只能修改一個(gè)^^

53、\n" );</p><p>　　printf( "輸入格式如下：先輸入橫坐標(biāo) 然后輸入縱坐標(biāo) 最后輸入數(shù)值\n" );</p><p>　　int Xpoint=0,Ypoint=0,Pvalue=0;</p><p>　　cout<<"請(qǐng)輸入橫坐標(biāo)(從0開(kāi)始)"<<endl;</p&

54、gt;<p>　　cin>>Xpoint;</p><p>　　cout<<"請(qǐng)輸入縱坐標(biāo)(從0開(kāi)始)"<<endl;</p><p>　　cin>>Ypoint;</p><p>　　cout<<"請(qǐng)輸入要修改的值"<<endl;</

55、p><p>　　cin>>Pvalue;</p><p>　　p[Xpoint][Ypoint]=Pvalue;</p><p>　　graph[Xpoint][Ypoint]=Pvalue;</p><p><b>　　}</b></p><p><b>　　//得到最短路徑&

56、lt;/b></p><p>　　double CGraph::GetBestWay( int dest , int path[] , int &pathLen)</p><p><b>　　{</b></p><p>　　int p = dest;</p><p>　　int theway[maxPoin

57、t];</p><p>　　int len = 0;</p><p>　　while( p != startPoint )</p><p><b>　　{</b></p><p>　　theway[len] = p;</p><p>　　p = prev[p];</p><p&

58、gt;<b>　　len++;</b></p><p><b>　　}</b></p><p>　　theway[len] = startPoint;</p><p><b>　　len++;</b></p><p>　　for( int i = 0 , j = len - 1

59、 ; i < len ; i++ , j-- )</p><p>　　path[i] = theway[j];</p><p>　　pathLen = len;</p><p>　　return dist[dest];</p><p><b>　　}</b></p><p><b>

60、;　　//</b></p><p><b>　　//得到開(kāi)始的點(diǎn)</b></p><p>　　int CGraph::GetStartPoint()</p><p><b>　　{</b></p><p>　　return startPoint;</p><p>

61、<b>　　}</b></p><p><b>　　//</b></p><p>　　五、測(cè)試數(shù)據(jù)及其結(jié)果分析</p><p>　　測(cè)試數(shù)據(jù)如下圖所示，是一個(gè)連接矩陣。</p><p>　　0 10 -1 30 100</p><p>　　-1

62、 0 50 -1 -1 </p><p>　　-1 -1 0 -1 10</p><p>　　-1 -1 20 0 60</p><p>　　-1 -1 -1 -1 0</p><p><b>　　測(cè)試結(jié)果如所示：<

63、;/b></p><p>　　0到0 的最短路徑為0 </p><p><b>　　所經(jīng)過(guò)節(jié)點(diǎn)為0</b></p><p>　　0到1 的最短路徑為10 </p><p>　　所經(jīng)過(guò)節(jié)點(diǎn)為0 1</p><p>　　0到2 的最短路徑為50 </p><p>　　所

64、經(jīng)過(guò)節(jié)點(diǎn)為0 3 2</p><p>　　0到3 的最短路徑為30 </p><p>　　所經(jīng)過(guò)節(jié)點(diǎn)為0 3</p><p>　　0到4 的最短路徑為60 </p><p>　　所經(jīng)過(guò)節(jié)點(diǎn)為0 3 2 4</p><p>　　排序器（排序算法驗(yàn)證及評(píng)價(jià)）</p><p>　

65、　一、題目與要求：?jiǎn)栴}描述：排序器（排序算法驗(yàn)證及評(píng)價(jià)）要    求：實(shí)現(xiàn)以下六種排序算法，將給定的不同規(guī)模大小的數(shù)據(jù)文件（data01.txt，data02.txt，data03.txt，data04.txt）進(jìn)行排序，并將排序結(jié)果分別存儲(chǔ)到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。1）、Shell排序；  &#

66、160; 2）、Quick排序3）、錦標(biāo)賽排序；   4）、堆排序5）、歸并排序；    6）、基數(shù)排序在實(shí)現(xiàn)排序算法1）~4）時(shí)，統(tǒng)計(jì)數(shù)據(jù)元素比較的次數(shù)和交換的次數(shù)，進(jìn)而對(duì)這四種算法在特定數(shù)據(jù)條件下的效率進(jìn)行分析和評(píng)判。二、題目分析：首先需要讀取4個(gè)不同大小文件中的數(shù)據(jù)，然后對(duì)其進(jìn)行六種不同方法的排序，最后將結(jié)果儲(chǔ)存在不同的文件中。其次，需要定義

67、兩個(gè)變量分別來(lái)記錄前四種排序中數(shù)據(jù)的比較次數(shù)和移動(dòng)次數(shù)，從而對(duì)這四種算法在特定數(shù)據(jù)條件下的效率進(jìn)行分析和評(píng)判。三、函數(shù)說(shuō)明及概要設(shè)計(jì)：以下為本程序中所涉及到的所有函數(shù)或重要變量，在設(shè)計(jì)思想中有具體解釋：/*全局變量*/int comp;//用來(lái)記錄數(shù)據(jù)間</p><p>　　/*主函數(shù)*/int main()</p><p>　　/*菜單選擇函數(shù)*/int

68、menu()</p><p>　　/*從文件中讀取待排序數(shù)據(jù)*/int ReadInfo(LinkList *p,char *f)</p><p>　　/*在屏幕上輸出每次排序的數(shù)據(jù)數(shù)目,比較次數(shù),移動(dòng)次數(shù)*/int PrintInfo(SqList *p)/*排序結(jié)果寫入文件中*/int WriteInfo(SqList *p,char *f)</p&g

69、t;<p>　　/*希爾排序*/int Shell_Sort(SqList *p)</p><p>　　/*希爾排序中的插入函數(shù)*/int Shell_Insert(SqList *p,int dk)</p><p>　　/*快速排序*/int Quick_Sort(SqList *p)</p><p>　　/*遞歸形式的快速排序函數(shù)*/int

70、 QSort(SqList *p,int low,int high)</p><p>　　/*快排中計(jì)算樞軸位置的函數(shù)*/int Partition(SqList *p,int low,int high)</p><p>　　/*錦標(biāo)賽排序*/int Tournament_Sort(SqList *p)</p><p>　　/*錦標(biāo)賽排序中的調(diào)整函數(shù)*/int

71、 UpdateTree(DataNode *tree,int i)</p><p>　　/*堆排序*/int Heap_Sort(SqList *H)</p><p>　　/*堆排序中的篩選函數(shù)*/void HeapAdjust(SqList *H,int s,int m)</p><p>　　/*歸并排序*/int Merg_Sort(SqList *p)&

72、lt;/p><p>　　/*遞歸形式的歸并排序函數(shù)*/int MSort(RedType SR[],RedType TR1[],int s,int t)</p><p>　　/*歸并排序中將一維數(shù)組中前后相鄰的兩個(gè)有序序列歸并為一個(gè)有序序列*/int Merge(RedType SR[],RedType TR[],int i,int m,int n)</p><p>

73、;　　/*基數(shù)排序*/int Radix_Sort(SqList *p,char *f1)</p><p>　　/*鏈?zhǔn)交鶖?shù)排序中一趟收集函數(shù)*/int Collect(SLCell *r,int i,ArrType f,ArrType e)/*鏈?zhǔn)交鶖?shù)排序中一趟分配函數(shù)*/int Distribute(SLCell *r,int i,ArrType f,ArrType e)本程序采用的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有三

74、種:/*鏈?zhǔn)交鶖?shù)排序的數(shù)據(jù)結(jié)構(gòu)*/typedef struct{ int keys[MAX_NUM_OF_KEY]; int info; int keysnum; int next;}SLCell;typedef struct{ SLCell *r; int keynum; int recnum;

75、}SLList;typedef int ArrType[RADIX];</p><p>　　/*勝者樹(shù)數(shù)據(jù)結(jié)點(diǎn)類的定義*/ //歸并排序typedef struct{ RedType data; int key;//關(guān)鍵字項(xiàng) int index;//滿二叉樹(shù)中的順序號(hào) int active;//1,參選 0,不參選}DataNode;&l

76、t;/p><p>　　/*其余排序的數(shù)據(jù)結(jié)構(gòu)*/typedef struct { int key;//關(guān)鍵字項(xiàng) int info;//其他數(shù)據(jù)項(xiàng)}RedType;//記錄類型typedef struct { RedType *r;//[MAXSIZE+1] int length;//順序表長(zhǎng)度

77、}SqList,*LinkList;</p><p>　　1. 首先建立起改程序的框架:需要一個(gè)主函數(shù): int main( )，在主函數(shù)中調(diào)用菜單函數(shù)int menu()即可。</p><p>　　2．在菜單函數(shù)中，使屏幕上輸出以下語(yǔ)句，以便進(jìn)行選擇。1.Shell排序2.Quick排序3.錦標(biāo)賽排序4.堆排序5.歸并排序6.基數(shù)排序7.退出并根據(jù)選擇的結(jié)果來(lái)

78、確定要調(diào)用的排序函數(shù)，這里特別要指出的是，由于基數(shù)排序與其他排序的參數(shù)調(diào)用型式略有不同，所以本函數(shù)中定義了兩個(gè)函數(shù)指針int (*f)(SqList *),(*f1)(SqList *,char *)，分別用來(lái)指向基數(shù)排序函數(shù)和其他排序函數(shù)。確定了要進(jìn)行的排序，接下來(lái)，在for(i=0;i<4;i++)這個(gè)循環(huán)中，每循環(huán)一次讀一個(gè)文件，排序后存儲(chǔ)并釋放內(nèi)存空間，沒(méi)選擇一次排序的方法，則4個(gè)文件中的數(shù)據(jù)均可按照該方法排序

79、完成，直至選擇“7.退出”為止。</p><p>　　3．希爾排序:它的基本思想是：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排 序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。     在希爾排序中，子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。如在第一趟排序時(shí)的增量為7，即將相隔為7的元素編成一組進(jìn)行直接插

80、入排序。第二趟排序時(shí)的增量為3，增量進(jìn)一步縮小。由于在這兩趟的插入排序中在子序列中逆序的關(guān)鍵字是跳躍式地移動(dòng)，從而使得在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序，只要作少量比較和移動(dòng)即可完成排序，因此希爾排序的時(shí)間復(fù)雜度較直接插入排序低。在該排序中，定義一個(gè)整型數(shù)組用來(lái)存儲(chǔ)增量increment[]，并且選取increment[i]=(k-1)/2。</p><p>　　4．快速排序:快速排序是對(duì)冒泡

81、排序的一種改進(jìn)。它的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一躺快速排序。一躺快速排序的算法是：

82、  1）、設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候I：=1，J：=N；  2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；  3）、從J開(kāi)始向前搜索，即由后開(kāi)始向前搜索（J：=J-1），找到第一個(gè)小于X的值，兩者交換；  4）、從I開(kāi)始向后搜索，即由前開(kāi)始向后搜索（I：=I+1），找到第一個(gè)大于X的值，兩者交換；  5）、重復(fù)第3、4步，直到I=J；  例如

83、：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49） A[1]    A[2]    A[3]    A[4]    A[5]     A[6]</p><p>　　5．錦標(biāo)賽排序:與體育淘汰賽類似，首先取得n個(gè)元素的關(guān)鍵字，進(jìn)行兩兩比較，得到

84、60; n/2  個(gè)比較的優(yōu)勝者，將其作為第一次比較的結(jié)果保留下來(lái)，然后對(duì)這些元素再進(jìn)行關(guān)鍵值的兩兩比較，…，如此重復(fù)，直到選出一個(gè)關(guān)鍵字最大的對(duì)象為止。每次兩兩比較的結(jié)果是把排序碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn),稱這種樹(shù)稱為勝者樹(shù).位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn).非葉結(jié)點(diǎn)稱為勝者樹(shù)的內(nèi)結(jié)點(diǎn).每個(gè)結(jié)點(diǎn)除了存放對(duì)象的排序碼data外,還存放了該對(duì)象是否要參選的標(biāo)志active和該對(duì)象在滿二叉樹(shù)中的序號(hào)index.勝者樹(shù)數(shù)

85、據(jù)結(jié)點(diǎn)類的定義typedef struct{ RedType data; int key;//關(guān)鍵字項(xiàng) int index;//滿二叉樹(shù)中的順序號(hào) int active;//1,參選 0,不參選}DataNode;</p><p>　　6．堆排序堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)

86、關(guān)鍵字的記錄變得簡(jiǎn)單。 (1)用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū) ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無(wú)序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無(wú)序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最

87、大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無(wú)序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。 …… 直到無(wú)序區(qū)只有一個(gè)元素為止。</p><p>　　7．歸并排序本程序中采用遞歸的歸并排序算法。在遞歸的歸并排序方法中，首先要把整個(gè)待排序序列劃分為兩個(gè)長(zhǎng)度大致相等的部分，分別

88、稱之為左子表和右子表。對(duì)這些子表分別遞歸地進(jìn)行排序，然后再把排好序的兩個(gè)子表進(jìn)行歸并。待排序?qū)ο笮蛄械年P(guān)鍵碼為 { 21, 25, 49, 25*,16, 08 }，先是進(jìn)行子表劃分，待到子表中只有一個(gè)對(duì)象時(shí)遞歸到底。再是實(shí)施歸并，逐步退出遞歸調(diào)用的過(guò)程。 </p><p>　　8．基數(shù)排序基數(shù)排序是采用“分配”與“收集”的辦法，用對(duì)多關(guān)鍵碼進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單關(guān)鍵碼進(jìn)行排序的方法。基數(shù)排序的

89、具體方法如下:1、根據(jù)數(shù)據(jù)項(xiàng)個(gè)位上的值，把所有的數(shù)據(jù)項(xiàng)分為10組；2、然后對(duì)這10組數(shù)據(jù)重新排列：把所有以0結(jié)尾的數(shù)據(jù)排在最前面，然后是結(jié)尾是1的數(shù)據(jù)項(xiàng)，照此順序直到以9結(jié)尾的數(shù)據(jù)，這個(gè)步驟稱為第一趟子排序。3、在第二趟子排序中，再次把所有的數(shù)據(jù)項(xiàng)分為10組，但是這一次是根據(jù)數(shù)據(jù)項(xiàng)十位上的值來(lái)分組的。這次分組不能改變先前的排序順序。也就是說(shuō)，第二趟排序之后，從每一組數(shù)據(jù)項(xiàng)的內(nèi)部來(lái)看，數(shù)據(jù)項(xiàng)的順序保持不變；4、然后再把10組數(shù)據(jù)項(xiàng)

90、重新合并，排在最前面的是十位上為0的數(shù)據(jù)項(xiàng)，然后是10位為1的數(shù)據(jù)項(xiàng)，如此排序直到十位上為9的數(shù)據(jù)項(xiàng)。5、對(duì)剩余位重復(fù)這個(gè)過(guò)程，如果某些數(shù)據(jù)項(xiàng)的位數(shù)少于其他數(shù)據(jù)項(xiàng)，那么認(rèn)為它們的高位為0。</p><p>　　五、六種排序算法的效率分析和評(píng)判1.Shell排序</p><p>　　2. Quick排序</p><p><b>　　3.

91、0;錦標(biāo)賽排序</b></p><p><b>　　4. 堆排序</b></p><p>　　從對(duì)前四種排序中的數(shù)據(jù)比較次數(shù)和移動(dòng)次數(shù)來(lái)看，快速排序最佳，其所需時(shí)間最省，但快速排序在比較壞的情況下的時(shí)間性能不如錦標(biāo)賽排序和堆排序。當(dāng)序列中的記錄“基本有序”或數(shù)據(jù)數(shù)目較小時(shí)，Shell排序是最佳的排序方法。 由文件中的排序結(jié)果可知，希

92、爾排序、快速排序和堆排序都是不穩(wěn)定的排序方法。</p><p><b>　　總結(jié)</b></p><p>　　在本程序的調(diào)試過(guò)程中，最大的體會(huì)就是對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度逐步的認(rèn)識(shí)。一開(kāi)始調(diào)試較小的文件時(shí)，還并未涉及到這兩個(gè)問(wèn)題，所以只考慮到了算法的正確性，而難免忽略了程序中對(duì)時(shí)間、空間復(fù)雜度的要求。舉個(gè)例子，在調(diào)試第四個(gè)大小為32.3M的文件時(shí)，經(jīng)常因?yàn)槌绦蛑幸粋€(gè)極

93、小的錯(cuò)誤而導(dǎo)致程序無(wú)限運(yùn)行直至系統(tǒng)提示虛擬內(nèi)存不足。在剛開(kāi)始的編寫中，由于并沒(méi)有釋放內(nèi)存空間，而導(dǎo)致經(jīng)常需要重啟電腦來(lái)達(dá)到清理內(nèi)存保證程序運(yùn)行速度的目的。 第五種排序方法，歸并，由于使用的是課本上所講的遞歸方法，而其中每遞歸一次都要申請(qǐng)一次內(nèi)存空間，至今該排序?qū)?2.3M的文件仍然無(wú)法成功排序，可見(jiàn)空間復(fù)雜度的重要性，看來(lái)在一個(gè)程序中，算法的正確與否僅僅是程序好壞的一部分，而評(píng)估一個(gè)算法好壞的主要因素則是它的時(shí)間、空間復(fù)雜度