1、實訓報告實訓題目：各種排序算法時間性能的比較 學 院： 計算機科學與技術學院 專 業： 軟件工程 班 級： 142 學 號： 1400170269 學生姓名： 莫磊 指導教師： 蔡麗 2016年 3 月15 日一、實訓目的及要求 數據結構是計算機課程的一門重要的基礎課，它的教學要求大致有三個重要方面：其一就是讓學生學會分析研究計算機加工的數據對象的特性，以便為數據選擇適當的物理結構和邏輯結構；其二，根據結構，選擇適當的算法，并初步掌握算法的時間分析和空間分析；其三，學習復雜的程序設計。本綜合實訓利用Visual Studio 2008 集成編程環境為實踐工具，通過上機實踐培養學生分析具體問題、

2、解決實際問題的能力，訓練和培養學生的數據抽象能力和程序設計的能力。 數據結構是一門實踐性較強的課程，以培養學生的數據抽象能力和程序設計的能力為目的。在實訓時應注重培養學生的實際操作能力。本綜合實訓安排了18學時的實驗課時，具體要求如下：1. 學習和理解每個實訓題目的基本理論和方法；2. 掌握每個實驗的實現步驟和關鍵技術；3. 準備好實驗所需要的資源和文檔；4. 上機實現程序，得到通過調試的正確程序。5. 根據每個實驗的不同要求，完成實驗報告的word文檔。2、 實訓環境 Windows XPVisual Studio 2013 三、實訓內容 (1) 設計并實現上述各種排序算法；(2) 產生正序

3、和逆序的初始排列分別調用上述排序算法，并比較時間性能；(3) 產生隨機的初始排列分別調用上述排序算法，并比較時間性能。 （4）對各種排序方法（直接插入排序、希爾排序、起泡排序、直接選擇排序）的時間性能進行比較。四、算法描述及實訓步驟 上述各種排序方法都是基于比較的內排序，其時間主要消耗在排序過程中進行的記錄的比較次數和移動次數，因此，統計在相同數據狀態下不同排序算法的比較次數和移動次數，即可實現比較各種排序算法的目的。 五、總結及心得體會直接選擇排序算法是對冒泡排序的改進，這種方法是在參加排序數組中找出最小（或最大）的數據元素，使它與第一個元素中的數據相互交換位置然后再在余下的元素中找出最小（

4、或最大）的數據元素與第二個元素中的元素交換位置，以此類推直到所有元素成為有序序列。六、實訓結果七、源代碼：#include <stdio.h>#include <stdlib.h>#include <time.h>/正序希爾排序void xiEr(int num, int n, int &no, int &r)int item;int i, j, d;for (d = n / 2; d >= 1; d = d / 2)for (i = d; i<n; i+)item = numi;j = i - d;while (j >=

5、0) && (item<numj)numj + d = numj;j = j - d;r = r + 1;numj + d = item;no = no + 1;/printf("n");/for(int x=0;x<n;x+)/printf("%dt",numx);/逆序希爾排序void xiErUp(int num, int n, int &no, int &r)int item;int i, j, d;for (d = n / 2; d >= 1; d = d / 2)for (i = d; i&l

6、t;n; i+)item = numi;j = i - d;while (j >= 0) && (item>numj)numj + d = numj;j = j - d;r = r + 1;numj + d = item;no = no + 1;/正序冒泡排序void MaoPao(int num, int n, int &no, int &r)bool flag;int test;for (int i = 1; i<n; i+)flag = true;for (int j = n - 1; j >= i; j-)if (numj<

7、numj - 1)test = numj;numj = numj - 1;numj - 1 = test;flag = false;r+;no+;if (flag)return;void MaoPaoUp(int num, int n, int &no, int &r)bool flag;int test;for (int i = 1; i<n; i+)flag = true;for (int j = n - 1; j >= i; j-)if (numj>numj - 1)test = numj;numj = numj - 1;numj - 1 = test;

8、flag = false;r+;no+;if (flag)return;void ChaRu(int num, int n, int &no, int &r)/直接插入排序/ :比較次數，r : 移動次數。int i, j, x;for (i = 1; i<n; i+)no+;x = numi;j = i - 1;while (j >= 0) && (x<numj)r+;numj + 1 = numj;j-; / 順序比較和移動numj + 1 = x;void ChaRuUp(int num, int n, int &no, int

9、&r)/直接插入排序/:比較次數，r : 移動次數。int i, j, x;for (i = 1; i<n; i+)no+;x = numi;j = i - 1;while (j >= 0) && (x>numj)r+;numj + 1 = numj;j-; / 順序比較和移動numj + 1 = x;void XuanZe(int num, int n, int &no, int &r)/直接選擇排序/:比較次數,r:移動次數int x; int i, j, k;for (i = 1; i <= n - 1; i+)k = i

10、- 1;for (j = i; j <= n - 1; j+)no+; if (numj < numk) k = j;if (k != i - 1)r+;x = numi - 1;numi - 1 = numk;numk = x;void XuanZeUp(int num, int n, int &no, int &r)/直接選擇排序/:比較次數,r:移動次數int x; int i, j, k;for (i = 1; i <= n - 1; i+)k = i - 1;for (j = i; j <= n - 1; j+)no+; if (numj &g

11、t; numk) k = j;if (k != i - 1)r+;x = numi - 1;numi - 1 = numk;numk = x;void ShuChu(int num, int n, int no, int r, char name)printf("=輸出%s排序后數據如下=nn", name);for (int x = 0; x<n; x+)printf("%dt", numx);printf("n比較的次數為:%dt移動的次數為:%d", no, r);printf("n=nn");int

12、main()int num100;int n = 100;int no1, no2, no3, no4;int r1, r2, r3, r4;int no11, no22, no33, no44;int r11, r22, r33, r44;char name1 = "希爾正序"char name11 = "希爾逆序"char name2 = "冒泡正序"char name22 = "冒泡逆序"char name3 = "直接插入正序"char name33 = "直接插入逆序&quo

13、t;char name4 = "直接選擇正序"char name44 = "直接選擇逆序"int item1100;int item2100;int item3100;int item4100;int item22100;int item33100;int item44100;no4 = no3 = no2 = no1 = 0;r4 = r3 = r2 = r1 = 0;no44 = no33 = no22 = no11 = 0;r44 = r33 = r22 = r11 = 0;printf("=初始的隨機數據如下=nn");for

14、 (int i = 0; i<n; i+)numi = rand() %100;printf("%dt", numi);for (int x = 0; x<n; x+)item1x = numx;item2x = numx;item3x = numx;item4x = numx;item22x = numx;item33x = numx;item44x = numx;xiEr(num, n, no1, r1);ShuChu(num, n, no1, r1, name1); xiEr(item1,n,no11,r11);ShuChu(item1,n,no11,r1

15、1,name11);MaoPao(item2,n, no2, r2);ShuChu(item2, n, no2, r2, name2);MaoPaoUp(item22, n, no22, r22);ShuChu(item22, n, no22, r22, name22);ChaRu(item3,n,no3,r3);ShuChu(item3, n, no3, r3, name3);ChaRuUp(item33, n, no33, r33);ShuChu(item33, n, no33, r33, name33);XuanZe(item4, n, no4, r4);ShuChu(item4, n,

16、 no4, r4, name4);XuanZeUp(item44, n, no44, r44);ShuChu(item44, n, no44, r44, name44);printf("=n");printf("=n");printf("所有排序的比較次數和移動次數如下：nn");printf("%s:t比較次數為：%d 移動次數為:%dn", name1, no1, r1);printf("%s:t比較次數為：%d 移動次數為:%dn", name1, no11,r11);printf("%s:t比較次數為：%d 移動次數為:%dn", name2, no2, r2);printf("%s:t比較次數為：%d 移動次數為:%dn", name22, no22,r22);printf("%s:t比較次數為：%