1、各种排序算法时间性能的比较讲解实训报告实训题目：各种排序算法时间性能的比较 学 院： 计算机科学与技术学院 专 业： 软件工程 班 级： 142 学 号： 1400170269 学生姓名： 莫磊 指导教师： 蔡丽 2016年 3 月15 日一、实训目的及要求 数据结构是计算机课程的一门重要的基础课，它的教学要求大致有三个重要方面：其一就是让学生学会分析研究计算机加工的数据对象的特性，以便为数据选择适当的物理结构和逻辑结构；其二，根据结构，选择适当的算法，并初步掌握算法的时间分析和空间分析；其三，学习复杂的程序设计。本综合实训利用Visual Studio 2008 集成编程环境为实践工具，通过
2、上机实践培养学生分析具体问题、解决实际问题的能力，训练和培养学生的数据抽象能力和程序设计的能力。 数据结构是一门实践性较强的课程，以培养学生的数据抽象能力和程序设计的能力为目的。在实训时应注重培养学生的实际操作能力。本综合实训安排了18学时的实验课时，具体要求如下：1. 学习和理解每个实训题目的基本理论和方法；2. 掌握每个实验的实现步骤和关键技术；3. 准备好实验所需要的资源和文档；4. 上机实现程序，得到通过调试的正确程序。5. 根据每个实验的不同要求，完成实验报告的word文档。2、实训环境 Windows XPVisual Studio 2013 三、实训内容 (1) 设计并实现上述各
3、种排序算法；(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 （4）对各种排序方法（直接插入排序、希尔排序、起泡排序、直接选择排序）的时间性能进行比较。四、算法描述及实训步骤 上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。 五、总结及心得体会直接选择排序算法是对冒泡排序的改进，这种方法是在参加排序数组中找出最小（或最大）的数据元素，使它与第一个元素中的数据相互交换位置然
4、后再在余下的元素中找出最小（或最大）的数据元素与第二个元素中的元素交换位置，以此类推直到所有元素成为有序序列。六、实训结果七、源代码：#include #include #include /正序希尔排序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= 0) & (itemnumj) numj + d = numj; j = j - d; r = r + 1; numj + d = item; no = no + 1;
5、 / printf(n); / for(int x=0;x= 1; d = d / 2) for (i = d; i= 0) & (itemnumj) 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= i; j-) if (numjnumj - 1) test = numj; numj = numj - 1; numj - 1
6、 = 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= i; j-) if (numjnumj - 1) test = numj; numj = numj - 1; numj - 1 = test; flag = false; r+; no+; if (flag) return; void ChaRu(int num, int n, int &no, int &r)/直接插入排序
7、 / :比较次数，r : 移动次数。 int i, j, x; for (i = 1; i= 0) & (xnumj) r+; numj + 1 = numj; j-; / 顺序比较和移动 numj + 1 = x; void ChaRuUp(int num, int n, int &no, int &r)/直接插入排序 /:比较次数，r : 移动次数。 int i, j, x; for (i = 1; i= 0) & (xnumj) r+; numj + 1 = numj; j-; / 顺序比较和移动 numj + 1 = x; void XuanZe(int num, int n, int
8、 &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 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
9、 = 1; i = n - 1; i+) k = i - 1; for (j = i; j 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; xn; x+) printf(%dt, numx); printf(n比较的次数为:%dt移动的次数为:%d, no, r); printf(n=nn);in
10、t 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 = 直接插入逆序; char name4 = 直接选择正序; char name44 = 直接选择逆序; int it
11、em1100; 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 (int i = 0; in; i+) numi = rand() %100; printf(%dt, numi); for (int x
12、= 0; xn; 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,r11,name11); MaoPao(item2,n, no2, r2); ShuChu(item2, n, no2, r2, name2); MaoPaoU
13、p(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, no4, r4, name4); XuanZeUp(item44, n, no44, r44); ShuChu(item44, n,
14、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比较次数为：%d 移动次数为:%dn, name3, no3, r3); printf(%s:t比较次数为：%d 移动次数为:%dn, name33, no33,r33); printf(%s:t比较次数为：%d 移动次数为:%dn, name4, no4, r4); printf(%s:t比较次数为：%d 移动次数为:%dn, name44, no44,r44); printf(n=n); getchar(); return 0;
