各种排序算法时间性能的比较重点讲义

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比较次数为：%