1、XXX大學實驗報告學院：計算計科學與信息學院 專業：數字媒體技術 班級：數媒091姓名學號實驗組實驗時間指導教師成績實驗項目名稱實驗目的1熟練掌握順序表和有序表的查找方法。2熟悉靜態查找樹的構造方法和查找算法，熟練掌握二叉排序樹的構造方法和查找算法。3掌握描述查找過程的判定樹的構造方法，掌握各種查找方法在等概率情況下查找成功時的平均查找長度。 實驗要求1了解散列表的構造和查找算法。 2了解各種排序方法的執行過程及其所依據的原則，掌握各種排序方法時間復雜度的分析方法。3熟練掌握希爾排序、快速排序、堆排序等高效排序算法。實驗原理在visual c+編程環境中編寫程序源代碼，并編譯、運行程序結果實驗

2、儀器奔騰2計算機或以上機型、visual c+編程環境實驗步驟1、 確定數據的結構2、 編寫頭文件、函數及變量聲明3、 設計子函數4、 寫主函數，并調用子函數5、 調試編寫好的程序6、 編譯正確后，運行，觀察分析結果實驗內容程序1 內部排序算法比較問題描述編寫常用的排序算法，并編寫主程序測試。基本要求（1）對以下常用的6種排序算法進行比較：直接插入排序、直接選擇排序、堆排序、快速排序、冒泡排序。（2）待排序表的表長不小于100；其中的數據用自行設計。（3）對結果作出分析。直接插入排序void InsertSort ( ElemType A, int n int i, j;ElemType x;

3、for ( i=1; i 進行 n-1 次插入 x = Ai; /準備插入第i個元素 for ( j=i-1; j>=0; j- /從第i-1個開始往前找插入點if ( x.stn < Aj.stn Aj+1=Aj;else break; Aj+1=x; /插入直接選擇排序void SelectSort(ElemType A, int nint i, j, k;ElemType x;for ( i=0; i<=n-2; i+ /每一趟選擇最小元素并與Ai交換k=i; for (j=i+1; j<=n-1; j+ /查找最小元素的下標if (Aj.stn if (k!=i

4、 /交換 x=Ai; Ai=Ak; Ak=x; 堆排序void CreatHeap(ElemType A, int nint i; for( i = (n2/2; i >= 0; i-Sift(A, n, i; /調整Ai.n-1使之為一個堆void Sift(ElemType A, int n, int i / 調整Ai.n-1成為一個堆（它的左右子樹已是一個堆）ElemType x=Ai; int j = 2 * i + 1; / j為i的左孩子 while (j <= n-1 / i有左子樹if ( j +1 < n && Aj.st

5、n < Aj+1.stn j+; / 使j指向左右孩子中排序碼大的孩子if ( x.stn < Aj.stn /將Aj上移，以便向下篩Ai=Aj; i=j; j=2*i+1; else break;Ai=x; void HeapSort(ElemType A, int n /A為待排序表， n為表的長度int i;ElemType x；  CreatHeap(A, n; / 把A建成一個堆for (i = n - 1; i >= 1; i- - x = A0; /第0個元素與第i個元素交換A0 = Ai;Ai = x; Sift(A, i, 0; /調整A0.i-1

6、使之為一個堆 冒泡排序void BubbleSort( ElemType A, int n int i, j, flag; /flag為交換標記ElemType x;for (i=1; i<=n-1; i+ / 最多n-1趟排序flag=0; /假設本次沒有交換for (j=n-1; j>=i; j- /第i 趟if ( Aj.stn < Aj-1.stn flag=1; /出現交換x=Aj; Aj=Aj-1; Aj-1=x; if (flag=0 return;快速排序void QuickSort(ElemType A , int s, int t /遞歸算法，對區間 As

7、 At 進行快速排序int i=s+1, j=t;ElemType temp, x = As; /第一個為基準元素while ( i<=j while ( i<=j && Ai.stn <= x.stn i+; /從左到右while ( i<=j && Aj.stn >= x.stn j-; /從右到左 if ( i < j temp=Ai; Ai=Aj; Aj=temp; i+; j-;if (s!=j /交換基準元素As=Aj; Aj=x; if (s 處理左區間 if (j+1 處理右區間 實驗數據#include us

8、ing namespace std;typedef int ElemType;/直接插入排序void InsertSort ( ElemType A, int n int i, j;ElemType x;for ( i=1; i / 進行 n-1 次插入 x = Ai; /準備插入第i個元素 for ( j=i-1; j>=0; j- /從第i-1個開始往前找插入點if ( x< Aj Aj+1=Aj;else break; Aj+1=x; /插入/直接選擇排序void SelectSort(ElemType A, int nint i, j, k;ElemType x;for (

9、 i=0; i<=n-2; i+ /每一趟選擇最小元素并與Ai交換k=i; for (j=i+1; j<=n-1; j+ /查找最小元素的下標if (Aj if (k!=i /交換 x=Ai; Ai=Ak; Ak=x; /堆排序void Sift(ElemType A, int n, int i;void CreatHeap(ElemType A, int nint i; for( i = (n-2/2; i >= 0; i-Sift(A, n, i; /調整Ai.n-1使之為一個堆void Sift(ElemType A, int n, int i / 調整Ai.n-1成為

10、一個堆（它的左右子樹已是一個堆）ElemType x=Ai; int j = 2 * i + 1; / j為i的左孩子while (j <= n-1 / i有左子樹if ( j +1 < n && Aj< Aj+1j+; / 使j指向左右孩子中排序碼大的孩子if ( x< Aj /將Aj上移，以便向下篩Ai=Aj; i=j; j=2*i+1; else break;Ai=x; void HeapSort(ElemType A, int n /A為待排序表，n為表的長度int i;ElemType x; CreatHeap(A, n; / 把A建成一個堆f

11、or(i=n-1;i>=1;i-x = A0; /第個元素與第i個元素交換A0 = Ai;Ai = x; Sift(A, i, 0; /調整A0.i-1使之為一個堆 /冒泡排序void BubbleSort( ElemType A, int n int i, j, flag; /flag為交換標記ElemType x;for (i=1; i<=n-1; i+ / 最多n-1趟排序flag=0; /假設本次沒有交換for (j=n-1; j>=i; j- /第i 趟if ( Aj< Aj-1 flag=1; /出現交換x=Aj; Aj=Aj-1; Aj-1=x; if (

12、flag=0 return;/快速排序void QuickSort(ElemType A, int s, int t /遞歸算法，對區間As At 進行快速排序int i=s+1, j=t;ElemType temp, x = As; /第一個為基準元素while ( i<=j while ( i<=j && Ai<= x i+; /從左到右while ( i<=j && Aj>=x j-; /從右到左 if ( i < j temp=Ai; Ai=Aj; Aj=temp; i+; j-;if (s!=j /交換基準元素As=

13、Aj; Aj=x;if (s / 處理左區間 if (j+1 / 處理右區間 void main(int i,j,n,N=5;cout<<"請輸入個整數：" ElemType A5;for(j=0;j cin>>Aj;cout<<"排序前為："< for(i=0;i cout< cout<<"直接插入排序:"< InsertSort (A, N ;for(i=0;i cout< 運 /運行結果如右;cout<<"直接選擇排序:"< SelectSort(A, N;for(i=0;i cout< cout<<"堆排序:"< HeapSort(A, N;f