數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--幾種排序算法的演示

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 </p><p><b>　　幾種排序算法的演示</b></p><p>　　班級(jí)： 姓名： 學(xué)號(hào)： 完成日期：</p><p><b>　　一 需求分析</b></p><p><b>　　1.運(yùn)行環(huán)境</b>&l

2、t;/p><p>　　Microsoft Visual Studio 2008</p><p>　　2.程序所實(shí)現(xiàn)的功能</p><p>　　對(duì)直接插入排序、折半插入排序、冒泡排序、簡(jiǎn)單選擇排序、快速排序、堆排序、歸并排序算法的演示，并且輸出每一趟的排序情況。</p><p>　　3.程序的輸入（包含輸入的數(shù)據(jù)格式和說(shuō)明）</p>

3、<p>　　<1>排序種類三輸入</p><p>　　<2>排序數(shù)的個(gè)數(shù)的輸入</p><p>　　<3>所需排序的所有數(shù)的輸入 </p><p>　　4.程序的輸出（程序輸出的形式）</p><p><b>　　<1>主菜單的輸出</b></p>

4、<p>　　<2>每一趟排序的輸出，即排序過(guò)程的輸出</p><p>　　5.測(cè)試數(shù)據(jù)，如果程序輸入的數(shù)據(jù)量比較大，需要給出測(cè)試數(shù)據(jù)。</p><p><b>　　二 設(shè)計(jì)說(shuō)明</b></p><p><b>　　1.算法設(shè)計(jì)思想</b></p><p>　　<1>

5、;交換排序（冒泡排序、快速排序）</p><p>　　交換排序的基本思想是：對(duì)排序表中的數(shù)據(jù)元素按關(guān)鍵字進(jìn)行兩兩比較，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則兩者交換位置，直到所有數(shù)據(jù)元素都排好序?yàn)橹埂?lt;/p><p>　　<2>插入排序（直接插入排序、折半插入排序）</p><p>　　插入排序的基本思想是：每一次設(shè)法把一個(gè)數(shù)據(jù)元素插入到已

6、經(jīng)排序的部分序列的合適位置，使得插入后的序列仍然是有序的。開(kāi)始時(shí)建立一個(gè)初始的有序序列，它只包含一個(gè)數(shù)據(jù)元素。然后，從這個(gè)初始序列出發(fā)不斷插入數(shù)據(jù)元素，直到最后一個(gè)數(shù)據(jù)元素插到有序序列后，整個(gè)排序工作就完成了。</p><p>　　<3>選擇排序（簡(jiǎn)單選擇排序、堆排序）</p><p>　　選擇排序的基本思想是：第一趟在有n個(gè)數(shù)據(jù)元素的排序表中選出關(guān)鍵字最小的數(shù)據(jù)元素，然后在剩

7、下的n-1個(gè)數(shù)據(jù)元素中再選出關(guān)鍵字最?。ㄕ麄€(gè)數(shù)據(jù)表中次小）的數(shù)據(jù)元素，依次重復(fù)，每一趟（例如第i趟，i=1，…，n-1）總是在當(dāng)前剩下的n-i+1個(gè)待排序數(shù)據(jù)元素中選出關(guān)鍵字最小的數(shù)據(jù)元素，作為有序數(shù)據(jù)元素序列的第i個(gè)數(shù)據(jù)元素。等到第n-1趟選擇結(jié)束，待排序數(shù)據(jù)元素僅剩下一個(gè)時(shí)就不用再選了，按選出的先后次序所得到的數(shù)據(jù)元素序列即為有序序列，排序即告完成。</p><p>　　<4>歸并排序（兩路歸并排

8、序）</p><p>　　兩路歸并排序的基本思想是：假設(shè)初始排序表有n個(gè)數(shù)據(jù)元素，首先把它看成是長(zhǎng)度為1的首尾相接的n個(gè)有序子表（以后稱它們?yōu)闅w并項(xiàng)），先做兩兩歸并，得n/2上取整個(gè)長(zhǎng)度為2的歸并項(xiàng)（如果n為奇數(shù)，則最后一個(gè)歸并項(xiàng)的長(zhǎng)度為1）；再做兩兩歸并，……，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為n的有序序列。</p><p>　　2.程序的主要流程圖</p><p>　

9、　3.程序的主要模塊(要求對(duì)主要流程圖中出現(xiàn)的模塊進(jìn)行說(shuō)明)</p><p>　　程序的主要模塊主要分為主菜單模塊和排序算法演示模塊。</p><p><b>　　<1>主菜單</b></p><p>　　主要功能：程序運(yùn)行時(shí)，可使運(yùn)行者根據(jù)提醒輸入相關(guān)操作，從而進(jìn)入不同的排序方法或者退出。</p><p>

10、　　<2>排序方法及輸出</p><p>　　根據(jù)運(yùn)行者對(duì)排序的不同選擇，進(jìn)入排序過(guò)程</p><p>　　a.直接插入排序：根據(jù)直接排序的算法，輸出排序過(guò)程</p><p>　　b.折半插入排序：根據(jù)折半插入的算法，輸出排序過(guò)程</p><p>　　c.冒泡排序：根據(jù)冒泡排序算法，輸出排序過(guò)程</p><p&

11、gt;　　d.簡(jiǎn)單選擇排序：根據(jù)簡(jiǎn)單選擇排序的算法，輸出排序過(guò)程</p><p>　　e.快速排序：根據(jù)快速排序的算法，輸出排序過(guò)程</p><p>　　f.堆排序：根據(jù)堆排序的算法，輸出排序過(guò)程</p><p>　　g.歸并排序：根據(jù)歸并排序的算法，輸出排序過(guò)程</p><p>　　4. 程序的主要函數(shù)及其偽代碼說(shuō)明</p>

12、<p><b>　　<1>模板類</b></p><p>　　主要說(shuō)明程序中用到的類的定義</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ù)元素的個(gè)數(shù)</p><p><b>　　public:</b></p><p>　　type *arr;//存儲(chǔ)數(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();//簡(jiǎn)單選擇排序</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>　　直接插入排序的基本思想：開(kāi)始時(shí)把第一個(gè)數(shù)據(jù)元素作為初始的有序序列，然后從第二個(gè)數(shù)據(jù)元素開(kāi)始依次把數(shù)據(jù)元素按關(guān)鍵字大小插入到已排序的部分排序表的適當(dāng)位置。當(dāng)插入第i(1<i<=n)個(gè)數(shù)據(jù)元素時(shí)，前面的i-1個(gè)數(shù)據(jù)元素已經(jīng)排好序，這時(shí)

20、，用第i個(gè)數(shù)據(jù)元素的關(guān)鍵字與前面的i-1個(gè)數(shù)據(jù)元素的關(guān)鍵字順序進(jìn)行比較，找到插入位置后就將第i個(gè)數(shù)據(jù)元素插入。如此進(jìn)行n-1次插入，就完成了排序。</p><p>　　以下是在順序表上實(shí)現(xiàn)的直接插入排序</p><p>　　在順序表上進(jìn)行直接插入排序時(shí)，當(dāng)插入第i(1<i<=n)個(gè)數(shù)據(jù)元素時(shí)，前面的arr[0]、arr[1]、…、arr[i-2]已經(jīng)排好序，這時(shí)，用arr[i-

21、1]的關(guān)鍵字依次與arr[i-2],arr[i-3],…的關(guān)鍵字順序進(jìn)行比較，如果這些數(shù)據(jù)元素的關(guān)鍵字大于arr[i-1]的關(guān)鍵字，則將數(shù)據(jù)元素向后移一個(gè)位置，當(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個(gè)數(shù)據(jù)元素arr[0],arr[1],…,arr[n-1]。其中，arr[0],arr[1],…,arr[n-1]是已經(jīng)排好序的部分?jǐn)?shù)據(jù)元素序列，在插入arr[i]時(shí)，利用折半查找方法尋找arr[i]的插入位置。折半插入排序方法只能在順序表存儲(chǔ)結(jié)構(gòu)

27、實(shí)現(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--)//向后移動(dòng)</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個(gè)數(shù)據(jù)元素。首先對(duì)排序表中第一，二個(gè)數(shù)據(jù)元素的關(guān)鍵字arr[0]和arr[1]進(jìn)行比較。如果前者大于后者，則進(jìn)行交換；然后對(duì)第二，三個(gè)數(shù)據(jù)做同樣的處理；重復(fù)此過(guò)程直到處理完最后兩個(gè)相鄰的數(shù)據(jù)元素。我們稱之為一趟冒泡，它將關(guān)鍵字最大的元素移到排序表的最后一個(gè)位置，其他數(shù)據(jù)元素一般也都向排序的最終位置移動(dòng)。然后進(jìn)行第二趟排序，對(duì)排序表中前n-1個(gè)元素進(jìn)行與上述同樣的操作，其結(jié)果使整個(gè)排序表中關(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表示還沒(méi)有排好序</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ā)生了交換，說(shuō)明還沒(méi)有排好序</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>簡(jiǎn)單選擇排序（直接選擇排序）</p><p>　　直接選擇排序的算法基本

40、思想是：</p><p>　　a)開(kāi)始時(shí)設(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ù)元素中的第一個(gè)數(shù)據(jù)元素（i≠k），則將arr[k]與arr[i]這兩數(shù)據(jù)元素的位置對(duì)調(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()//簡(jiǎn)單選擇排序</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>　　其算法基本思想是：任取排序表中的某個(gè)數(shù)據(jù)元素(例如取第一個(gè)數(shù)據(jù)元素)作為基準(zhǔn)，按照該數(shù)據(jù)元素的關(guān)鍵字大小，將整個(gè)排序表劃分為左右兩個(gè)子表： 左側(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ù)元素則排在這兩個(gè)子表中間(這也是該數(shù)據(jù)元素最終應(yīng)安放的位置)，然后分別對(duì)這兩個(gè)子表重復(fù)施行上述方法的快速排序，直到所有的子表長(zhǎng)度為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]上，遞歸地進(jìn)行快速排序</p><p><b>　　{</b></p><p>　　int i=low,j=high;</p><p>　　type temp=arr[low];//取區(qū)間第一個(gè)位置為基準(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ū)間遞歸進(jìn)行快速排序</p><p>　　quicksort(i+1,high);//在右子區(qū)間遞歸進(jìn)行快速排序</p>

53、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　<7>堆排序（包括建立最大堆和堆排序兩個(gè)過(guò)程）</p><p>　　堆排序算法的基本思想是：</p><p>　　a.對(duì)排序表中的數(shù)據(jù)元素，利用堆的調(diào)整算法形成初始堆。</p&g

54、t;<p><b>　　b.輸出堆頂元素。</b></p><p>　　c.對(duì)剩余元素重新調(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開(kāi)始到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++;//在兩個(gè)孩子中選關(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>　　如果建立的堆滿足最大堆的條件，則堆的第一個(gè)數(shù)據(jù)元素arr[0]具有最大的關(guān)鍵字，將arr[0]與a

59、rr[n-1]對(duì)調(diào)，把具有最大關(guān)鍵字的數(shù)據(jù)元素交換到最后，再對(duì)前面的n-1個(gè)數(shù)據(jù)元素使用堆的調(diào)整算法，重新建立最大堆，結(jié)果把具有次最大關(guān)鍵字的數(shù)據(jù)元素又上浮到堆頂，即arr[0]的位置，再對(duì)調(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、元素和最后一個(gè)元素交換</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è)有兩個(gè)有序表A和B

65、，其數(shù)據(jù)元素個(gè)數(shù)（表長(zhǎng)）分別為n和m，變量i和j分別是表A和表B的當(dāng)前檢測(cè)指針；設(shè)表C是歸并后的新有序表，變量k是它的當(dāng)前存放指針。開(kāi)始時(shí)i、j、k都分別指向A、B、C三個(gè)表的起始位置；然后根據(jù)A[i]與B[j]的關(guān)鍵字的大小，把關(guān)鍵字小的數(shù)據(jù)元素放到新表C[k]中；且相應(yīng)的檢測(cè)指針（i或j）和存放指針k增加1.如此循環(huán)，當(dāng)i與j中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表C[k]~C[m+n]中。</p>&

66、lt;p>　　下面的歸并算法中，兩個(gè)待歸并的有序表首尾相接存放在數(shù)組sourcetable.arr[]中，其中第一個(gè)表的下標(biāo)范圍從left到mid，另一個(gè)表的下標(biāo)范圍從mid+1到right。前一個(gè)表中有mid-left+1個(gè)數(shù)據(jù)元素，后一個(gè)表中有right –mid個(gè)數(shù)據(jù)元素。歸并后得到的新有序表有right –mid個(gè)數(shù)據(jù)元素。歸并后得到的新有序表存放在另一個(gè)輔助數(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個(gè)數(shù)據(jù)元素已經(jīng)分為一些長(zhǎng)度為len的歸并項(xiàng)，將這些歸并項(xiàng)兩兩歸并，歸并成一些長(zhǎng)度為2len的歸并項(xiàng)，結(jié)果放到mergedtable.arr[]中。如果n不是2len的整數(shù)倍，

73、則一趟歸并到最后，可能遇到兩種情況：</p><p>　　剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和一個(gè)長(zhǎng)度不足len的歸并項(xiàng)，可用一次merge算法，將它們歸并成一個(gè)長(zhǎng)度小于2len的歸并項(xiàng)。</p><p>　　只剩下一個(gè)歸并項(xiàng)，其長(zhǎng)度小于或等于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)//表示至少有個(gè)子序列</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)//若只有最后兩個(gè)子序列</p><p>　　merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);</p><p>　　else//若只有最后一個(gè)子序列</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ǔ)上，實(shí)現(xiàn)兩路歸并排序算法。在兩路歸并排序算法中，初始排序表存放在數(shù)組table.arr[]中,第一趟歸并將table.arr[]中的歸并項(xiàng)兩兩歸并，結(jié)果存放在輔助數(shù)組temptable.arr[]中。第二趟將temptable.arr[]中的歸并項(xiàng)兩兩歸并，結(jié)果放回原數(shù)組table.arr[]中，如此反復(fù)進(jìn)行。為了將最后歸并結(jié)果仍放在數(shù)組table.arr[]中，歸并趟數(shù)應(yīng)為偶數(shù)

82、。如果做奇數(shù)趟就能完成時(shí)，最后還需要執(zhí)行一次一趟歸并過(guò)程，由于這時(shí)的歸并項(xiàng)長(zhǎng)度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ù)元素進(jìn)行遞歸排序</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、主菜單，以及對(duì)各種排序的調(diào)用</p><p><b>　　偽代碼如下：</b></p><p><b>　　三 上機(jī)結(jié)果及體會(huì)</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.簡(jiǎn)單選擇排序 7.堆排序

92、 0.退出排序程序 "<<endl;</p><p>　　cout<<" "<<endl; </p><p>　　cout<&

93、lt;"*******************************************************************************"<<endl;</p><p>　　cout<<"\n請(qǐng)選擇所需排序法：";</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請(qǐng)輸入排序的數(shù)的

96、個(gè)數(shù)：";</p><p><b>　　cin>>n;</b></p><p>　　cout<<"\n請(qǐng)輸入"<<n<<"個(gè)數(shù)：";</p><p>　　sortlist<int>table(n);</p><p&g

97、t;　　for(int i=0;i<n;i++)//輸入n個(gè)數(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 ======直接插入排序法過(guò)程演示======\n"<<endl;</p><p>　　ti

99、mestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　Sleep(1000);</p><p>　　table.zhicha();</p><p>　　timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms)

100、 </p><p>　　timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p>　　cout<<"直接插入排序用時(shí)為:"<<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 ======冒泡排序法過(guò)程演示======\n"<<endl;</p><p>　　timestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　Sleep(1000);</p><

103、p>　　table.maopao();</p><p>　　timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK;

104、 </p><p>　　cout<<"冒泡排序用時(shí)為:"<<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 ======快速排序法過(guò)程演示======\n"<<endl;</p><p>　　timestart=GetTickC

106、ount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　Sleep(1000);</p><p>　　table.kuaisu(0,n-1);</p><p>　　timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p>

107、<p>　　timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK;</p><p>　　cout<<"快速排序用時(shí)為:"<<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 ======歸并排序法過(guò)程演示====

109、==\n"<<endl;</p><p>　　timestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　Sleep(1000);</p><p>　　table.mergesort(table);</p><p>　　timeen

110、d=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p>　　cout<<&

111、quot;歸并排序用時(shí)為:"<<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 ======折半插入排序法過(guò)程演示======\n"<<endl;</p><p>　　timestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p

113、><p>　　Sleep(1000);</p><p>　　table.binaryinsertsort();</p><p>　　timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　timeused=timeend

114、-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p>　　cout<<"折半插入排序用時(shí)為:"<<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 ======簡(jiǎn)單選擇排序法過(guò)程演示======\

116、n"<<endl;</p><p>　　timestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　Sleep(1000);</p><p>　　table.selectsort();</p><p>　　timeend=GetTi

117、ckCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　timeused=timeend-timestart;//(double)(timeend-timestart)/CLK_TCK; </p><p>　　cout<<"簡(jiǎn)

118、單選擇排序用時(shí)為:"<<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 ======堆排序法過(guò)程演示======\n"<<endl;</p><p>　　timestart=GetTickCount();//(double)clock();//程序段開(kāi)始前取得系統(tǒng)運(yùn)行時(shí)間(ms) </p&g

120、t;<p>　　Sleep(1000);</p><p>　　table.heapsort();</p><p>　　timeend=GetTickCount();//(double)clock();//程序段結(jié)束后取得系統(tǒng)運(yùn)行時(shí)間(ms) </p><p>　　timeused=timeend-timestar

121、t;//(double)(timeend-timestart)/CLK_TCK; </p><p>　　cout<<"堆排序用時(shí)為:"<<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運(yùn)行情況</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>　　簡(jiǎn)單選擇排序</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ù)元素的個(gè)數(shù)</p><p><b>　　public:</b></p><p>　　type *arr;//存儲(chǔ)數(shù)據(jù)元素的向量（排序表）</p><p>　　sortlist():m

129、omentsize(0)//無(wú)參的構(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();//簡(jiǎn)單選擇排序</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