

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、<p> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 </p><p><b> 幾種排序算法的演示</b></p><p> 班級: 姓名: 學(xué)號: 完成日期:</p><p><b> 一 需求分析</b></p><p><b> 1.運行環(huán)境</b>&l
2、t;/p><p> Microsoft Visual Studio 2008</p><p> 2.程序所實現(xiàn)的功能</p><p> 對直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序算法的演示,并且輸出每一趟的排序情況。</p><p> 3.程序的輸入(包含輸入的數(shù)據(jù)格式和說明)</p>
3、<p> <1>排序種類三輸入</p><p> <2>排序數(shù)的個數(shù)的輸入</p><p> <3>所需排序的所有數(shù)的輸入 </p><p> 4.程序的輸出(程序輸出的形式)</p><p><b> <1>主菜單的輸出</b></p>
4、<p> <2>每一趟排序的輸出,即排序過程的輸出</p><p> 5.測試數(shù)據(jù),如果程序輸入的數(shù)據(jù)量比較大,需要給出測試數(shù)據(jù)。</p><p><b> 二 設(shè)計說明</b></p><p><b> 1.算法設(shè)計思想</b></p><p> <1>
5、;交換排序(冒泡排序、快速排序)</p><p> 交換排序的基本思想是:對排序表中的數(shù)據(jù)元素按關(guān)鍵字進行兩兩比較,如果發(fā)生逆序(即排列順序與排序后的次序正好相反),則兩者交換位置,直到所有數(shù)據(jù)元素都排好序為止。</p><p> <2>插入排序(直接插入排序、折半插入排序)</p><p> 插入排序的基本思想是:每一次設(shè)法把一個數(shù)據(jù)元素插入到已
6、經(jīng)排序的部分序列的合適位置,使得插入后的序列仍然是有序的。開始時建立一個初始的有序序列,它只包含一個數(shù)據(jù)元素。然后,從這個初始序列出發(fā)不斷插入數(shù)據(jù)元素,直到最后一個數(shù)據(jù)元素插到有序序列后,整個排序工作就完成了。</p><p> <3>選擇排序(簡單選擇排序、堆排序)</p><p> 選擇排序的基本思想是:第一趟在有n個數(shù)據(jù)元素的排序表中選出關(guān)鍵字最小的數(shù)據(jù)元素,然后在剩
7、下的n-1個數(shù)據(jù)元素中再選出關(guān)鍵字最小(整個數(shù)據(jù)表中次?。┑臄?shù)據(jù)元素,依次重復(fù),每一趟(例如第i趟,i=1,…,n-1)總是在當(dāng)前剩下的n-i+1個待排序數(shù)據(jù)元素中選出關(guān)鍵字最小的數(shù)據(jù)元素,作為有序數(shù)據(jù)元素序列的第i個數(shù)據(jù)元素。等到第n-1趟選擇結(jié)束,待排序數(shù)據(jù)元素僅剩下一個時就不用再選了,按選出的先后次序所得到的數(shù)據(jù)元素序列即為有序序列,排序即告完成。</p><p> <4>歸并排序(兩路歸并排
8、序)</p><p> 兩路歸并排序的基本思想是:假設(shè)初始排序表有n個數(shù)據(jù)元素,首先把它看成是長度為1的首尾相接的n個有序子表(以后稱它們?yōu)闅w并項),先做兩兩歸并,得n/2上取整個長度為2的歸并項(如果n為奇數(shù),則最后一個歸并項的長度為1);再做兩兩歸并,……,如此重復(fù),最后得到一個長度為n的有序序列。</p><p> 2.程序的主要流程圖</p><p>
9、 3.程序的主要模塊(要求對主要流程圖中出現(xiàn)的模塊進行說明)</p><p> 程序的主要模塊主要分為主菜單模塊和排序算法演示模塊。</p><p><b> <1>主菜單</b></p><p> 主要功能:程序運行時,可使運行者根據(jù)提醒輸入相關(guān)操作,從而進入不同的排序方法或者退出。</p><p>
10、 <2>排序方法及輸出</p><p> 根據(jù)運行者對排序的不同選擇,進入排序過程</p><p> a.直接插入排序:根據(jù)直接排序的算法,輸出排序過程</p><p> b.折半插入排序:根據(jù)折半插入的算法,輸出排序過程</p><p> c.冒泡排序:根據(jù)冒泡排序算法,輸出排序過程</p><p&
11、gt; d.簡單選擇排序:根據(jù)簡單選擇排序的算法,輸出排序過程</p><p> e.快速排序:根據(jù)快速排序的算法,輸出排序過程</p><p> f.堆排序:根據(jù)堆排序的算法,輸出排序過程</p><p> g.歸并排序:根據(jù)歸并排序的算法,輸出排序過程</p><p> 4. 程序的主要函數(shù)及其偽代碼說明</p>
12、<p><b> <1>模板類</b></p><p> 主要說明程序中用到的類的定義</p><p> template<class type>class sortlist</p><p><b> {</b></p><p><b> pri
13、vate:</b></p><p> int currentsize;//數(shù)據(jù)表中數(shù)據(jù)元素的個數(shù)</p><p><b> public:</b></p><p> type *arr;//存儲數(shù)據(jù)元素的向量(排序表)</p><p> sortlist():currentsize(0){arr=ne
14、w type[maxsize];}//構(gòu)造函數(shù)</p><p> sortlist(int n){arr=new type[maxsize];currentsize=n;}</p><p> void insert(int i,type x){arr[i]=x;}</p><p> ~sortlist(){delete []arr;}//析構(gòu)函數(shù)</p&
15、gt;<p> void swap(type &x,type &y)//數(shù)據(jù)元素x和y交換位置</p><p> {type temp=x;x=y;y=temp;}</p><p> void bubblesort();//冒泡排序</p><p> void quicksort(int low,int high);//快速排序
16、</p><p> void insertionsort();//直接插入排序</p><p> void binaryinsertsort();//折半插入排序</p><p> void selectsort();//簡單選擇排序</p><p> void heapsort();//堆排序</p><p>
17、; void mergesort(sortlist<type> &table);//歸并排序</p><p> void filterdown(const int start);//建立最大堆</p><p> void mergepass(sortlist<type>&sourcetable,sortlist<type>&
18、mergedtable,const int len);//一趟歸并</p><p> void merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);//兩路歸并算法</p><p><
19、b> };</b></p><p><b> <2>直接插入排序</b></p><p> 直接插入排序的基本思想:開始時把第一個數(shù)據(jù)元素作為初始的有序序列,然后從第二個數(shù)據(jù)元素開始依次把數(shù)據(jù)元素按關(guān)鍵字大小插入到已排序的部分排序表的適當(dāng)位置。當(dāng)插入第i(1<i<=n)個數(shù)據(jù)元素時,前面的i-1個數(shù)據(jù)元素已經(jīng)排好序,這時
20、,用第i個數(shù)據(jù)元素的關(guān)鍵字與前面的i-1個數(shù)據(jù)元素的關(guān)鍵字順序進行比較,找到插入位置后就將第i個數(shù)據(jù)元素插入。如此進行n-1次插入,就完成了排序。</p><p> 以下是在順序表上實現(xiàn)的直接插入排序</p><p> 在順序表上進行直接插入排序時,當(dāng)插入第i(1<i<=n)個數(shù)據(jù)元素時,前面的arr[0]、arr[1]、…、arr[i-2]已經(jīng)排好序,這時,用arr[i-
21、1]的關(guān)鍵字依次與arr[i-2],arr[i-3],…的關(guān)鍵字順序進行比較,如果這些數(shù)據(jù)元素的關(guān)鍵字大于arr[i-1]的關(guān)鍵字,則將數(shù)據(jù)元素向后移一個位置,當(dāng)找到插入位置后就將arr[i-1]插入,就完成了arr[0],arr[1],…,arr[n-1]的排序。</p><p><b> 偽代碼如下</b></p><p> template <clas
22、s type>//直接插入排序</p><p> void sortlist<type>::insertionsort()</p><p><b> {</b></p><p> type temp;</p><p><b> int j;</b></p>&
23、lt;p> for(int i=1;i<=currentsize-1;i++)</p><p><b> {</b></p><p> temp=arr[i];j=i-1;</p><p> while(j>=0&&temp<arr[j])</p><p> {arr[j
24、+1]=arr[j];j--;}</p><p> arr[j+1]=temp;</p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p>
25、 cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> }</b><
26、/p><p><b> <3>折半插入排序</b></p><p> 折半插入排序的基本思想:設(shè)在排序表中有n個數(shù)據(jù)元素arr[0],arr[1],…,arr[n-1]。其中,arr[0],arr[1],…,arr[n-1]是已經(jīng)排好序的部分?jǐn)?shù)據(jù)元素序列,在插入arr[i]時,利用折半查找方法尋找arr[i]的插入位置。折半插入排序方法只能在順序表存儲結(jié)構(gòu)
27、實現(xiàn)。</p><p><b> 偽代碼如下:</b></p><p> template <class type>//折半插入排序</p><p> void sortlist<type>::binaryinsertsort()</p><p><b> {</b>
28、</p><p> type temp;</p><p> int left,right;</p><p> for(int i=1;i<currentsize;i++)</p><p><b> { </b></p><p> left=0;right=i-1;temp=arr[
29、i];</p><p> while(left<=right)//找插入位置</p><p><b> {</b></p><p> int mid=(left+right)/2;</p><p> if(temp<arr[mid])right=mid-1;</p><p>
30、 else left=mid+1;</p><p><b> }</b></p><p> for(int k=i-1;k>=left;k--)//向后移動</p><p> arr[k+1]=arr[k];</p><p> arr[left]=temp;</p><p> co
31、ut<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<e
32、ndl;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> }</b></p><p><b> <4>冒泡排序</b></p><p> 冒泡排序
33、的基本思想是:設(shè)排序表中有n個數(shù)據(jù)元素。首先對排序表中第一,二個數(shù)據(jù)元素的關(guān)鍵字arr[0]和arr[1]進行比較。如果前者大于后者,則進行交換;然后對第二,三個數(shù)據(jù)做同樣的處理;重復(fù)此過程直到處理完最后兩個相鄰的數(shù)據(jù)元素。我們稱之為一趟冒泡,它將關(guān)鍵字最大的元素移到排序表的最后一個位置,其他數(shù)據(jù)元素一般也都向排序的最終位置移動。然后進行第二趟排序,對排序表中前n-1個元素進行與上述同樣的操作,其結(jié)果使整個排序表中關(guān)鍵字次大的數(shù)據(jù)元素被
34、移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有數(shù)據(jù)元素排好序。</p><p><b> 偽代碼如下:</b></p><p> template <class type>//冒泡排序</p><p> void sortlist<type>:: bubblesort()</p><
35、;p><b> {</b></p><p><b> int i=1;</b></p><p> int finish=0;//0表示還沒有排好序</p><p> while(i<currentsize &&!finish)</p><p><b>
36、 {</b></p><p> finish=1;//排序結(jié)束標(biāo)志置為,假定已經(jīng)排好序</p><p> for(int j=0;j<currentsize-i;j++)</p><p> if(arr[j]>arr[j+1])//逆序</p><p><b> {</b></p&g
37、t;<p> swap(arr[j],arr[j+1]);//相鄰元素交換位置</p><p><b> finish=0;</b></p><p> }//排序結(jié)束標(biāo)志置為,表示本趟發(fā)生了交換,說明還沒有排好序</p><p><b> i++;</b></p><p>
38、cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<
39、;endl;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> }</b></p><p> <5>簡單選擇排序(直接選擇排序)</p><p> 直接選擇排序的算法基本
40、思想是:</p><p> a)開始時設(shè)i的初始值為0。</p><p> b)如果i<n-1,在數(shù)據(jù)元素序列arr[i]arr[n-1]中,選出具有最小關(guān)鍵字的數(shù)據(jù)元素arr[k];否則算法結(jié)束。</p><p> c)若arr[k]不是這組數(shù)據(jù)元素中的第一個數(shù)據(jù)元素(i≠k),則將arr[k]與arr[i]這兩數(shù)據(jù)元素的位置對調(diào);</p>
41、<p> d)令i=i+1轉(zhuǎn)步驟 b)。</p><p><b> 偽代碼如下:</b></p><p> template <class type></p><p> void sortlist<type>::selectsort()//簡單選擇排序</p><p><
42、;b> {</b></p><p><b> int k;</b></p><p> for(int i=0;i<=currentsize-1;i++)</p><p><b> {</b></p><p><b> k=i;</b></
43、p><p> for(int j=i+1;j<currentsize;j++)</p><p> if(arr[j]<arr[k])</p><p> k=j;//k 指示當(dāng)前序列中最小者的位置</p><p> if(k!=i)//最小關(guān)鍵字的數(shù)據(jù)元素位置不等于i</p><p> swap(arr
44、[i],arr[k]);</p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" "
45、;</p><p> cout<<endl;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> }</b></p><p><b> <6>快速排序
46、</b></p><p> 快速排序(Quick Sort)又被稱做分區(qū)交換排序,這是一種平均性能非常好的排序方法。</p><p> 其算法基本思想是:任取排序表中的某個數(shù)據(jù)元素(例如取第一個數(shù)據(jù)元素)作為基準(zhǔn),按照該數(shù)據(jù)元素的關(guān)鍵字大小,將整個排序表劃分為左右兩個子表: 左側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都小于基準(zhǔn)數(shù)據(jù)元素的關(guān)鍵字。右側(cè)子表中所有數(shù)據(jù)元素的關(guān)鍵字都大于或等于
47、基準(zhǔn)數(shù)據(jù)元素的關(guān)鍵字,基準(zhǔn)數(shù)據(jù)元素則排在這兩個子表中間(這也是該數(shù)據(jù)元素最終應(yīng)安放的位置),然后分別對這兩個子表重復(fù)施行上述方法的快速排序,直到所有的子表長度為1,則排序結(jié)束。</p><p><b> 偽代碼如下:</b></p><p> template <class type>//快速排序</p><p> void
48、sortlist<type>::quicksort(int low,int high)//在待排序區(qū)間[low,high]上,遞歸地進行快速排序</p><p><b> {</b></p><p> int i=low,j=high;</p><p> type temp=arr[low];//取區(qū)間第一個位置為基準(zhǔn)位置&l
49、t;/p><p><b> if(i<j)</b></p><p><b> {</b></p><p> while(i<j)</p><p><b> {</b></p><p> while(i<j&&tem
50、p<arr[j])j--;</p><p> if(i<j){swap(arr[i],arr[j]);i++;}</p><p> while(i<j&&temp>=arr[i])i++;</p><p> if(i<j){swap(arr[i],arr[j]);j--;}</p><p>
51、<b> }</b></p><p> arr[i]=temp;//將基準(zhǔn)元素就位</p><p> cout<<"第"<<++x<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p>
52、<p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p> quicksort(low,i-1);//在左子區(qū)間遞歸進行快速排序</p><p> quicksort(i+1,high);//在右子區(qū)間遞歸進行快速排序</p>
53、<p><b> }</b></p><p><b> }</b></p><p> <7>堆排序(包括建立最大堆和堆排序兩個過程)</p><p> 堆排序算法的基本思想是:</p><p> a.對排序表中的數(shù)據(jù)元素,利用堆的調(diào)整算法形成初始堆。</p&g
54、t;<p><b> b.輸出堆頂元素。</b></p><p> c.對剩余元素重新調(diào)整形成堆。</p><p> d.重復(fù)執(zhí)行第b、c步,直到所有數(shù)據(jù)元素被輸出。 </p><p> (1)建立最大堆的偽代碼如下:</p><p> template <class type>//建
55、立最大堆</p><p> void sortlist<type>::filterdown(const int start)</p><p> {//向下調(diào)整使從start開始到currentsize-1為止的子表成為最大堆</p><p> int i=start,j=2*i+1;//j為i的左孩子</p><p> i
56、nt tablesize=currentsize;</p><p> type temp=arr[i];</p><p> while(j<=currentsize-1)</p><p><b> {</b></p><p> if(j<currentsize-1 && arr[j]&
57、lt;arr[j+1])</p><p> j++;//在兩個孩子中選關(guān)鍵字較大者</p><p> if(temp>=arr[j])break;</p><p> else{arr[i]=arr[j];i=j;j=2*j+1;</p><p><b> }</b></p><p>
58、<b> }</b></p><p> arr[i]=temp;</p><p><b> }</b></p><p><b> (2)堆排序</b></p><p> 如果建立的堆滿足最大堆的條件,則堆的第一個數(shù)據(jù)元素arr[0]具有最大的關(guān)鍵字,將arr[0]與a
59、rr[n-1]對調(diào),把具有最大關(guān)鍵字的數(shù)據(jù)元素交換到最后,再對前面的n-1個數(shù)據(jù)元素使用堆的調(diào)整算法,重新建立最大堆,結(jié)果把具有次最大關(guān)鍵字的數(shù)據(jù)元素又上浮到堆頂,即arr[0]的位置,再對調(diào)arr[0]和arr[n-2],…,如此反復(fù)執(zhí)行n-1次,最后得到全部排序好的數(shù)據(jù)元素序列。</p><p><b> 偽代碼如下:</b></p><p> templat
60、e <class type>//堆排序</p><p> void sortlist<type>::heapsort()</p><p><b> {</b></p><p> int tablesize=currentsize;</p><p> for(int i=(currentsi
61、ze-2)/2;i>=0;i--)</p><p> filterdown(i); //初始建堆</p><p> for(int i=currentsize-1;i>=1;i--)</p><p><b> {</b></p><p> swap(arr[0],arr[i]);//堆頂
62、元素和最后一個元素交換</p><p> currentsize--;</p><p> filterdown(0);//重建最大堆</p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<
63、;tablesize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><b> }</b></p><p><b> num=0;</b></p>
64、<p> currentsize=tablesize;</p><p><b> }</b></p><p> <8>歸并排序(包括歸并算法,一趟歸并算法和歸并排序)</p><p><b> 歸并算法</b></p><p> 其基本思想是:設(shè)有兩個有序表A和B
65、,其數(shù)據(jù)元素個數(shù)(表長)分別為n和m,變量i和j分別是表A和表B的當(dāng)前檢測指針;設(shè)表C是歸并后的新有序表,變量k是它的當(dāng)前存放指針。開始時i、j、k都分別指向A、B、C三個表的起始位置;然后根據(jù)A[i]與B[j]的關(guān)鍵字的大小,把關(guān)鍵字小的數(shù)據(jù)元素放到新表C[k]中;且相應(yīng)的檢測指針(i或j)和存放指針k增加1.如此循環(huán),當(dāng)i與j中有一個已經(jīng)超出表長時,將另一個表中的剩余部分照抄到新表C[k]~C[m+n]中。</p>&
66、lt;p> 下面的歸并算法中,兩個待歸并的有序表首尾相接存放在數(shù)組sourcetable.arr[]中,其中第一個表的下標(biāo)范圍從left到mid,另一個表的下標(biāo)范圍從mid+1到right。前一個表中有mid-left+1個數(shù)據(jù)元素,后一個表中有right –mid個數(shù)據(jù)元素。歸并后得到的新有序表有right –mid個數(shù)據(jù)元素。歸并后得到的新有序表存放在另一個輔助數(shù)組mergedtable.arr[]中,其下標(biāo)范圍從left到
67、right。</p><p><b> 偽代碼如下:</b></p><p> template <class type></p><p> void sortlist<type>::merge(sortlist<type>&sourcetable,sortlist<type>&am
68、p;mergedtable,const int left,const int mid,const int right)</p><p><b> {</b></p><p> int i=left,j=mid+1,k=left;//指針初始化</p><p> //i是前一段的當(dāng)前元素位置,j是后一段的當(dāng)前元素位置,k是輔助數(shù)組的當(dāng)前位置
69、</p><p> while(i<=mid&&j<=right)</p><p> if(sourcetable.arr[i]<=sourcetable.arr[j])</p><p> {mergedtable.arr[k]=sourcetable.arr[i];i++;k++;}</p><p>
70、 else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;}</p><p> if(i<=mid)</p><p> for(int p=k,q=i;q<=mid;p++,q++)</p><p> mergedtable.arr[p]=sourcetable.arr[q];//把前一段復(fù)制到mer
71、gedtable</p><p><b> else</b></p><p> for(int p=k,q=j;q<=right;p++,q++)</p><p> mergedtable.arr[p]=sourcetable.arr[q];//把后一段復(fù)制到mergedtable</p><p><b
72、> }</b></p><p><b> 一趟歸并算法</b></p><p> 設(shè)數(shù)組sourcetable.arr[0]到sourcetable.arr[n-1]中的n個數(shù)據(jù)元素已經(jīng)分為一些長度為len的歸并項,將這些歸并項兩兩歸并,歸并成一些長度為2len的歸并項,結(jié)果放到mergedtable.arr[]中。如果n不是2len的整數(shù)倍,
73、則一趟歸并到最后,可能遇到兩種情況:</p><p> 剩下一個長度為len的歸并項和一個長度不足len的歸并項,可用一次merge算法,將它們歸并成一個長度小于2len的歸并項。</p><p> 只剩下一個歸并項,其長度小于或等于len,可將它直接復(fù)制到數(shù)組mergedtable.arr[]中。</p><p><b> 偽代碼如下:</b
74、></p><p> template <class type></p><p> template <class type></p><p> void sortlist<type>::mergepass(sortlist<type>&sourcetable,sortlist<type>
75、;&mergedtable,const int len)</p><p><b> {</b></p><p><b> int i=0;</b></p><p> while(i+2*len<=currentsize-1)//表示至少有個子序列</p><p><b>
76、; {</b></p><p> merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);</p><p><b> i+=2*len;</b></p><p><b> }</b></p><p> if(i+len<=cu
77、rrentsize-1)//若只有最后兩個子序列</p><p> merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);</p><p> else//若只有最后一個子序列</p><p> for(int j=i;j<=currentsize-1;j++)</p><p>
78、; mergedtable.arr[j]=sourcetable.arr[j];</p><p> if(len<=currentsize-1)</p><p><b> {</b></p><p> if(num<currentsize)</p><p><b> {</b>
79、</p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<mergedtable.arr[t]<<" "
80、;</p><p> cout<<endl;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> 歸并排序</b><
81、/p><p> 在一趟歸并算法的基礎(chǔ)上,實現(xiàn)兩路歸并排序算法。在兩路歸并排序算法中,初始排序表存放在數(shù)組table.arr[]中,第一趟歸并將table.arr[]中的歸并項兩兩歸并,結(jié)果存放在輔助數(shù)組temptable.arr[]中。第二趟將temptable.arr[]中的歸并項兩兩歸并,結(jié)果放回原數(shù)組table.arr[]中,如此反復(fù)進行。為了將最后歸并結(jié)果仍放在數(shù)組table.arr[]中,歸并趟數(shù)應(yīng)為偶數(shù)
82、。如果做奇數(shù)趟就能完成時,最后還需要執(zhí)行一次一趟歸并過程,由于這時的歸并項長度len>=n,因此在則趟歸并中while循環(huán)不執(zhí)行,只做把temptable.arr[]中的數(shù)據(jù)元素復(fù)制到table.arr[]的工作。</p><p><b> 偽代碼如下:</b></p><p> template <class type></p>
83、<p> void sortlist<type>::mergesort(sortlist<type> &table )</p><p> {//按數(shù)據(jù)元素關(guān)鍵字非遞減的順序?qū)ε判虮韙able中數(shù)據(jù)元素進行遞歸排序</p><p> sortlist<type> temptable;</p><p> in
84、t len=1;</p><p> while(len<currentsize)</p><p><b> {</b></p><p> mergepass(table,temptable,len);len*=2;</p><p> mergepass(temptable,table,len);len*=2
85、;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> } </b></p><p><b> <9>主函數(shù)</b></p><p> 主要功能是顯示
86、主菜單,以及對各種排序的調(diào)用</p><p><b> 偽代碼如下:</b></p><p><b> 三 上機結(jié)果及體會</b></p><p> int main()//主函數(shù)</p><p><b> { </b></p><p>
87、 //time_t timestart,timeend;double timeused;</p><p> double timestart,timeend,timeused;</p><p><b> int c=1; </b></p><p><b> char ch;</b></p><p
88、><b> int n1=0;</b></p><p> while(c!=0)</p><p><b> {</b></p><p> cout<<endl;</p><p> cout<<"****************************
89、*******排序菜單************************************"<<endl;</p><p> cout<<" "<<endl;</p>&l
90、t;p> cout<<"==================================排序法選擇==================================="<<endl;</p><p> cout<<"
91、 "<<endl;</p><p> cout<<" 1.直接插入排序 2.冒泡排序 3.快速排序 4.歸并排序 "<<endl;</p><p> cout<<" 5.折半插入排序 6.簡單選擇排序 7.堆排序
92、 0.退出排序程序 "<<endl;</p><p> cout<<" "<<endl; </p><p> cout<&
93、lt;"*******************************************************************************"<<endl;</p><p> cout<<"\n請選擇所需排序法:";</p><p><b> cin>>ch;</b
94、></p><p> if(ch=='0')</p><p><b> {</b></p><p> cout<<"退出系統(tǒng)!"<<endl;system("pause"); return 0;</p><p><b>
95、 }</b></p><p> int n,cishuber;</p><p> if(ch>='0'&&ch<='7')</p><p><b> {</b></p><p> cout<<"\n請輸入排序的數(shù)的
96、個數(shù):";</p><p><b> cin>>n;</b></p><p> cout<<"\n請輸入"<<n<<"個數(shù):";</p><p> sortlist<int>table(n);</p><p&g
97、t; for(int i=0;i<n;i++)//輸入n個數(shù)據(jù)</p><p><b> {</b></p><p> cin>>cishuber;table.insert(i,cishuber);</p><p><b> }</b></p><p> switch(c
98、h)</p><p><b> { </b></p><p><b> case '1':</b></p><p> cout<<"\n ======直接插入排序法過程演示======\n"<<endl;</p><p> ti
99、mestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p><p> Sleep(1000);</p><p> table.zhicha();</p><p> timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms)
100、 </p><p> timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p> cout<<"直接插入排序用時為:"<<timeused<<"ms&q
101、uot;;</p><p><b> break;</b></p><p> system("pause");</p><p><b> break;</b></p><p><b> case '2':</b></p
102、><p> cout<<"\n ======冒泡排序法過程演示======\n"<<endl;</p><p> timestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p><p> Sleep(1000);</p><
103、p> table.maopao();</p><p> timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p><p> timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK;
104、 </p><p> cout<<"冒泡排序用時為:"<<timeused<<"ms";</p><p><b> break;</b></p><p> system("pause");</p><
105、p><b> break;</b></p><p><b> case '3':</b></p><p> cout<<"\n ======快速排序法過程演示======\n"<<endl;</p><p> timestart=GetTickC
106、ount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p><p> Sleep(1000);</p><p> table.kuaisu(0,n-1);</p><p> timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p>
107、<p> timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK;</p><p> cout<<"快速排序用時為:"<<timeused<<"ms";</p><p><b> break;</b>&
108、lt;/p><p> system("pause");</p><p><b> break;</b></p><p><b> case '4':</b></p><p> cout<<"\n ======歸并排序法過程演示====
109、==\n"<<endl;</p><p> timestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p><p> Sleep(1000);</p><p> table.mergesort(table);</p><p> timeen
110、d=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p><p> timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p> cout<<&
111、quot;歸并排序用時為:"<<timeused<<"ms";</p><p><b> break;</b></p><p> system("pause");</p><p> break; </p><p>
112、<b> case '5':</b></p><p> cout<<"\n ======折半插入排序法過程演示======\n"<<endl;</p><p> timestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p
113、><p> Sleep(1000);</p><p> table.binaryinsertsort();</p><p> timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p><p> timeused=timeend
114、-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p> cout<<"折半插入排序用時為:"<<timeused<<"ms";</p><p><b> break;</b></p
115、><p> system("pause");</p><p><b> break;</b></p><p><b> case '6':</b></p><p> cout<<"\n ======簡單選擇排序法過程演示======\
116、n"<<endl;</p><p> timestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p><p> Sleep(1000);</p><p> table.selectsort();</p><p> timeend=GetTi
117、ckCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p><p> timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p> cout<<"簡
118、單選擇排序用時為:"<<timeused<<"ms";</p><p><b> break;</b></p><p> system("pause");</p><p><b> break;</b></p><p>
119、<b> case '7':</b></p><p> cout<<"\n ======堆排序法過程演示======\n"<<endl;</p><p> timestart=GetTickCount();//(double)clock();//程序段開始前取得系統(tǒng)運行時間(ms) </p&g
120、t;<p> Sleep(1000);</p><p> table.heapsort();</p><p> timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運行時間(ms) </p><p> timeused=timeend-timestar
121、t;//(double)(timeend-timestart)/CLK_TCK; </p><p> cout<<"堆排序用時為:"<<timeused<<"ms";</p><p><b> break;</b></p><p&
122、gt; system("pause");</p><p><b> break;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p>
123、<p> system("pause"); </p><p><b> return 0;</b></p><p><b> }</b></p><p><b> 1運行情況</b></p><p><b> 主菜單<
124、;/b></p><p><b> 直接插入排序</b></p><p><b> 冒泡排序</b></p><p><b> 快速排序</b></p><p><b> 歸并排序</b></p><p><b&
125、gt; 折半插入排序</b></p><p><b> 簡單選擇排序</b></p><p><b> 堆排序</b></p><p><b> 退出排序</b></p><p><b> 四、源代碼</b></p>&
126、lt;p> #include<time.h></p><p> #include<windows.h></p><p> #include<iostream></p><p> using namespace std;</p><p> const int maxsize=100;</
127、p><p> int cishu=0;//定義全局變量,為每一趟的輸出做準(zhǔn)備</p><p><b> int x=0;</b></p><p> template<class type>class sortlist</p><p><b> {</b></p>&l
128、t;p><b> private:</b></p><p> int momentsize;//數(shù)據(jù)表中數(shù)據(jù)元素的個數(shù)</p><p><b> public:</b></p><p> type *arr;//存儲數(shù)據(jù)元素的向量(排序表)</p><p> sortlist():m
129、omentsize(0)//無參的構(gòu)造函數(shù)</p><p><b> {</b></p><p> arr=new type[maxsize];</p><p><b> }</b></p><p> sortlist(int n)//帶參的構(gòu)造函數(shù)</p><p>
130、<b> {</b></p><p> arr=new type[maxsize];momentsize=n;</p><p><b> }</b></p><p> void insert(int i,type x){arr[i]=x;}</p><p> ~sortlist(){del
131、ete []arr;}//析構(gòu)函數(shù)</p><p> void swap(type &x,type &y)//數(shù)據(jù)元素x和y交換位置</p><p><b> {</b></p><p> type temp=x;x=y;y=temp;</p><p><b> }</b>&
132、lt;/p><p> void maopao();//冒泡排序</p><p> void kuaisu(int low,int high);//快速排序</p><p> void zhicha();//直接插入排序</p><p> void binaryinsertsort();//折半插入排序</p><p&g
133、t; void selectsort();//簡單選擇排序</p><p> void heapsort();//堆排序</p><p> void mergesort(sortlist<type> &table);//歸并排序</p><p> void filterdown(const int start);//建立最大堆</p
134、><p> void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);//一趟歸并</p><p> void merge(sortlist<type>&sourcetable,sortlist<type>&a
135、mp;mergedtable,const int left,const int mid,const int right);//兩路歸并算法</p><p><b> };</b></p><p> template <class type>//直接插入排序</p><p> void sortlist<type>:
136、:zhicha()</p><p><b> {</b></p><p> type temp;</p><p><b> int b;</b></p><p> for(int a=1;a<=momentsize-1;a++)</p><p><b>
137、; {</b></p><p> temp=arr[a];b=a-1;</p><p> while(b>=0&&temp<arr[b])</p><p><b> {</b></p><p> arr[b+1]=arr[b];</p><p>
138、 b--; </p><p><b> }</b></p><p> arr[b+1]=temp;</p><p> cout<<"第"<<++cishu<<"趟排序結(jié)果為:";</p><p> for(int t
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法演示系統(tǒng)
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序演示
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)58165
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法的實現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--- 數(shù)據(jù)結(jié)構(gòu)各章算法的演示系統(tǒng)
- 拓?fù)渑判?算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----內(nèi)部排序算法性能分析
- 幾種常見的排序算法的實現(xiàn)與性能分析數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序綜合
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計—綜合排序的設(shè)計
評論
0/150
提交評論