1、數據結構課程設計報告 幾種排序算法的演示 時間：2010-1-14一 需求分析運行環境Microsoft Visual Studio 2005程序所實現的功能對直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序算法的演示，并且輸出每一趟的排序情況。程序的輸入（包含輸入的數據格式和說明）<1>排序種類三輸入 <2>排序數的個數的輸入 <3>所需排序的所有數的輸入 程序的輸出（程序輸出的形式）<1>主菜單的輸出 <2>每一趟排序的輸出，即排序過程的輸出二 設計說明算法設計思想<1>交換排序（冒泡排序

2、、快速排序）交換排序的基本思想是：對排序表中的數據元素按關鍵字進行兩兩比較，如果發生逆序（即排列順序與排序后的次序正好相反），則兩者交換位置，直到所有數據元素都排好序為止。 <2>插入排序（直接插入排序、折半插入排序）插入排序的基本思想是：每一次設法把一個數據元素插入到已經排序的部分序列的合適位置，使得插入后的序列仍然是有序的。開始時建立一個初始的有序序列，它只包含一個數據元素。然后，從這個初始序列出發不斷插入數據元素，直到最后一個數據元素插到有序序列后，整個排序工作就完成了。 <3>選擇排序（簡單選擇排序、堆排序）選擇排序的基本思想是：第一趟在有n個數據元素的排序表中

3、選出關鍵字最小的數據元素，然后在剩下的n-1個數據元素中再選出關鍵字最小（整個數據表中次小）的數據元素，依次重復，每一趟（例如第i趟，i=1，n-1）總是在當前剩下的n-i+1個待排序數據元素中選出關鍵字最小的數據元素，作為有序數據元素序列的第i個數據元素。等到第n-1趟選擇結束，待排序數據元素僅剩下一個時就不用再選了，按選出的先后次序所得到的數據元素序列即為有序序列，排序即告完成。 <4>歸并排序（兩路歸并排序）兩路歸并排序的基本思想是：假設初始排序表有n個數據元素，首先把它看成是長度為1的首尾相接的n個有序子表（以后稱它們為歸并項），先做兩兩歸并，得n/2上取整個長度為2的歸并

4、項（如果n為奇數，則最后一個歸并項的長度為1）；再做兩兩歸并，如此重復，最后得到一個長度為n的有序序列。程序的主要流程圖退出系統輸出排序結果開始直插折半冒泡選擇快排堆排歸并選擇排序方法進入主菜單程序的主要模塊(要求對主要流程圖中出現的模塊進行說明)程序的主要模塊主要分為主菜單模塊和排序算法演示模塊。 <1>主菜單主要功能：程序運行時，可使運行者根據提醒輸入相關操作，從而進入不同的排序方法或者退出。 <2>排序方法及輸出 根據運行者對排序的不同選擇，進入排序過程 a.直接插入排序：根據直接排序的算法，輸出排序過程 b.折半插入排序：根據折半插入的算法，輸出排序過程 c.冒

5、泡排序：根據冒泡排序算法，輸出排序過程 d.簡單選擇排序：根據簡單選擇排序的算法，輸出排序過程 e.快速排序：根據快速排序的算法，輸出排序過程 f.堆排序：根據堆排序的算法，輸出排序過程 g.歸并排序：根據歸并排序的算法，輸出排序過程 程序的主要函數及其偽代碼說明 <1>模板類主要說明程序中用到的類的定義template<class type>class sortlistprivate:int currentsize;/數據表中數據元素的個數public:type *arr;/存儲數據元素的向量（排序表）sortlist():currentsize(0)arr=new

6、typemaxsize;/構造函數sortlist(int n)arr=new typemaxsize;currentsize=n;void insert(int i,type x)arri=x;sortlist()delete arr;/析構函數void swap(type &x,type &y)/數據元素x和y交換位置type temp=x;x=y;y=temp; void bubblesort();/冒泡排序 void quicksort(int low,int high);/快速排序 void insertionsort();/直接插入排序 void binaryins

7、ertsort();/折半插入排序 void selectsort();/簡單選擇排序 void heapsort();/堆排序 void mergesort(sortlist<type> &table);/歸并排序 void filterdown(const int start);/建立最大堆 void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);/一趟歸并 void merge(sortlist<type>

8、&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);/兩路歸并算法; <2>直接插入排序直接插入排序的基本思想：開始時把第一個數據元素作為初始的有序序列，然后從第二個數據元素開始依次把數據元素按關鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1<i<=n)個數據元素時，前面的i-1個數據元素已經排好序，這時，用第i個數據元素的關鍵字與前面的i-1個數據元素的關鍵字順序進行比較，找到插入位置后就將第i個數據元素插入。

9、如此進行n-1次插入，就完成了排序。以下是在順序表上實現的直接插入排序在順序表上進行直接插入排序時，當插入第i(1<i<=n)個數據元素時，前面的arr0、arr1、arri-2已經排好序，這時，用arri-1的關鍵字依次與arri-2,arri-3,的關鍵字順序進行比較，如果這些數據元素的關鍵字大于arri-1的關鍵字，則將數據元素向后移一個位置，當找到插入位置后就將arri-1插入，就完成了arr0,arr1,arrn-1的排序。偽代碼如下template <class type>/直接插入排序void sortlist<type>:insertions

10、ort()type temp;int j;for(int i=1;i<=currentsize-1;i+)temp=arri;j=i-1; while(j>=0&&temp<arrj) arrj+1=arrj;j-; arrj+1=temp;cout<<"第"<<+num<<"趟排序結果為:" for(int t=0;t<currentsize;t+) cout<<arrt<<" " cout<<endl;num=0; &l

11、t;3>折半插入排序折半插入排序的基本思想：設在排序表中有n個數據元素arr0,arr1,arrn-1。其中，arr0,arr1,arrn-1是已經排好序的部分數據元素序列，在插入arri時，利用折半查找方法尋找arri的插入位置。折半插入排序方法只能在順序表存儲結構實現。偽代碼如下：template <class type>/折半插入排序void sortlist<type>:binaryinsertsort()type temp;int left,right;for(int i=1;i<currentsize;i+) left=0;right=i-1;t

12、emp=arri;while(left<=right)/找插入位置int mid=(left+right)/2;if(temp<arrmid)right=mid-1;else left=mid+1;for(int k=i-1;k>=left;k-)/向后移動arrk+1=arrk;arrleft=temp;cout<<"第"<<+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout

13、<<endl;num=0; <4>冒泡排序冒泡排序的基本思想是：設排序表中有n個數據元素。首先對排序表中第一，二個數據元素的關鍵字arr0和arr1進行比較。如果前者大于后者，則進行交換；然后對第二，三個數據做同樣的處理；重復此過程直到處理完最后兩個相鄰的數據元素。我們稱之為一趟冒泡，它將關鍵字最大的元素移到排序表的最后一個位置，其他數據元素一般也都向排序的最終位置移動。然后進行第二趟排序，對排序表中前n-1個元素進行與上述同樣的操作，其結果使整個排序表中關鍵字次大的數據元素被移到arrn-2的位置。如此最多做n-1趟冒泡就能把所有數據元素排好序。偽代碼如下：templ

14、ate <class type>/冒泡排序void sortlist<type>: bubblesort()int i=1;int finish=0;/0表示還沒有排好序while(i<currentsize &&!finish)finish=1;/排序結束標志置為,假定已經排好序for(int j=0;j<currentsize-i;j+)if(arrj>arrj+1)/逆序swap(arrj,arrj+1);/相鄰元素交換位置finish=0;/排序結束標志置為,表示本趟發生了交換，說明還沒有排好序i+;cout<<&q

15、uot;第"<<+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<<endl;num=0;<5>簡單選擇排序（直接選擇排序）直接選擇排序的算法基本思想是：a)開始時設i的初始值為0。b)如果i<n-1，在數據元素序列arriarrn-1中，選出具有最小關鍵字的數據元素arrk；否則算法結束。c)若arrk不是這組數據元素中的第一個數據元素（ik），則將arrk與arri這兩數據元素的位

16、置對調；d)令i=i+1轉步驟 b)。偽代碼如下：template <class type>void sortlist<type>:selectsort()/簡單選擇排序int k; for(int i=0;i<=currentsize-1;i+)k=i;for(int j=i+1;j<currentsize;j+)if(arrj<arrk)k=j;/k 指示當前序列中最小者的位置if(k!=i)/最小關鍵字的數據元素位置不等于iswap(arri,arrk);cout<<"第"<<+num<<&

17、quot;趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<<endl;num=0; <6>快速排序快速排序（Quick Sort）又被稱做分區交換排序，這是一種平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某個數據元素(例如取第一個數據元素)作為基準，按照該數據元素的關鍵字大小，將整個排序表劃分為左右兩個子表： 左側子表中所有數據元素的關鍵字都小于基準數據元素的關鍵字。右側子表中所有數據元素的關鍵字都大于或等于基準數據元素的關鍵字，基

18、準數據元素則排在這兩個子表中間(這也是該數據元素最終應安放的位置)，然后分別對這兩個子表重復施行上述方法的快速排序，直到所有的子表長度為1，則排序結束。偽代碼如下：template <class type>/快速排序void sortlist<type>:quicksort(int low,int high)/在待排序區間low,high上，遞歸地進行快速排序int i=low,j=high;type temp=arrlow;/取區間第一個位置為基準位置if(i<j)while(i<j)while(i<j&&temp<arrj)j

19、-;if(i<j)swap(arri,arrj);i+;while(i<j&&temp>=arri)i+;if(i<j)swap(arri,arrj);j-;arri=temp;/將基準元素就位cout<<"第"<<+x<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<<endl;quicksort(low,i-1);/在左子區間遞歸進行快速排序qu

20、icksort(i+1,high);/在右子區間遞歸進行快速排序 <7>堆排序（包括建立最大堆和堆排序兩個過程）堆排序算法的基本思想是：a.對排序表中的數據元素，利用堆的調整算法形成初始堆。b.輸出堆頂元素。c.對剩余元素重新調整形成堆。d.重復執行第b、c步，直到所有數據元素被輸出。 (1)建立最大堆的偽代碼如下：template <class type>/建立最大堆void sortlist<type>:filterdown(const int start)/向下調整使從start開始到currentsize-1為止的子表成為最大堆int i=start

21、,j=2*i+1;/j為i的左孩子int tablesize=currentsize;type temp=arri;while(j<=currentsize-1)if(j<currentsize-1 && arrj<arrj+1)j+;/在兩個孩子中選關鍵字較大者if(temp>=arrj)break;elsearri=arrj;i=j;j=2*j+1;arri=temp;(2)堆排序如果建立的堆滿足最大堆的條件，則堆的第一個數據元素arr0具有最大的關鍵字，將arr0與arrn-1對調，把具有最大關鍵字的數據元素交換到最后，再對前面的n-1個數據元素使

22、用堆的調整算法，重新建立最大堆，結果把具有次最大關鍵字的數據元素又上浮到堆頂，即arr0的位置，再對調arr0和arrn-2，如此反復執行n-1次，最后得到全部排序好的數據元素序列。偽代碼如下：template <class type>/堆排序void sortlist<type>:heapsort()int tablesize=currentsize;for(int i=(currentsize-2)/2;i>=0;i-)filterdown(i); /初始建堆for(int i=currentsize-1;i>=1;i-)swap(arr0,arri);

23、/堆頂元素和最后一個元素交換currentsize-;filterdown(0);/重建最大堆cout<<"第"<<+num<<"趟排序結果為:"for(int t=0;t<tablesize;t+)cout<<arrt<<" "cout<<endl;num=0;currentsize=tablesize; <8>歸并排序（包括歸并算法，一趟歸并算法和歸并排序）歸并算法其基本思想是：設有兩個有序表A和B，其數據元素個數（表長）分別為n和m，變量i

24、和j分別是表A和表B的當前檢測指針；設表C是歸并后的新有序表，變量k是它的當前存放指針。開始時i、j、k都分別指向A、B、C三個表的起始位置；然后根據Ai與Bj的關鍵字的大小，把關鍵字小的數據元素放到新表Ck中；且相應的檢測指針（i或j）和存放指針k增加1.如此循環，當i與j中有一個已經超出表長時，將另一個表中的剩余部分照抄到新表CkCm+n中。下面的歸并算法中，兩個待歸并的有序表首尾相接存放在數組sourcetable.arr中，其中第一個表的下標范圍從left到mid，另一個表的下標范圍從mid+1到right。前一個表中有mid-left+1個數據元素，后一個表中有right mid個數

25、據元素。歸并后得到的新有序表有right mid個數據元素。歸并后得到的新有序表存放在另一個輔助數組mergedtable.arr中，其下標范圍從left到right。偽代碼如下：template <class type>void sortlist<type>:merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right)int i=left,j=mid+1,k=left;/指針初始化

26、/i是前一段的當前元素位置，j是后一段的當前元素位置，k是輔助數組的當前位置while(i<=mid&&j<=right)if(sourcetable.arri<=sourcetable.arrj)mergedtable.arrk=sourcetable.arri;i+;k+;elsemergedtable.arrk=sourcetable.arrj;j+;k+;if(i<=mid)for(int p=k,q=i;q<=mid;p+,q+)mergedtable.arrp=sourcetable.arrq;/把前一段復制到mergedtableel

27、sefor(int p=k,q=j;q<=right;p+,q+)mergedtable.arrp=sourcetable.arrq;/把后一段復制到mergedtable一趟歸并算法設數組sourcetable.arr0到sourcetable.arrn-1中的n個數據元素已經分為一些長度為len的歸并項，將這些歸并項兩兩歸并，歸并成一些長度為2len的歸并項，結果放到mergedtable.arr中。如果n不是2len的整數倍，則一趟歸并到最后，可能遇到兩種情況：剩下一個長度為len的歸并項和一個長度不足len的歸并項，可用一次merge算法，將它們歸并成一個長度小于2len的歸并項

28、。只剩下一個歸并項，其長度小于或等于len，可將它直接復制到數組mergedtable.arr中。偽代碼如下：template <class type>template <class type>void sortlist<type>:mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len)int i=0;while(i+2*len<=currentsize-1)/表示至少有個子序列merge(sourcetable

29、,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;if(i+len<=currentsize-1)/若只有最后兩個子序列merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);else/若只有最后一個子序列for(int j=i;j<=currentsize-1;j+)mergedtable.arrj=sourcetable.arrj;if(len<=currentsize-1)if(num<currentsize) cout<<"第"<<

30、;+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<mergedtable.arrt<<" "cout<<endl; 歸并排序在一趟歸并算法的基礎上，實現兩路歸并排序算法。在兩路歸并排序算法中，初始排序表存放在數組table.arr中,第一趟歸并將table.arr中的歸并項兩兩歸并，結果存放在輔助數組temptable.arr中。第二趟將temptable.arr中的歸并項兩兩歸并，結果放回原數組table.arr中，如此反復進行。為了將最后歸并結果

31、仍放在數組table.arr中，歸并趟數應為偶數。如果做奇數趟就能完成時，最后還需要執行一次一趟歸并過程，由于這時的歸并項長度len>=n，因此在則趟歸并中while循環不執行，只做把temptable.arr中的數據元素復制到table.arr的工作。偽代碼如下：template <class type>void sortlist<type>:mergesort(sortlist<type> &table )/按數據元素關鍵字非遞減的順序對排序表table中數據元素進行遞歸排序sortlist<type> temptable;in

32、t len=1;while(len<currentsize)mergepass(table,temptable,len);len*=2;mergepass(temptable,table,len);len*=2; num=0; <9>主函數主要功能是顯示主菜單，以及對各種排序的調用偽代碼如下：int main()/主函數 cout<<" *"<<endl;cout<<" 排序問題 "<<endl;cout<<"*"<<endl<<en

33、dl<<endl;int c=1; char ch;int n1=0;while(c!=0)cout<<"="<<endl;cout<<"=可供選擇的排序方法="<<endl;cout<<" 1 直接插入排序 2 折半插入排序 "<<endl;cout<<" 3 冒泡排序 4 簡單選擇排序 "<<endl;cout<<" 5 快速排序 6 堆排序 "<<endl;c

34、out<<" 7 歸并排序 0 退出排序程序 "<<endl; cout<<" ="<<endl;cout<<"n 請輸入您需要的排序種類:"cin>>ch;if(ch='0') cout<<" 您已成功退出該系統!"<<endl;system("pause"); return 0;int n,number;if(ch>='0'&&ch<=&

35、#39;7')cout<<"n 輸入您要進行排序的數的個數："cin>>n;cout<<"n 請輸入"<<n<<"個數："sortlist<int>table(n);for(int i=0;i<n;i+)cin>>number;table.insert(i,number);switch(ch) case '1':cout<<"n *您選擇的是直接插入排序*n"<<endl;tab

36、le.insertionsort();break;system("pause");break;case '2':cout<<"n *您選擇的是折半插入排序*n"<<endl;table.binaryinsertsort();break;system("pause");break;case '3':cout<<"n *您選擇的是冒泡排序*n"<<endl;table.bubblesort();break;system("paus

37、e");break;case '4':cout<<"n *您選擇的是簡單選擇排序*n"<<endl;table.selectsort();break;system("pause");break;case '5':cout<<"n *您選擇的是快速排序*n"<<endl;table.quicksort(0,n-1);break;system("pause");break;case '6':cout<<

38、"n *您選擇的是堆排序*n"<<endl;table.heapsort();break;system("pause");break;case '7':cout<<"n *您選擇的是歸并排序*n"<<endl;table.mergesort(table);break;system("pause");break; system("pause");return 0;三 上機結果及體會1) 實際完成的情況說明此程序主要實現了對不同排序算法的演示，并給

39、出了每一趟的變化情況2) 程序的性能分析a. 直接插入排序（穩定的排序方法）1時間復雜度a) 若待排序記錄按關鍵字從小到大排列(正序)關鍵字比較次數：記錄移動次數：2(n-1)b)若待排序記錄按關鍵字從大到小排列(逆序)關鍵字比較次數：記錄移動次數： c) 若待排序記錄是隨機的，取最好和最壞情況的平均值關鍵字比較次數(約為)：記錄移動次數(約為)： 2空間復雜度：S(n)=O(1)b. 折半插入排序（穩定的排序算法）就平均性能而言，因為折半查找優于順序查找，所以折半插入排序也優于直接插入排序。關鍵字的比較次數為：n*log2(n)c. 冒泡排序（穩定的排序算法）1. 時間復雜度：a) 最好情況

40、（正序）b) 比較次數：n-1（只要進行一趟即可）c) 移動次數：0d) 最壞情況（逆序）e) 比較次數：（需n-1趟，每趟達到最大比較次數） f) 移動次數：在最壞情況下，時間復雜度為:T(n)=O(n²)2. 空間復雜度：S(n)=O(1)d. 簡單選擇排序（不穩定的排序方法）1. 時間復雜度：O(n2)。2. 空間復雜度：S(1)。 e. 快速排序（不穩定的排序方法）1.時間復雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n²) 2.空間復雜度：需棧空間以實現遞歸最壞情況：S(n)=O(n

41、)一般情況：S(n)=O(log2n) f. 堆排序（不穩定的排序方法） 1.間復雜性為O(nlog2n)。 2空間復雜性為O(1)。g. 歸并排序（穩定的排序方法） 1時間復雜度為O(nlog2n)。 2空間復雜度為O(n）。 3）運行情況主菜單直接插入排序折半插入排序冒泡排序簡單選擇排序快速排序堆排序歸并排序退出系統3) 上機過程中出現的問題及其解決方案1 快速排序時出現多一次排序的情況 解決方法：在進行循環體時，多運行了一次，將運行次序減1即可。2 堆排序時也出現與上一條相同的情況 解決方法：由于缺少一個判斷語句導致輸出只能是偶數倍趟數，因此加一條if(len<=currentsi

42、ze-1)判斷語句就可以使程序正常輸出結果3 快速排序趟數開始為1 ,2 ,1, 2出現 解決方法：再定義一個全局變量，不過當其用完時，沒有將它重新置為0，這樣最后輸出的趟數就正確了。4 運行程序時，若輸入字符，則必須輸入完全后，才判斷其為不正確的選擇 解決方法：加一個if判斷語句即可4) 程序中可以改進的地方說明本程序不能判斷字符數大于1的字符串，這方面需要改進可以在程序中加入性能分析，例如空間復雜度，時間復雜度等5) 程序中可以擴充的功能及其設計實現假想擴充功能：可以加入希爾排序等未加入的排序方法，可以加入性能分析實現假想：加入其他排序方法后，輸出為正確排序的過程，加入性能分析時，輸出排序

43、過程的同時，可以輸出時間復雜度與空間復雜度6) 收獲及體會在進行為期一個星期的課程設計中，最終完成了算法。這期間，遇到的各種麻煩也都相繼解決。從這次實踐中，我意識到自己還有很多不足之處。首先先說一下基本的。對于各種排序算法的過程還是不夠熟悉，進行編程時還需要翻書查找，對于這一點，只能說對數據結構的學習還不夠扎實，雖然說這門課程以后就沒有了，但是我想這門課對以后的學習會有很大幫助，所以有空時還應該繼續熟悉這門課程。其次，就是對于錯誤的處理，不能得心應手，不能正確處理一些簡單的錯誤。對于邏輯上的錯誤，不能夠立即找到出錯點，往往需要向同學請教才能找出錯誤，并且改正。我覺得這是自己獨自思考能力不高的問

44、題，遇事需要自己仔細想想，若還不能改正，再請教別人也不遲。從總體上說，整個代碼的實現還是存在不足的，例如本程序不能判斷字符數大于1的字符串，沒有相應排序的性能分析（如空間復雜度，時間復雜度），等等。從這點看，說明自己的程序還是不夠完善，不能做到十全十美，希望以后能有所修正。總而言之，從這次的實踐中我學到了很多東西，希望以后能夠多加運應 7) 源代碼：#include "stdafx.h"#include<iostream>using namespace std;const int maxsize=100;int num=0;/定義全局變量，為每一趟的輸出做準備i

45、nt x=0;template<class type>class sortlistprivate:int currentsize;/數據表中數據元素的個數public:type *arr;/存儲數據元素的向量（排序表）sortlist():currentsize(0)arr=new typemaxsize;/構造函數sortlist(int n)arr=new typemaxsize;currentsize=n;void insert(int i,type x)arri=x;sortlist()delete arr;/析構函數void swap(type &x,type &

46、amp;y)/數據元素x和y交換位置type temp=x;x=y;y=temp; void bubblesort();/冒泡排序 void quicksort(int low,int high);/快速排序 void insertionsort();/直接插入排序 void binaryinsertsort();/折半插入排序 void selectsort();/簡單選擇排序 void heapsort();/堆排序 void mergesort(sortlist<type> &table);/歸并排序 void filterdown(const int start);

47、/建立最大堆 void mergepass(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int len);/一趟歸并 void merge(sortlist<type>&sourcetable,sortlist<type>&mergedtable,const int left,const int mid,const int right);/兩路歸并算法;template <class type>/直接插入排序void sortl

48、ist<type>:insertionsort()type temp;int j;for(int i=1;i<=currentsize-1;i+)temp=arri;j=i-1; while(j>=0&&temp<arrj) arrj+1=arrj;j-; arrj+1=temp;cout<<"第"<<+num<<"趟排序結果為:" for(int t=0;t<currentsize;t+) cout<<arrt<<" "

49、cout<<endl;num=0;template <class type>/折半插入排序void sortlist<type>:binaryinsertsort()type temp;int left,right;for(int i=1;i<currentsize;i+) left=0;right=i-1;temp=arri;while(left<=right)/找插入位置int mid=(left+right)/2;if(temp<arrmid)right=mid-1;else left=mid+1;for(int k=i-1;k>

50、;=left;k-)/向后移動arrk+1=arrk;arrleft=temp;cout<<"第"<<+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<<endl;num=0;template <class type>/冒泡排序void sortlist<type>: bubblesort()int i=1;int finish=0;/0表示還沒有排好序wh

51、ile(i<currentsize &&!finish)finish=1;/排序結束標志置為,假定已經排好序for(int j=0;j<currentsize-i;j+)if(arrj>arrj+1)/逆序swap(arrj,arrj+1);/相鄰元素交換位置finish=0;/排序結束標志置為,表示本趟發生了交換，說明還沒有排好序i+;cout<<"第"<<+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt&

52、lt;<" "cout<<endl;num=0;template <class type>void sortlist<type>:selectsort()/簡單選擇排序int k; for(int i=0;i<currentsize-1;i+)k=i;for(int j=i+1;j<currentsize;j+)if(arrj<arrk)k=j;/k 指示當前序列中最小者的位置if(k!=i)/最小關鍵字的數據元素位置不等于iswap(arri,arrk);cout<<"第"<

53、<+num<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<<endl;num=0;template <class type>/快速排序void sortlist<type>:quicksort(int low,int high)/在待排序區間low,high上，遞歸地進行快速排序int i=low,j=high;type temp=arrlow;/取區間第一個位置為基準位置if(i<j)whil

54、e(i<j)while(i<j&&temp<arrj)j-;if(i<j)swap(arri,arrj);i+;while(i<j&&temp>=arri)i+;if(i<j)swap(arri,arrj);j-;arri=temp;/將基準元素就位cout<<"第"<<+x<<"趟排序結果為:"for(int t=0;t<currentsize;t+)cout<<arrt<<" "cout<

55、;<endl;quicksort(low,i-1);/在左子區間遞歸進行快速排序quicksort(i+1,high);/在右子區間遞歸進行快速排序template <class type>/建立最大堆void sortlist<type>:filterdown(const int start)/向下調整使從start開始到currentsize-1為止的子表成為最大堆int i=start,j=2*i+1;/j為i的左孩子int tablesize=currentsize;type temp=arri;while(j<=currentsize-1)if(j<currents