各種排序算法時(shí)間性能的比較

1、實(shí)訓(xùn)報(bào)告實(shí)訓(xùn)題目：各種排序算法時(shí)間性能的比較 學(xué) 院： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 專 業(yè)： 軟件工程 班 級(jí)： 142 學(xué) 號(hào)： 1400170269 學(xué)生姓名： 莫磊 指導(dǎo)教師： 蔡麗 2016年 3 月15 日一、實(shí)訓(xùn)目的及要求 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)課程的一門重要的基礎(chǔ)課，它的教學(xué)要求大致有三個(gè)重要方面：其一就是讓學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便為數(shù)據(jù)選擇適當(dāng)?shù)奈锢斫Y(jié)構(gòu)和邏輯結(jié)構(gòu)；其二，根據(jù)結(jié)構(gòu)，選擇適當(dāng)?shù)乃惴?，并初步掌握算法的時(shí)間分析和空間分析；其三，學(xué)習(xí)復(fù)雜的程序設(shè)計(jì)。本綜合實(shí)訓(xùn)利用Visual Studio 2008 集成編程環(huán)境為實(shí)踐工具，通過上機(jī)實(shí)踐培養(yǎng)學(xué)生分析具體問題、

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

3、和逆序的初始排列分別調(diào)用上述排序算法，并比較時(shí)間性能；(3) 產(chǎn)生隨機(jī)的初始排列分別調(diào)用上述排序算法，并比較時(shí)間性能。 （4）對(duì)各種排序方法（直接插入排序、希爾排序、起泡排序、直接選擇排序）的時(shí)間性能進(jìn)行比較。四、算法描述及實(shí)訓(xùn)步驟 上述各種排序方法都是基于比較的內(nèi)排序，其時(shí)間主要消耗在排序過程中進(jìn)行的記錄的比較次數(shù)和移動(dòng)次數(shù)，因此，統(tǒng)計(jì)在相同數(shù)據(jù)狀態(tài)下不同排序算法的比較次數(shù)和移動(dòng)次數(shù)，即可實(shí)現(xiàn)比較各種排序算法的目的。 五、總結(jié)及心得體會(huì)直接選擇排序算法是對(duì)冒泡排序的改進(jìn)，這種方法是在參加排序數(shù)組中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)元素，使它與第一個(gè)元素中的數(shù)據(jù)相互交換位置然后再在余下的元素中找出最?。?/p>

4、或最大）的數(shù)據(jù)元素與第二個(gè)元素中的元素交換位置，以此類推直到所有元素成為有序序列。六、實(shí)訓(xùn)結(jié)果七、源代碼：#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)/直接插入排序/ :比較次數(shù)，r : 移動(dòng)次數(shù)。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-; / 順序比較和移動(dòng)numj + 1 = x;void ChaRuUp(int num, int n, int &no, int

9、&r)/直接插入排序/:比較次數(shù)，r : 移動(dòng)次數(shù)。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-; / 順序比較和移動(dòng)numj + 1 = x;void XuanZe(int num, int n, int &no, int &r)/直接選擇排序/:比較次數(shù),r:移動(dòng)次數(shù)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)/直接選擇排序/:比較次數(shù),r:移動(dòng)次數(shù)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排序后數(shù)據(jù)如下=nn", name);for (int x = 0; x<n; x+)printf("%dt", numx);printf("n比較的次數(shù)為:%dt移動(dòng)的次數(shù)為:%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("=初始的隨機(jī)數(shù)據(jù)如下=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("所有排序的比較次數(shù)和移動(dòng)次數(shù)如下：nn");printf("%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為:%dn", name1, no1, r1);printf("%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為:%dn", name1, no11,r11);printf("%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為:%dn", name2, no2, r2);printf("%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為:%dn", name22, no22,r22);printf("%s:t比較次數(shù)為：%