數據結構課程設計報告---幾種排序算法的演示

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：26 大?。?94.50KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩25頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程設計報告　　—幾種排序算法的演示　　時間：2010-1-14　　一需求分析　　運行環(huán)境　　Microsoft Visu

2、al Studio 2005　　程序所實現的功能　　對直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序算法的演示，并且輸出每一趟的排序情況。　　程序的輸入（包含輸入的數據格式和說明）　　<1>

3、排序種類三輸入　　<2>排序數的個數的輸入　　<3>所需排序的所有數的輸入 　　程序的輸出（程序輸出的形式）　　<1>主菜單的輸出　　<2>每一

4、趟排序的輸出，即排序過程的輸出　　二設計說明　　算法設計思想　　<1>交換排序（冒泡排序、快速排序）　　交換排序的基本思想是：對排序表中的數據元素按關鍵字進行兩兩比較，如果發(fā)生逆序（

5、即排列順序與排序后的次序正好相反），則兩者交換位置，直到所有數據元素都排好序為止。　　<2>插入排序（直接插入排序、折半插入排序）　　插入排序的基本思想是：每一次設法把一個數據元素插入到已經排序的部分序列的合適位置，使得插入后的序列仍然是有序的。開始時建立一個初始的有序序列，它只包含一個數據元素。然后，從這個初始序列出發(fā)不斷插入數據元素，直到

6、最后一個數據元素插到有序序列后，整個排序工作就完成了。　　<3>選擇排序（簡單選擇排序、堆排序）　　選擇排序的基本思想是：第一趟在有n個數據元素的排序表中選出關鍵字最小的數據元素，然后在剩下的n-1個數據元素中再選出關鍵字最小（整個數據表中次?。┑臄祿兀来沃貜?，每一趟（例如第i趟，i=1，…，n-1）總是在當前剩下的n-i+1個待排序數

7、據元素中選出關鍵字最小的數據元素，作為有序數據元素序列的第i個數據元素。等到第n-1趟選擇結束，待排序數據元素僅剩下一個時就不用再選了，按選出的先后次序所得到的數據元素序列即為有序序列，排序即告完成。　　<4>歸并排序（兩路歸并排序）　　兩路歸并排序的基本思想是：假設初始排序表有n個數據元素，首先把它看成是長度為1的首尾相接的n個有序子表（以

8、后稱它們?yōu)闅w并項），先做兩兩歸并，得n/2上取整個長度為2的歸并項（如果n為奇數，則最后一個歸并項的長度為1）；再做兩兩歸并，……，如此重復，最后得到一個長度為n的有序序列。　　程序的主要流程圖　　程序的主要模塊(要求對主要流程圖中出現的模塊進行說明)　　程序的主要模塊主要分

9、為主菜單模塊和排序算法演示模塊。　　<1>主菜單　　主要功能：程序運行時，可使運行者根據提醒輸入相關操作，從而進入不同的排序方法或者退出。　　<2>排序方法及輸出　　根據運行者對排序的不同選擇，進入排序過程&l

10、t;/p>　　a.直接插入排序：根據直接排序的算法，輸出排序過程　　b.折半插入排序：根據折半插入的算法，輸出排序過程　　c.冒泡排序：根據冒泡排序算法，輸出排序過程　　d.簡單選擇排序：根據簡單選擇排序的算法，輸出排序過程　　e.快速排序：根

11、據快速排序的算法，輸出排序過程　　f.堆排序：根據堆排序的算法，輸出排序過程　　g.歸并排序：根據歸并排序的算法，輸出排序過程　　程序的主要函數及其偽代碼說明　　<1>模板類　　主

12、要說明程序中用到的類的定義　　template<class type>class sortlist　　{　　private:　　int currentsize;//數據表中數據元素的個

13、數　　public:　　type *arr;//存儲數據元素的向量（排序表）　　sortlist():currentsize(0){arr=new type[maxsize];}//構造函數　　sortlist(int n){arr=

14、new type[maxsize];currentsize=n;}　　void insert(int i,type x){arr[i]=x;}　　~sortlist(){delete []arr;}//析構函數　　void swap(type &x,type &y)//數據元素x和y交換位置<

15、;/p>　　{type temp=x;x=y;y=temp;}　　void bubblesort();//冒泡排序　　void quicksort(int low,int high);//快速排序　　void insertionsort();//直接插入排序&l

16、t;p>　　void binaryinsertsort();//折半插入排序　　void selectsort();//簡單選擇排序　　void heapsort();//堆排序　　void mergesort(sortlist<type> &table);//歸并排序

17、;　　void filterdown(const int start);//建立最大堆　　void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);//一趟歸并　　void merge

18、(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);//兩路歸并算法　　};　　<2>直接插入排序

19、　　直接插入排序的基本思想：開始時把第一個數據元素作為初始的有序序列，然后從第二個數據元素開始依次把數據元素按關鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1<i<=n)個數據元素時，前面的i-1個數據元素已經排好序，這時，用第i個數據元素的關鍵字與前面的i-1個數據元素的關鍵字順序進行比較，找到插入位置后就將第i個數據元素插入。如此進行n-1次插入，

20、就完成了排序。　　以下是在順序表上實現的直接插入排序　　在順序表上進行直接插入排序時，當插入第i(1<i<=n)個數據元素時，前面的arr[0]、arr[1]、…、arr[i-2]已經排好序，這時，用arr[i-1]的關鍵字依次與arr[i-2],arr[i-3],…的關鍵字順序進行比較，如果這些數據元素的關鍵字大于arr[i-1]的關鍵字，

21、則將數據元素向后移一個位置，當找到插入位置后就將arr[i-1]插入，就完成了arr[0],arr[1],…,arr[n-1]的排序。　　偽代碼如下　　template <class type>//直接插入排序　　void sortlist<type>

22、::insertionsort()　　{　　type temp;　　int j;　　for(int i=1;i<=currentsize-1;i++)

23、;　　{　　temp=arr[i];j=i-1;　　while(j>=0&&temp<arr[j])　　{arr[j+1]=arr[j];j--;}　　arr[j+1]=temp;&

24、lt;p>　　cout<<"第"<<++num<<"趟排序結果為:";　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";　　c

25、out<<endl;　　}　　num=0;　　}　　<3>折半插入排序&

26、lt;p>　　折半插入排序的基本思想：設在排序表中有n個數據元素arr[0],arr[1],…,arr[n-1]。其中，arr[0],arr[1],…,arr[n-1]是已經排好序的部分數據元素序列，在插入arr[i]時，利用折半查找方法尋找arr[i]的插入位置。折半插入排序方法只能在順序表存儲結構實現。　　偽代碼如下：<

27、;p>　　template <class type>//折半插入排序　　void sortlist<type>::binaryinsertsort()　　{　　type temp;　　int left,r

28、ight;　　for(int i=1;i<currentsize;i++)　　{ 　　left=0;right=i-1;temp=arr[i];　　while(left<=right)//找插入位置

29、　　{　　int mid=(left+right)/2;　　if(temp<arr[mid])right=mid-1;　　else left=mid+1;　　}</p

30、>　　for(int k=i-1;k>=left;k--)//向后移動　　arr[k+1]=arr[k];　　arr[left]=temp;　　cout<<"第"<<++num<<"趟排序結果為:";&l

31、t;/p>　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";　　cout<<endl;　　}<p&g

32、t;　　num=0;　　}　　<4>冒泡排序　　冒泡排序的基本思想是：設排序表中有n個數據元素。首先對排序表中第一，二個數據元素的關鍵字arr[0]和arr[1]進行比較。如果前者大于后者

33、，則進行交換；然后對第二，三個數據做同樣的處理；重復此過程直到處理完最后兩個相鄰的數據元素。我們稱之為一趟冒泡，它將關鍵字最大的元素移到排序表的最后一個位置，其他數據元素一般也都向排序的最終位置移動。然后進行第二趟排序，對排序表中前n-1個元素進行與上述同樣的操作，其結果使整個排序表中關鍵字次大的數據元素被移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有數據元素排好序。<b&g

34、t;　　偽代碼如下：　　template <class type>//冒泡排序　　void sortlist<type>:: bubblesort()　　{　　int i=

35、1;　　int finish=0;//0表示還沒有排好序　　while(i<currentsize &&!finish)　　{　　finish=1;//排序結束標志置為,假定已經排好序<

36、/p>　　for(int j=0;j<currentsize-i;j++)　　if(arr[j]>arr[j+1])//逆序　　{　　swap(arr[j],arr[j+1]);//相鄰元素交換位置<p&g

37、t;　　finish=0;　　}//排序結束標志置為,表示本趟發(fā)生了交換，說明還沒有排好序　　i++;　　cout<<"第"<<++num<<"趟排序結果為:";

38、　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";　　cout<<endl;　　}<p

39、>　　num=0;　　}　　<5>簡單選擇排序（直接選擇排序）　　直接選擇排序的算法基本思想是：　　a)開始時設i的初始值為0。　　b)

40、如果i<n-1，在數據元素序列arr[i]arr[n-1]中，選出具有最小關鍵字的數據元素arr[k]；否則算法結束。　　c)若arr[k]不是這組數據元素中的第一個數據元素（i≠k），則將arr[k]與arr[i]這兩數據元素的位置對調；　　d)令i=i+1轉步驟 b)。　　偽代碼如下：

41、　　template <class type>　　void sortlist<type>::selectsort()//簡單選擇排序　　{　　int k;

42、;　　for(int i=0;i<=currentsize-1;i++)　　{　　k=i;　　for(int j=i+1;j<currentsize;j++)&

43、lt;p>　　if(arr[j]<arr[k])　　k=j;//k 指示當前序列中最小者的位置　　if(k!=i)//最小關鍵字的數據元素位置不等于i　　swap(arr[i],arr[k]);　　cout<<"第"<&l

44、t;++num<<"趟排序結果為:";　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";　　cout<<endl;<

45、b>　　}　　num=0;　　}　　<6>快速排序　　快速排序（Quick Sort）又被稱做分區(qū)交換排序，這是一種平均

46、性能非常好的排序方法。　　其算法基本思想是：任取排序表中的某個數據元素(例如取第一個數據元素)作為基準，按照該數據元素的關鍵字大小，將整個排序表劃分為左右兩個子表：左側子表中所有數據元素的關鍵字都小于基準數據元素的關鍵字。右側子表中所有數據元素的關鍵字都大于或等于基準數據元素的關鍵字，基準數據元素則排在這兩個子表中間(這也是該數據元素最終應安放的位置)，然后分別對這兩個子表重復施行上述方法的快

47、速排序，直到所有的子表長度為1，則排序結束。　　偽代碼如下：　　template <class type>//快速排序　　void sortlist<type>::quicksort(int low,int high)//在待排序區(qū)間[low,high

48、]上，遞歸地進行快速排序　　{　　int i=low,j=high;　　type temp=arr[low];//取區(qū)間第一個位置為基準位置　　if(i<j)<

49、p>　　{　　while(i<j)　　{　　while(i<j&&temp<arr[j])j--;　　if(i<j){swap(arr[i],arr[

50、j]);i++;}　　while(i<j&&temp>=arr[i])i++;　　if(i<j){swap(arr[i],arr[j]);j--;}　　}　　arr[i]=temp;//將基準元素就

51、位　　cout<<"第"<<++x<<"趟排序結果為:";　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";

52、　　cout<<endl;　　quicksort(low,i-1);//在左子區(qū)間遞歸進行快速排序　　quicksort(i+1,high);//在右子區(qū)間遞歸進行快速排序　　}　　}&

53、lt;/b>　　<7>堆排序（包括建立最大堆和堆排序兩個過程）　　堆排序算法的基本思想是：　　a.對排序表中的數據元素，利用堆的調整算法形成初始堆。　　b.輸出堆頂元素。

54、c.對剩余元素重新調整形成堆。　　d.重復執(zhí)行第b、c步，直到所有數據元素被輸出。　　(1)建立最大堆的偽代碼如下：　　template <class type>//建立最大堆　　void sortlist<type>::filterdown(co

55、nst int start)　　{//向下調整使從start開始到currentsize-1為止的子表成為最大堆　　int i=start,j=2*i+1;//j為i的左孩子　　int tablesize=currentsize;　　type temp=arr[i];&l

56、t;/p>　　while(j<=currentsize-1)　　{　　if(j<currentsize-1 && arr[j]<arr[j+1])　　j++;//在兩個孩子中選關鍵字較大者&

57、lt;p>　　if(temp>=arr[j])break;　　else{arr[i]=arr[j];i=j;j=2*j+1;　　}　　}　　arr[i]=temp;

58、　　}　　(2)堆排序　　如果建立的堆滿足最大堆的條件，則堆的第一個數據元素arr[0]具有最大的關鍵字，將arr[0]與arr[n-1]對調，把具有最大關鍵字的數據元素交換到最后，再對前面的n-1個數據元素使用堆的調整算法，重新建立最大堆，結果把具有次最大

59、關鍵字的數據元素又上浮到堆頂，即arr[0]的位置，再對調arr[0]和arr[n-2]，…，如此反復執(zhí)行n-1次，最后得到全部排序好的數據元素序列。　　偽代碼如下：　　template <class type>//堆排序　　void sortlist<ty

60、pe>::heapsort()　　{　　int tablesize=currentsize;　　for(int i=(currentsize-2)/2;i>=0;i--)　　filterdown(i); //

61、初始建堆　　for(int i=currentsize-1;i>=1;i--)　　{　　swap(arr[0],arr[i]);//堆頂元素和最后一個元素交換　　currentsize--;<p&g

62、t;　　filterdown(0);//重建最大堆　　cout<<"第"<<++num<<"趟排序結果為:";　　for(int t=0;t<tablesize;t++)　　cout<<arr[t]<<&qu

63、ot; ";　　cout<<endl;　　}　　num=0;　　currentsize=tablesize;

64、}　　<8>歸并排序（包括歸并算法，一趟歸并算法和歸并排序）　　歸并算法　　其基本思想是：設有兩個有序表A和B，其數據元素個數（表長）分別為n和m，變量i和j分別是表A和表B的當前檢測指針；設表C是歸并后的新有序表，變量k是它的當前存放指針。開

65、始時i、j、k都分別指向A、B、C三個表的起始位置；然后根據A[i]與B[j]的關鍵字的大小，把關鍵字小的數據元素放到新表C[k]中；且相應的檢測指針（i或j）和存放指針k增加1.如此循環(huán)，當i與j中有一個已經超出表長時，將另一個表中的剩余部分照抄到新表C[k]~C[m+n]中。　　下面的歸并算法中，兩個待歸并的有序表首尾相接存放在數組sourcetable.arr[]中，其中第一個表的下標范圍

66、從left到mid，另一個表的下標范圍從mid+1到right。前一個表中有mid-left+1個數據元素，后一個表中有right –mid個數據元素。歸并后得到的新有序表有right –mid個數據元素。歸并后得到的新有序表存放在另一個輔助數組mergedtable.arr[]中，其下標范圍從left到right。　　偽代碼如下：&

67、lt;p>　　template <class type>　　void sortlist<type>::merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right)</p&g

68、t;　　{　　int i=left,j=mid+1,k=left;//指針初始化　　//i是前一段的當前元素位置，j是后一段的當前元素位置，k是輔助數組的當前位置　　while(i<=mid&&j<=right)</p&

69、gt;　　if(sourcetable.arr[i]<=sourcetable.arr[j])　　{mergedtable.arr[k]=sourcetable.arr[i];i++;k++;}　　else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;}&

70、lt;p>　　if(i<=mid)　　for(int p=k,q=i;q<=mid;p++,q++)　　mergedtable.arr[p]=sourcetable.arr[q];//把前一段復制到mergedtable　　else&

71、lt;p>　　for(int p=k,q=j;q<=right;p++,q++)　　mergedtable.arr[p]=sourcetable.arr[q];//把后一段復制到mergedtable　　}　　一趟歸并算法&l

72、t;/p>　　設數組sourcetable.arr[0]到sourcetable.arr[n-1]中的n個數據元素已經分為一些長度為len的歸并項，將這些歸并項兩兩歸并，歸并成一些長度為2len的歸并項，結果放到mergedtable.arr[]中。如果n不是2len的整數倍，則一趟歸并到最后，可能遇到兩種情況：　　剩下一個長度為len的歸并項和一個長度不足len的歸

73、并項，可用一次merge算法，將它們歸并成一個長度小于2len的歸并項。　　只剩下一個歸并項，其長度小于或等于len，可將它直接復制到數組mergedtable.arr[]中。　　偽代碼如下：　　template <class type>&

74、lt;p>　　template <class type>　　void sortlist<type>::mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len)　　{&l

75、t;/b>　　int i=0;　　while(i+2*len<=currentsize-1)//表示至少有個子序列　　{　　merge(sourcetable,mergedtable,

76、i,i+len-1,i+2*len-1);　　i+=2*len;　　}　　if(i+len<=currentsize-1)//若只有最后兩個子序列　　merge(sourcetable,me

77、rgedtable,i,i+len-1,currentsize-1);　　else//若只有最后一個子序列　　for(int j=i;j<=currentsize-1;j++)　　mergedtable.arr[j]=sourcetable.arr[j];　　if(

78、len<=currentsize-1)　　{　　if(num<currentsize)　　{　　cout<<"第"<<++num<&l

79、t;"趟排序結果為:";　　for(int t=0;t<currentsize;t++)　　cout<<mergedtable.arr[t]<<" ";　　cout<<endl;<b

80、>　　}　　}　　}　　歸并排序　　在一趟歸并算法的基礎上，實現兩路歸并排序算法。在兩路歸并排序算法中，初始排序表存放在數組tabl

81、e.arr[]中,第一趟歸并將table.arr[]中的歸并項兩兩歸并，結果存放在輔助數組temptable.arr[]中。第二趟將temptable.arr[]中的歸并項兩兩歸并，結果放回原數組table.arr[]中，如此反復進行。為了將最后歸并結果仍放在數組table.arr[]中，歸并趟數應為偶數。如果做奇數趟就能完成時，最后還需要執(zhí)行一次一趟歸并過程，由于這時的歸并項長度len>=n，因此在則趟歸并中while循環(huán)不執(zhí)行

82、，只做把temptable.arr[]中的數據元素復制到table.arr[]的工作。　　偽代碼如下：　　template <class type>　　void sortlist<type>::mergesort(sortlist<type>

83、; &table )　　{//按數據元素關鍵字非遞減的順序對排序表table中數據元素進行遞歸排序　　sortlist<type> temptable;　　int len=1;　　while(len<currentsize)

84、　　{　　mergepass(table,temptable,len);len*=2;　　mergepass(temptable,table,len);len*=2;　　}&l

85、t;b>　　num=0;　　} 　　<9>主函數　　主要功能是顯示主菜單，以及對各種排序的調用　　偽代碼如下：

86、　　int main()//主函數　　{ 　　cout<<" ***********************************************************************"<<endl;<

87、/p>　　cout<<" 排序問題 "<<endl;　　cout<<"*********************************************************************

88、**"<<endl<<endl<<endl;　　int c=1; 　　char ch;　　int n1=0;

89、　while(c!=0)　　{　　cout<<"\======================================================================"<<endl;　　cout<<

90、;"===================可供選擇的排序方法==========================="<<endl;　　cout<<" 1 直接插入排序 2 折半插入排序 "<<endl;　　cout&l

91、t;<" 3 冒泡排序 4 簡單選擇排序 "<<endl;　　cout<<" 5 快速排序 6 堆排序 "<<endl;

92、　cout<<" 7 歸并排序 0 退出排序程序 "<<endl; 　　cout<<" ======================================================================="<<

93、;endl;　　cout<<"\n 請輸入您需要的排序種類:";　　cin>>ch;　　if(ch=='0') {cout<<" 您已成功退出該系統!"<<endl

94、;system("pause"); return 0;}　　int n,number;　　if(ch>='0'&&ch<='7')　　{　　cout&l

95、t;<"\n 輸入您要進行排序的數的個數：";　　cin>>n;　　cout<<"\n 請輸入"<<n<<"個數：";　　sortlist<int&

96、gt;table(n);　　for(int i=0;i<n;i++)　　{cin>>number;table.insert(i,number);}　　switch(ch)　　{ <p&g

97、t;　　case '1':　　cout<<"\n *******您選擇的是直接插入排序*******\n"<<endl;　　table.insertionsort();　　break;</

98、b>　　system("pause");　　break;　　case '2':　　cout<<"\n *******您選擇的是折

99、半插入排序*******\n"<<endl;　　table.binaryinsertsort();　　break;　　system("pause");　　break;<

100、/b>　　case '3':　　cout<<"\n *******您選擇的是冒泡排序*******\n"<<endl;　　table.bubblesort();&l

101、t;b>　　break;　　system("pause");　　break;　　case '4':　　cout<<&quo

102、t;\n *******您選擇的是簡單選擇排序*******\n"<<endl;　　table.selectsort();　　break;　　system("pause");<b&g

103、t;　　break;　　case '5':　　cout<<"\n *******您選擇的是快速排序*******\n"<<endl;　　table.quicksort(0,n-1);</

104、p>　　break;　　system("pause");　　break;　　case '6':

105、　　cout<<"\n *******您選擇的是堆排序*******\n"<<endl;　　table.heapsort();　　break;　　system("pause");<

106、;p>　　break;　　case '7':　　cout<<"\n *******您選擇的是歸并排序*******\n"<<endl;　　table.mergesort

107、(table);　　break;　　system("pause");　　break; 　　}&l

108、t;b>　　}　　}　　system("pause");　　return 0;　　}&l

109、t;p>　　三上機結果及體會　　實際完成的情況說明　　此程序主要實現了對不同排序算法的演示，并給出了每一趟的變化情況　　程序的性能分析　　直接插入排序

110、（穩(wěn)定的排序方法）　　1時間復雜度　　若待排序記錄按關鍵字從小到大排列(正序)　　關鍵字比較次數：　　記錄移動次數：2(n-1)　　b)若待排序記錄按關鍵

111、字從大到小排列(逆序)　　關鍵字比較次數：　　記錄移動次數：　　c) 若待排序記錄是隨機的，取最好和最壞情況的平均值　　關鍵字比較次數(約為)：　　記錄移

112、動次數(約為)：　　2空間復雜度：S(n)=O(1)　　折半插入排序（穩(wěn)定的排序算法）　　就平均性能而言，因為折半查找優(yōu)于順序查找，所以折半插入排序也優(yōu)于直接插入排序。　　關鍵字的比較次數為：n*log2(n)　　冒泡排序（穩(wěn)定的

113、排序算法）　　時間復雜度：　　最好情況（正序）　　比較次數：n-1（只要進行一趟即可）　　移動次數：0<b&g

114、t;　　最壞情況（逆序）　　比較次數：（需n-1趟，每趟達到最大比較次數） 　　移動次數：　　在最壞情況下，時間復雜度為:T(n)=O(n²)　　空間復雜度：S(n)=O(1)&l

115、t;p>　　簡單選擇排序（不穩(wěn)定的排序方法）　　時間復雜度：O(n2)。　　空間復雜度：S(1)。　　e. 快速排序（不穩(wěn)定的排序方法）　　1.時間復雜度　　最好情況（每次總是選到中間值

116、作樞軸）T(n)=O(nlog2n)　　最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n²) 　　2.空間復雜度：需?？臻g以實現遞歸　　最壞情況：S(n)=O(n)　　一般情況：S(n)=O(log2n)

117、f. 堆排序（不穩(wěn)定的排序方法）]　　1.間復雜性為O(nlog2n)。　　2空間復雜性為O(1)。　　g. 歸并排序（穩(wěn)定的排序方法）　　1時間復雜度為O(nlog2n)。　　2空間復雜度為O(n）。&l

118、t;p>　　3）運行情況　　主菜單　　直接插入排序　　折半插入排序　　冒泡排序

119、;　　簡單選擇排序　　快速排序　　堆排序　　歸并排序　　退出

120、系統　　上機過程中出現的問題及其解決方案　　1 快速排序時出現多一次排序的情況解決方法：在進行循環(huán)體時，多運行了一次，將運行次序減1即可。　　2 堆排序時也出現與上一條相同的情況解決方法：由于缺少一個判斷語句導致輸出只能是偶數倍趟數，因此加一條if(len<=currentsize-

121、1)判斷語句就可以使程序正常輸出結果　　3 快速排序趟數開始為1 ,2 ,1, 2出現解決方法：再定義一個全局變量，不過當其用完時，沒有將它重新置為0，這樣最后輸出的趟數就正確了。　　4 運行程序時，若輸入字符，則必須輸入完全后，才判斷其為不正確的選擇解決方法：加一個if判斷語句即可　　程序中可以改進的地方說

122、明　　本程序不能判斷字符數大于1的字符串，這方面需要改進　　可以在程序中加入性能分析，例如空間復雜度，時間復雜度等　　程序中可以擴充的功能及其設計實現假想　　擴充功能：可以加入希爾排序等未加入的排序方法，可以加入性能分析　　實現假

123、想：加入其他排序方法后，輸出為正確排序的過程，加入性能分析時，輸出排序過程的同時，可以輸出時間復雜度與空間復雜度　　6) 收獲及體會　　在進行為期一個星期的課程設計中，最終完成了算法。這期間，遇到的各種麻煩也都相繼解決。從這次實踐中，我意識到自己還有很多不足之處。　　首先先說

124、一下基本的。對于各種排序算法的過程還是不夠熟悉，進行編程時還需要翻書查找，對于這一點，只能說對數據結構的學習還不夠扎實，雖然說這門課程以后就沒有了，但是我想這門課對以后的學習會有很大幫助，所以有空時還應該繼續(xù)熟悉這門課程。　　其次，就是對于錯誤的處理，不能得心應手，不能正確處理一些簡單的錯誤。對于邏輯上的錯誤，不能夠立即找到出錯點，往往需要向同學請教才能找出錯誤，并且改正。我覺得這是自己獨自思考

125、能力不高的問題，遇事需要自己仔細想想，若還不能改正，再請教別人也不遲。　　從總體上說，整個代碼的實現還是存在不足的，例如本程序不能判斷字符數大于1的字符串，沒有相應排序的性能分析（如空間復雜度，時間復雜度），等等。從這點看，說明自己的程序還是不夠完善，不能做到十全十美，希望以后能有所修正。　　總而言之，從這次的實踐中我學到了很多東西，希望以后能夠多加運應

126、 　　7) 源代碼：　　#include "stdafx.h"　　#include<iostream>　　using namespace std;　　const

127、 int maxsize=100;　　int num=0;//定義全局變量，為每一趟的輸出做準備　　int x=0;　　template<class type>class sortlist　　{<

128、/b>　　private:　　int currentsize;//數據表中數據元素的個數　　public:　　type *arr;//存儲數據元素的向量（排序表）&l

129、t;p>　　sortlist():currentsize(0){arr=new type[maxsize];}//構造函數　　sortlist(int n){arr=new type[maxsize];currentsize=n;}　　void insert(int i,type x){arr[i]=x;}

130、　　~sortlist(){delete []arr;}//析構函數　　void swap(type &x,type &y)//數據元素x和y交換位置　　{type temp=x;x=y;y=temp;}　　void bubblesort();//冒泡排序

131、　　void quicksort(int low,int high);//快速排序　　void insertionsort();//直接插入排序　　void binaryinsertsort();//折半插入排序　　void selectsort();//簡單選擇排序

132、void heapsort();//堆排序　　void mergesort(sortlist<type> &table);//歸并排序　　void filterdown(const int start);//建立最大堆　　void mergepass(sortlist<type>&

133、amp;sourcetable,sortlist<type>&mergedtable,const int len);//一趟歸并　　void merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int

134、 right);//兩路歸并算法　　};　　template <class type>//直接插入排序　　void sortlist<type>::insertionsort()　　{<

135、/b>　　type temp;　　int j;　　for(int i=1;i<=currentsize-1;i++)　　{　　temp=arr

136、[i];j=i-1;　　while(j>=0&&temp<arr[j])　　{arr[j+1]=arr[j];j--;}　　arr[j+1]=temp;　　cout<<"第"<<++num<&l

137、t;"趟排序結果為:";　　for(int t=0;t<currentsize;t++)　　cout<<arr[t]<<" ";　　cout<<endl;　　}</

138、b>　　num=0;　　}　　template <class type>//折半插入排序　　void sortlist<type>::binaryinsertsort

139、()　　{　　type temp;　　int left,right;　　for(int i=1;i<currentsize;i++)　　{ <

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構課程設計報告---幾種排序算法的演示

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計報告---幾種排序算法的演示

文檔簡介

溫馨提示

最新文檔

評論

免費下載