版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p> —幾種排序算法的演示</p><p> 時(shí)間:2010-1-14</p><p><b> 一 需求分析</b></p><p><b> 運(yùn)行環(huán)境</b></p><p> Microsoft Visu
2、al Studio 2005</p><p><b> 程序所實(shí)現(xiàn)的功能</b></p><p> 對(duì)直接插入排序、折半插入排序、冒泡排序、簡(jiǎn)單選擇排序、快速排序、堆排序、歸并排序算法的演示,并且輸出每一趟的排序情況。</p><p> 程序的輸入(包含輸入的數(shù)據(jù)格式和說明)</p><p> <1>
3、排序種類三輸入</p><p> <2>排序數(shù)的個(gè)數(shù)的輸入</p><p> <3>所需排序的所有數(shù)的輸入 </p><p> 程序的輸出(程序輸出的形式)</p><p><b> <1>主菜單的輸出</b></p><p> <2>每一
4、趟排序的輸出,即排序過程的輸出</p><p><b> 二 設(shè)計(jì)說明</b></p><p><b> 算法設(shè)計(jì)思想</b></p><p> <1>交換排序(冒泡排序、快速排序)</p><p> 交換排序的基本思想是:對(duì)排序表中的數(shù)據(jù)元素按關(guān)鍵字進(jìn)行兩兩比較,如果發(fā)生逆序(
5、即排列順序與排序后的次序正好相反),則兩者交換位置,直到所有數(shù)據(jù)元素都排好序?yàn)橹埂?lt;/p><p> <2>插入排序(直接插入排序、折半插入排序)</p><p> 插入排序的基本思想是:每一次設(shè)法把一個(gè)數(shù)據(jù)元素插入到已經(jīng)排序的部分序列的合適位置,使得插入后的序列仍然是有序的。開始時(shí)建立一個(gè)初始的有序序列,它只包含一個(gè)數(shù)據(jù)元素。然后,從這個(gè)初始序列出發(fā)不斷插入數(shù)據(jù)元素,直到
6、最后一個(gè)數(shù)據(jù)元素插到有序序列后,整個(gè)排序工作就完成了。</p><p> <3>選擇排序(簡(jiǎn)單選擇排序、堆排序)</p><p> 選擇排序的基本思想是:第一趟在有n個(gè)數(shù)據(jù)元素的排序表中選出關(guān)鍵字最小的數(shù)據(jù)元素,然后在剩下的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ù)
7、據(jù)元素中選出關(guān)鍵字最小的數(shù)據(jù)元素,作為有序數(shù)據(jù)元素序列的第i個(gè)數(shù)據(jù)元素。等到第n-1趟選擇結(jié)束,待排序數(shù)據(jù)元素僅剩下一個(gè)時(shí)就不用再選了,按選出的先后次序所得到的數(shù)據(jù)元素序列即為有序序列,排序即告完成。</p><p> <4>歸并排序(兩路歸并排序)</p><p> 兩路歸并排序的基本思想是:假設(shè)初始排序表有n個(gè)數(shù)據(jù)元素,首先把它看成是長(zhǎng)度為1的首尾相接的n個(gè)有序子表(以
8、后稱它們?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><b> 程序的主要流程圖</b></p><p> 程序的主要模塊(要求對(duì)主要流程圖中出現(xiàn)的模塊進(jìn)行說明)</p><p> 程序的主要模塊主要分
9、為主菜單模塊和排序算法演示模塊。</p><p><b> <1>主菜單</b></p><p> 主要功能:程序運(yùn)行時(shí),可使運(yùn)行者根據(jù)提醒輸入相關(guān)操作,從而進(jìn)入不同的排序方法或者退出。</p><p> <2>排序方法及輸出</p><p> 根據(jù)運(yùn)行者對(duì)排序的不同選擇,進(jìn)入排序過程&l
10、t;/p><p> a.直接插入排序:根據(jù)直接排序的算法,輸出排序過程</p><p> b.折半插入排序:根據(jù)折半插入的算法,輸出排序過程</p><p> c.冒泡排序:根據(jù)冒泡排序算法,輸出排序過程</p><p> d.簡(jiǎn)單選擇排序:根據(jù)簡(jiǎn)單選擇排序的算法,輸出排序過程</p><p> e.快速排序:根
11、據(jù)快速排序的算法,輸出排序過程</p><p> f.堆排序:根據(jù)堆排序的算法,輸出排序過程</p><p> g.歸并排序:根據(jù)歸并排序的算法,輸出排序過程</p><p> 程序的主要函數(shù)及其偽代碼說明</p><p><b> <1>模板類</b></p><p> 主
12、要說明程序中用到的類的定義</p><p> template<class type>class sortlist</p><p><b> {</b></p><p><b> private:</b></p><p> int currentsize;//數(shù)據(jù)表中數(shù)據(jù)元素的個(gè)
13、數(shù)</p><p><b> public:</b></p><p> type *arr;//存儲(chǔ)數(shù)據(jù)元素的向量(排序表)</p><p> sortlist():currentsize(0){arr=new type[maxsize];}//構(gòu)造函數(shù)</p><p> sortlist(int n){arr=
14、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><p> void swap(type &x,type &y)//數(shù)據(jù)元素x和y交換位置<
15、;/p><p> {type temp=x;x=y;y=temp;}</p><p> void bubblesort();//冒泡排序</p><p> void quicksort(int low,int high);//快速排序</p><p> void insertionsort();//直接插入排序</p>&l
16、t;p> void binaryinsertsort();//折半插入排序</p><p> void selectsort();//簡(jiǎn)單選擇排序</p><p> void heapsort();//堆排序</p><p> void mergesort(sortlist<type> &table);//歸并排序</p>
17、;<p> void filterdown(const int start);//建立最大堆</p><p> void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);//一趟歸并</p><p> void merge
18、(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);//兩路歸并算法</p><p><b> };</b></p><p><b> <2>直接插入排序
19、</b></p><p> 直接插入排序的基本思想:開始時(shí)把第一個(gè)數(shù)據(jù)元素作為初始的有序序列,然后從第二個(gè)數(shù)據(jù)元素開始依次把數(shù)據(jù)元素按關(guān)鍵字大小插入到已排序的部分排序表的適當(dāng)位置。當(dāng)插入第i(1<i<=n)個(gè)數(shù)據(jù)元素時(shí),前面的i-1個(gè)數(shù)據(jù)元素已經(jīng)排好序,這時(shí),用第i個(gè)數(shù)據(jù)元素的關(guān)鍵字與前面的i-1個(gè)數(shù)據(jù)元素的關(guān)鍵字順序進(jìn)行比較,找到插入位置后就將第i個(gè)數(shù)據(jù)元素插入。如此進(jìn)行n-1次插入,
20、就完成了排序。</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-1]的關(guān)鍵字依次與arr[i-2],arr[i-3],…的關(guān)鍵字順序進(jìn)行比較,如果這些數(shù)據(jù)元素的關(guān)鍵字大于arr[i-1]的關(guān)鍵字,
21、則將數(shù)據(jù)元素向后移一個(gè)位置,當(dāng)找到插入位置后就將arr[i-1]插入,就完成了arr[0],arr[1],…,arr[n-1]的排序。</p><p><b> 偽代碼如下</b></p><p> template <class type>//直接插入排序</p><p> void sortlist<type>
22、::insertionsort()</p><p><b> {</b></p><p> type temp;</p><p><b> int j;</b></p><p> for(int i=1;i<=currentsize-1;i++)</p><p>
23、;<b> {</b></p><p> temp=arr[i];j=i-1;</p><p> while(j>=0&&temp<arr[j])</p><p> {arr[j+1]=arr[j];j--;}</p><p> arr[j+1]=temp;</p>&
24、lt;p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> c
25、out<<endl;</p><p><b> }</b></p><p><b> num=0;</b></p><p><b> }</b></p><p><b> <3>折半插入排序</b></p>&
26、lt;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)實(shí)現(xiàn)。</p><p><b> 偽代碼如下:</b></p><
27、;p> template <class type>//折半插入排序</p><p> void sortlist<type>::binaryinsertsort()</p><p><b> {</b></p><p> type temp;</p><p> int left,r
28、ight;</p><p> for(int i=1;i<currentsize;i++)</p><p><b> { </b></p><p> left=0;right=i-1;temp=arr[i];</p><p> while(left<=right)//找插入位置</p>
29、<p><b> {</b></p><p> int mid=(left+right)/2;</p><p> if(temp<arr[mid])right=mid-1;</p><p> else left=mid+1;</p><p><b> }</b></p
30、><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> cout<<"第"<<++num<<"趟排序結(jié)果為:";&l
31、t;/p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><b> }</b></p><p&g
32、t;<b> num=0;</b></p><p><b> }</b></p><p><b> <4>冒泡排序</b></p><p> 冒泡排序的基本思想是:設(shè)排序表中有n個(gè)數(shù)據(jù)元素。首先對(duì)排序表中第一,二個(gè)數(shù)據(jù)元素的關(guān)鍵字arr[0]和arr[1]進(jìn)行比較。如果前者大于后者
33、,則進(jìn)行交換;然后對(duì)第二,三個(gè)數(shù)據(jù)做同樣的處理;重復(fù)此過程直到處理完最后兩個(gè)相鄰的數(shù)據(jù)元素。我們稱之為一趟冒泡,它將關(guān)鍵字最大的元素移到排序表的最后一個(gè)位置,其他數(shù)據(jù)元素一般也都向排序的最終位置移動(dòng)。然后進(jìn)行第二趟排序,對(duì)排序表中前n-1個(gè)元素進(jìn)行與上述同樣的操作,其結(jié)果使整個(gè)排序表中關(guān)鍵字次大的數(shù)據(jù)元素被移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有數(shù)據(jù)元素排好序。</p><p><b&g
34、t; 偽代碼如下:</b></p><p> template <class type>//冒泡排序</p><p> void sortlist<type>:: bubblesort()</p><p><b> {</b></p><p><b> int i=
35、1;</b></p><p> int finish=0;//0表示還沒有排好序</p><p> while(i<currentsize &&!finish)</p><p><b> {</b></p><p> finish=1;//排序結(jié)束標(biāo)志置為,假定已經(jīng)排好序<
36、/p><p> for(int j=0;j<currentsize-i;j++)</p><p> if(arr[j]>arr[j+1])//逆序</p><p><b> {</b></p><p> swap(arr[j],arr[j+1]);//相鄰元素交換位置</p><p&g
37、t;<b> finish=0;</b></p><p> }//排序結(jié)束標(biāo)志置為,表示本趟發(fā)生了交換,說明還沒有排好序</p><p><b> i++;</b></p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";
38、</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><b> }</b></p><p
39、><b> num=0;</b></p><p><b> }</b></p><p> <5>簡(jiǎn)單選擇排序(直接選擇排序)</p><p> 直接選擇排序的算法基本思想是:</p><p> a)開始時(shí)設(shè)i的初始值為0。</p><p> b)
40、如果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><p> d)令i=i+1轉(zhuǎn)步驟 b)。</p><p><b> 偽代碼如下:
41、</b></p><p> template <class type></p><p> void sortlist<type>::selectsort()//簡(jiǎn)單選擇排序</p><p><b> {</b></p><p><b> int k;</b>
42、;</p><p> for(int i=0;i<=currentsize-1;i++)</p><p><b> {</b></p><p><b> k=i;</b></p><p> for(int j=i+1;j<currentsize;j++)</p>&
43、lt;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[i],arr[k]);</p><p> cout<<"第"<&l
44、t;++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><
45、b> }</b></p><p><b> num=0;</b></p><p><b> }</b></p><p><b> <6>快速排序</b></p><p> 快速排序(Quick Sort)又被稱做分區(qū)交換排序,這是一種平均
46、性能非常好的排序方法。</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)鍵字都大于或等于基準(zhǔn)數(shù)據(jù)元素的關(guān)鍵字,基準(zhǔn)數(shù)據(jù)元素則排在這兩個(gè)子表中間(這也是該數(shù)據(jù)元素最終應(yīng)安放的位置),然后分別對(duì)這兩個(gè)子表重復(fù)施行上述方法的快
47、速排序,直到所有的子表長(zhǎng)度為1,則排序結(jié)束。</p><p><b> 偽代碼如下:</b></p><p> template <class type>//快速排序</p><p> void sortlist<type>::quicksort(int low,int high)//在待排序區(qū)間[low,high
48、]上,遞歸地進(jìn)行快速排序</p><p><b> {</b></p><p> int i=low,j=high;</p><p> type temp=arr[low];//取區(qū)間第一個(gè)位置為基準(zhǔn)位置</p><p><b> if(i<j)</b></p><
49、p><b> {</b></p><p> while(i<j)</p><p><b> {</b></p><p> while(i<j&&temp<arr[j])j--;</p><p> if(i<j){swap(arr[i],arr[
50、j]);i++;}</p><p> while(i<j&&temp>=arr[i])i++;</p><p> if(i<j){swap(arr[i],arr[j]);j--;}</p><p><b> }</b></p><p> arr[i]=temp;//將基準(zhǔn)元素就
51、位</p><p> cout<<"第"<<++x<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p>
52、<p> cout<<endl;</p><p> quicksort(low,i-1);//在左子區(qū)間遞歸進(jìn)行快速排序</p><p> quicksort(i+1,high);//在右子區(qū)間遞歸進(jìn)行快速排序</p><p><b> }</b></p><p><b> }&
53、lt;/b></p><p> <7>堆排序(包括建立最大堆和堆排序兩個(gè)過程)</p><p> 堆排序算法的基本思想是:</p><p> a.對(duì)排序表中的數(shù)據(jù)元素,利用堆的調(diào)整算法形成初始堆。</p><p><b> b.輸出堆頂元素。</b></p><p>
54、c.對(duì)剩余元素重新調(diào)整形成堆。</p><p> d.重復(fù)執(zhí)行第b、c步,直到所有數(shù)據(jù)元素被輸出。</p><p> (1)建立最大堆的偽代碼如下:</p><p> template <class type>//建立最大堆</p><p> void sortlist<type>::filterdown(co
55、nst int start)</p><p> {//向下調(diào)整使從start開始到currentsize-1為止的子表成為最大堆</p><p> int i=start,j=2*i+1;//j為i的左孩子</p><p> int tablesize=currentsize;</p><p> type temp=arr[i];&l
56、t;/p><p> while(j<=currentsize-1)</p><p><b> {</b></p><p> if(j<currentsize-1 && arr[j]<arr[j+1])</p><p> j++;//在兩個(gè)孩子中選關(guān)鍵字較大者</p>&
57、lt;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><b> }</b></p><p> arr[i]=temp;</p>
58、<p><b> }</b></p><p><b> (2)堆排序</b></p><p> 如果建立的堆滿足最大堆的條件,則堆的第一個(gè)數(shù)據(jù)元素arr[0]具有最大的關(guān)鍵字,將arr[0]與arr[n-1]對(duì)調(diào),把具有最大關(guān)鍵字的數(shù)據(jù)元素交換到最后,再對(duì)前面的n-1個(gè)數(shù)據(jù)元素使用堆的調(diào)整算法,重新建立最大堆,結(jié)果把具有次最大
59、關(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> template <class type>//堆排序</p><p> void sortlist<ty
60、pe>::heapsort()</p><p><b> {</b></p><p> int tablesize=currentsize;</p><p> for(int i=(currentsize-2)/2;i>=0;i--)</p><p> filterdown(i); //
61、初始建堆</p><p> for(int i=currentsize-1;i>=1;i--)</p><p><b> {</b></p><p> swap(arr[0],arr[i]);//堆頂元素和最后一個(gè)元素交換</p><p> currentsize--;</p><p&g
62、t; filterdown(0);//重建最大堆</p><p> cout<<"第"<<++num<<"趟排序結(jié)果為:";</p><p> for(int t=0;t<tablesize;t++)</p><p> cout<<arr[t]<<&qu
63、ot; ";</p><p> cout<<endl;</p><p><b> }</b></p><p><b> num=0;</b></p><p> currentsize=tablesize;</p><p><b>
64、}</b></p><p> <8>歸并排序(包括歸并算法,一趟歸并算法和歸并排序)</p><p><b> 歸并算法</b></p><p> 其基本思想是:設(shè)有兩個(gè)有序表A和B,其數(shù)據(jù)元素個(gè)數(shù)(表長(zhǎng))分別為n和m,變量i和j分別是表A和表B的當(dāng)前檢測(cè)指針;設(shè)表C是歸并后的新有序表,變量k是它的當(dāng)前存放指針。開
65、始時(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><p> 下面的歸并算法中,兩個(gè)待歸并的有序表首尾相接存放在數(shù)組sourcetable.arr[]中,其中第一個(gè)表的下標(biāo)范圍
66、從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到right。</p><p><b> 偽代碼如下:</b></p>&
67、lt;p> template <class type></p><p> void sortlist<type>::merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right)</p&g
68、t;<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)前位置</p><p> while(i<=mid&&j<=right)</p&
69、gt;<p> if(sourcetable.arr[i]<=sourcetable.arr[j])</p><p> {mergedtable.arr[k]=sourcetable.arr[i];i++;k++;}</p><p> else{mergedtable.arr[k]=sourcetable.arr[j];j++;k++;}</p>&
70、lt;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ù)制到mergedtable</p><p><b> else</b></p>&
71、lt;p> for(int p=k,q=j;q<=right;p++,q++)</p><p> mergedtable.arr[p]=sourcetable.arr[q];//把后一段復(fù)制到mergedtable</p><p><b> }</b></p><p><b> 一趟歸并算法</b>&l
72、t;/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ù)倍,則一趟歸并到最后,可能遇到兩種情況:</p><p> 剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和一個(gè)長(zhǎng)度不足len的歸
73、并項(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></p><p> template <class type></p>&
74、lt;p> template <class type></p><p> void sortlist<type>::mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len)</p><p><b> {&l
75、t;/b></p><p><b> int i=0;</b></p><p> while(i+2*len<=currentsize-1)//表示至少有個(gè)子序列</p><p><b> {</b></p><p> merge(sourcetable,mergedtable,
76、i,i+len-1,i+2*len-1);</p><p><b> i+=2*len;</b></p><p><b> }</b></p><p> if(i+len<=currentsize-1)//若只有最后兩個(gè)子序列</p><p> merge(sourcetable,me
77、rgedtable,i,i+len-1,currentsize-1);</p><p> else//若只有最后一個(gè)子序列</p><p> for(int j=i;j<=currentsize-1;j++)</p><p> mergedtable.arr[j]=sourcetable.arr[j];</p><p> if(
78、len<=currentsize-1)</p><p><b> {</b></p><p> if(num<currentsize)</p><p><b> {</b></p><p> cout<<"第"<<++num<&l
79、t;"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<mergedtable.arr[t]<<" ";</p><p> cout<<endl;</p><p><b
80、> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> 歸并排序</b></p><p> 在一趟歸并算法的基礎(chǔ)上,實(shí)現(xiàn)兩路歸并排序算法。在兩路歸并排序算法中,初始排序表存放在數(shù)組tabl
81、e.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ù)。如果做奇數(shù)趟就能完成時(shí),最后還需要執(zhí)行一次一趟歸并過程,由于這時(shí)的歸并項(xiàng)長(zhǎng)度len>=n,因此在則趟歸并中while循環(huán)不執(zhí)行
82、,只做把temptable.arr[]中的數(shù)據(jù)元素復(fù)制到table.arr[]的工作。</p><p><b> 偽代碼如下:</b></p><p> template <class type></p><p> void sortlist<type>::mergesort(sortlist<type>
83、; &table )</p><p> {//按數(shù)據(jù)元素關(guān)鍵字非遞減的順序?qū)ε判虮韙able中數(shù)據(jù)元素進(jìn)行遞歸排序</p><p> sortlist<type> temptable;</p><p> int len=1;</p><p> while(len<currentsize)</p>
84、<p><b> {</b></p><p> mergepass(table,temptable,len);len*=2;</p><p> mergepass(temptable,table,len);len*=2;</p><p><b> }</b></p><p>&l
85、t;b> num=0;</b></p><p><b> } </b></p><p><b> <9>主函數(shù)</b></p><p> 主要功能是顯示主菜單,以及對(duì)各種排序的調(diào)用</p><p><b> 偽代碼如下:</b>
86、</p><p> int main()//主函數(shù)</p><p><b> { </b></p><p> cout<<" ***********************************************************************"<<endl;<
87、/p><p> cout<<" 排序問題 "<<endl;</p><p> cout<<"*********************************************************************
88、**"<<endl<<endl<<endl;</p><p><b> int c=1; </b></p><p><b> char ch;</b></p><p><b> int n1=0;</b></p><p>
89、 while(c!=0)</p><p><b> {</b></p><p> cout<<"\======================================================================"<<endl;</p><p> cout<<
90、;"===================可供選擇的排序方法==========================="<<endl;</p><p> cout<<" 1 直接插入排序 2 折半插入排序 "<<endl;</p><p> cout&l
91、t;<" 3 冒泡排序 4 簡(jiǎn)單選擇排序 "<<endl;</p><p> cout<<" 5 快速排序 6 堆排序 "<<endl;</p><p>
92、 cout<<" 7 歸并排序 0 退出排序程序 "<<endl; </p><p> cout<<" ======================================================================="<<
93、;endl;</p><p> cout<<"\n 請(qǐng)輸入您需要的排序種類:";</p><p><b> cin>>ch;</b></p><p> if(ch=='0') {cout<<" 您已成功退出該系統(tǒng)!"<<endl
94、;system("pause"); return 0;}</p><p> int n,number;</p><p> if(ch>='0'&&ch<='7')</p><p><b> {</b></p><p> cout&l
95、t;<"\n 輸入您要進(jìn)行排序的數(shù)的個(gè)數(shù):";</p><p><b> cin>>n;</b></p><p> cout<<"\n 請(qǐng)輸入"<<n<<"個(gè)數(shù):";</p><p> sortlist<int&
96、gt;table(n);</p><p> for(int i=0;i<n;i++)</p><p> {cin>>number;table.insert(i,number);}</p><p> switch(ch)</p><p><b> { </b></p><p&g
97、t;<b> case '1':</b></p><p> cout<<"\n *******您選擇的是直接插入排序*******\n"<<endl;</p><p> table.insertionsort();</p><p><b> break;</
98、b></p><p> system("pause");</p><p><b> break;</b></p><p><b> case '2':</b></p><p> cout<<"\n *******您選擇的是折
99、半插入排序*******\n"<<endl;</p><p> table.binaryinsertsort();</p><p><b> break;</b></p><p> system("pause");</p><p><b> break;<
100、/b></p><p><b> case '3':</b></p><p> cout<<"\n *******您選擇的是冒泡排序*******\n"<<endl;</p><p> table.bubblesort();</p><p>&l
101、t;b> break;</b></p><p> system("pause");</p><p><b> break;</b></p><p><b> case '4':</b></p><p> cout<<&quo
102、t;\n *******您選擇的是簡(jiǎn)單選擇排序*******\n"<<endl;</p><p> table.selectsort();</p><p><b> break;</b></p><p> system("pause");</p><p><b&g
103、t; break;</b></p><p><b> case '5':</b></p><p> cout<<"\n *******您選擇的是快速排序*******\n"<<endl;</p><p> table.quicksort(0,n-1);</
104、p><p><b> break;</b></p><p> system("pause");</p><p><b> break;</b></p><p><b> case '6':</b></p><p>
105、 cout<<"\n *******您選擇的是堆排序*******\n"<<endl;</p><p> table.heapsort();</p><p><b> break;</b></p><p> system("pause");</p><
106、;p><b> break;</b></p><p><b> case '7':</b></p><p> cout<<"\n *******您選擇的是歸并排序*******\n"<<endl;</p><p> table.mergesort
107、(table);</p><p><b> break;</b></p><p> system("pause");</p><p><b> break; </b></p><p><b> }</b></p><p>&l
108、t;b> }</b></p><p><b> }</b></p><p> system("pause");</p><p><b> return 0;</b></p><p><b> }</b></p>&l
109、t;p><b> 三 上機(jī)結(jié)果及體會(huì)</b></p><p><b> 實(shí)際完成的情況說明</b></p><p> 此程序主要實(shí)現(xiàn)了對(duì)不同排序算法的演示,并給出了每一趟的變化情況</p><p><b> 程序的性能分析</b></p><p> 直接插入排序
110、(穩(wěn)定的排序方法)</p><p><b> 1時(shí)間復(fù)雜度</b></p><p> 若待排序記錄按關(guān)鍵字從小到大排列(正序)</p><p><b> 關(guān)鍵字比較次數(shù):</b></p><p> 記錄移動(dòng)次數(shù):2(n-1)</p><p> b)若待排序記錄按關(guān)鍵
111、字從大到小排列(逆序)</p><p><b> 關(guān)鍵字比較次數(shù):</b></p><p><b> 記錄移動(dòng)次數(shù):</b></p><p> c) 若待排序記錄是隨機(jī)的,取最好和最壞情況的平均值</p><p> 關(guān)鍵字比較次數(shù)(約為):</p><p> 記錄移
112、動(dòng)次數(shù)(約為):</p><p> 2空間復(fù)雜度:S(n)=O(1)</p><p> 折半插入排序(穩(wěn)定的排序算法)</p><p> 就平均性能而言,因?yàn)檎郯氩檎覂?yōu)于順序查找,所以折半插入排序也優(yōu)于直接插入排序。</p><p> 關(guān)鍵字的比較次數(shù)為:n*log2(n)</p><p> 冒泡排序(穩(wěn)定的
113、排序算法)</p><p><b> 時(shí)間復(fù)雜度:</b></p><p><b> 最好情況(正序)</b></p><p> 比較次數(shù):n-1(只要進(jìn)行一趟即可)</p><p><b> 移動(dòng)次數(shù):0</b></p><p><b&g
114、t; 最壞情況(逆序)</b></p><p> 比較次數(shù):(需n-1趟,每趟達(dá)到最大比較次數(shù)) </p><p><b> 移動(dòng)次數(shù):</b></p><p> 在最壞情況下,時(shí)間復(fù)雜度為:T(n)=O(n²)</p><p> 空間復(fù)雜度:S(n)=O(1)</p>&l
115、t;p> 簡(jiǎn)單選擇排序(不穩(wěn)定的排序方法)</p><p> 時(shí)間復(fù)雜度:O(n2)。</p><p> 空間復(fù)雜度:S(1)。</p><p> e. 快速排序(不穩(wěn)定的排序方法)</p><p><b> 1.時(shí)間復(fù)雜度</b></p><p> 最好情況(每次總是選到中間值
116、作樞軸)T(n)=O(nlog2n)</p><p> 最壞情況(每次總是選到最小或最大元素作樞軸)T(n)=O(n²) </p><p> 2.空間復(fù)雜度:需??臻g以實(shí)現(xiàn)遞歸</p><p> 最壞情況:S(n)=O(n)</p><p> 一般情況:S(n)=O(log2n)</p><p>
117、f. 堆排序(不穩(wěn)定的排序方法)]</p><p> 1.間復(fù)雜性為O(nlog2n)。</p><p> 2空間復(fù)雜性為O(1)。</p><p> g. 歸并排序(穩(wěn)定的排序方法)</p><p> 1時(shí)間復(fù)雜度為O(nlog2n)。</p><p> 2空間復(fù)雜度為O(n)。</p>&l
118、t;p><b> 3)運(yùn)行情況</b></p><p><b> 主菜單</b></p><p><b> 直接插入排序</b></p><p><b> 折半插入排序</b></p><p><b> 冒泡排序</b>
119、;</p><p><b> 簡(jiǎn)單選擇排序</b></p><p><b> 快速排序</b></p><p><b> 堆排序</b></p><p><b> 歸并排序</b></p><p><b> 退出
120、系統(tǒng)</b></p><p> 上機(jī)過程中出現(xiàn)的問題及其解決方案</p><p> 1 快速排序時(shí)出現(xiàn)多一次排序的情況 解決方法:在進(jìn)行循環(huán)體時(shí),多運(yùn)行了一次,將運(yùn)行次序減1即可。</p><p> 2 堆排序時(shí)也出現(xiàn)與上一條相同的情況 解決方法:由于缺少一個(gè)判斷語句導(dǎo)致輸出只能是偶數(shù)倍趟數(shù),因此加一條if(len<=currentsize-
121、1)判斷語句就可以使程序正常輸出結(jié)果</p><p> 3 快速排序趟數(shù)開始為1 ,2 ,1, 2出現(xiàn) 解決方法:再定義一個(gè)全局變量,不過當(dāng)其用完時(shí),沒有將它重新置為0,這樣最后輸出的趟數(shù)就正確了。</p><p> 4 運(yùn)行程序時(shí),若輸入字符,則必須輸入完全后,才判斷其為不正確的選擇 解決方法:加一個(gè)if判斷語句即可</p><p> 程序中可以改進(jìn)的地方說
122、明</p><p> 本程序不能判斷字符數(shù)大于1的字符串,這方面需要改進(jìn)</p><p> 可以在程序中加入性能分析,例如空間復(fù)雜度,時(shí)間復(fù)雜度等</p><p> 程序中可以擴(kuò)充的功能及其設(shè)計(jì)實(shí)現(xiàn)假想</p><p> 擴(kuò)充功能:可以加入希爾排序等未加入的排序方法,可以加入性能分析</p><p> 實(shí)現(xiàn)假
123、想:加入其他排序方法后,輸出為正確排序的過程,加入性能分析時(shí),輸出排序過程的同時(shí),可以輸出時(shí)間復(fù)雜度與空間復(fù)雜度</p><p><b> 6) 收獲及體會(huì)</b></p><p> 在進(jìn)行為期一個(gè)星期的課程設(shè)計(jì)中,最終完成了算法。這期間,遇到的各種麻煩也都相繼解決。從這次實(shí)踐中,我意識(shí)到自己還有很多不足之處。</p><p> 首先先說
124、一下基本的。對(duì)于各種排序算法的過程還是不夠熟悉,進(jìn)行編程時(shí)還需要翻書查找,對(duì)于這一點(diǎn),只能說對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還不夠扎實(shí),雖然說這門課程以后就沒有了,但是我想這門課對(duì)以后的學(xué)習(xí)會(huì)有很大幫助,所以有空時(shí)還應(yīng)該繼續(xù)熟悉這門課程。</p><p> 其次,就是對(duì)于錯(cuò)誤的處理,不能得心應(yīng)手,不能正確處理一些簡(jiǎn)單的錯(cuò)誤。對(duì)于邏輯上的錯(cuò)誤,不能夠立即找到出錯(cuò)點(diǎn),往往需要向同學(xué)請(qǐng)教才能找出錯(cuò)誤,并且改正。我覺得這是自己獨(dú)自思考
125、能力不高的問題,遇事需要自己仔細(xì)想想,若還不能改正,再請(qǐng)教別人也不遲。</p><p> 從總體上說,整個(gè)代碼的實(shí)現(xiàn)還是存在不足的,例如本程序不能判斷字符數(shù)大于1的字符串,沒有相應(yīng)排序的性能分析(如空間復(fù)雜度,時(shí)間復(fù)雜度),等等。從這點(diǎn)看,說明自己的程序還是不夠完善,不能做到十全十美,希望以后能有所修正。</p><p> 總而言之,從這次的實(shí)踐中我學(xué)到了很多東西,希望以后能夠多加運(yùn)應(yīng)
126、 </p><p><b> 7) 源代碼:</b></p><p> #include "stdafx.h"</p><p> #include<iostream></p><p> using namespace std;</p><p> const
127、 int maxsize=100;</p><p> int num=0;//定義全局變量,為每一趟的輸出做準(zhǔn)備</p><p><b> int x=0;</b></p><p> template<class type>class sortlist</p><p><b> {<
128、/b></p><p><b> private:</b></p><p> int currentsize;//數(shù)據(jù)表中數(shù)據(jù)元素的個(gè)數(shù)</p><p><b> public:</b></p><p> type *arr;//存儲(chǔ)數(shù)據(jù)元素的向量(排序表)</p>&l
129、t;p> sortlist():currentsize(0){arr=new 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>
130、 ~sortlist(){delete []arr;}//析構(gòu)函數(shù)</p><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>
131、 void quicksort(int low,int high);//快速排序</p><p> void insertionsort();//直接插入排序</p><p> void binaryinsertsort();//折半插入排序</p><p> void selectsort();//簡(jiǎn)單選擇排序</p><p>
132、void heapsort();//堆排序</p><p> void mergesort(sortlist<type> &table);//歸并排序</p><p> void filterdown(const int start);//建立最大堆</p><p> void mergepass(sortlist<type>&
133、amp;sourcetable,sortlist<type>&mergedtable,const int len);//一趟歸并</p><p> void merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int
134、 right);//兩路歸并算法</p><p><b> };</b></p><p> template <class type>//直接插入排序</p><p> void sortlist<type>::insertionsort()</p><p><b> {<
135、/b></p><p> type temp;</p><p><b> int j;</b></p><p> for(int i=1;i<=currentsize-1;i++)</p><p><b> {</b></p><p> temp=arr
136、[i];j=i-1;</p><p> while(j>=0&&temp<arr[j])</p><p> {arr[j+1]=arr[j];j--;}</p><p> arr[j+1]=temp;</p><p> cout<<"第"<<++num<&l
137、t;"趟排序結(jié)果為:";</p><p> for(int t=0;t<currentsize;t++)</p><p> cout<<arr[t]<<" ";</p><p> cout<<endl;</p><p><b> }</
138、b></p><p><b> num=0;</b></p><p><b> }</b></p><p> template <class type>//折半插入排序</p><p> void sortlist<type>::binaryinsertsort
139、()</p><p><b> {</b></p><p> type temp;</p><p> int left,right;</p><p> for(int i=1;i<currentsize;i++)</p><p><b> { </b><
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法演示系統(tǒng)
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--內(nèi)部排序演示
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)排序算法演示系統(tǒng)58165
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法比較
- 幾種常見的排序算法的實(shí)現(xiàn)與性能分析數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---數(shù)據(jù)結(jié)構(gòu)相關(guān)算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序算法的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--- 數(shù)據(jù)結(jié)構(gòu)各章算法的演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告---排序算法的實(shí)現(xiàn)與比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--內(nèi)部排序算法的性能分析
- 拓?fù)渑判?算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))
評(píng)論
0/150
提交評(píng)論