何彬实验报告

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业计算机科学与工程学院算法与数据结构实验报告(十)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目排序技术综合应用实验类别基础性（） 设计性（） 综合性（） 其它（ ）实验目的及要求（1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；（2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。成 绩 评 定 表类 别评 分 标

2、 准分值得分合 计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明： 评阅教师： 赵卿松 日 期： 2015 年 6 月 18 日实 验 内 容实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组数据：单增、单减、乱码等，对它们进行比较分析。实验说明：希尔排序算法如下：void ShellSort(int r , int n)for (d=n/2; d=1; d=d/2) /以增量为d进行直接插入排序for (i=d+1; i0 & r0rj;

3、j=j-d) rj+d=rj; /记录后移d个位置 rj+d=r0; 快速排序算法如下：void QuickSort(int r , int first, int end) if (firstend) /递归结束 pivot=Partition(r, first, end); /一次划分 QuickSort(r, first, pivot-1); /递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); /递归地对右侧子序列进行快速排序 int Partition(int r , int first, int end)i=first; j=end; /初始化wh

4、ile (ij) while (ij & ri= rj) j-； /右侧扫描 if (ij) rirj; /将较小记录交换到前面 i+; while (ij & ri= rj) i+； /左侧扫描if (ij) rjri; /将较大记录交换到后面 j-; retutn i; /i为轴值记录的最终位置实 验 内 容#include#define Max 100int ShellSort(int r, int n)int x = 0;for (int d = n / 2; d = 1; d = d / 2) /以增量为d进行直接插入排序 for (int i = d + 1; i 0 & r0 r

5、j; j = j - d)rj + d = rj; /记录后移d个位置x+;rj + d = r0;return x;void exchange(int a, int i, int j)int temp;temp = ai;ai = aj;aj = temp;int Partition(int r, int first, int end, int &x) int i = first, j = end; /初始化while (i j)while (i j & ri = rj)j-; /右侧扫描if (i j) exchange(r, i, j); /将较小记录交换到前面 i+;x+;while

6、(i j & ri = rj)i+; /左侧扫描if (i j) exchange(r, j, i); /将较大记录交换到后面 j-;x+;return i; /i为轴值记录的最终位置int quickSort(int r, int first, int end) /在序列 firstend中递归地进行快速排序static int x = 0;int pivotpos;if (first end)pivotpos = Partition(r, first, end, x);quickSort(r, first, pivotpos - 1);quickSort(r, pivotpos + 1,

7、end);return x;void getlist(int a, int &n)printf(请输入数组的元素的个数n：);scanf(%d, &n);for (int i = 1; i = n; i+)printf(请输入数组的第%d个元素：, i);scanf(%d, &ai);void print(int a, int n)for (int i = 1; i = n; i+)printf(%d , ai);printf(n);void main()int aMax = 0 , bMax = 0 , n = 0, x, y;getlist(a, n);for (int i = 0; i

8、= n; i+)bi = ai;x = ShellSort(a, n);printf(经过希尔排序得到的排序序列为：);print(a, n);printf(希尔排序需要的交换次数为：%d次nn, x);y = quickSort(b, 1, n);printf(经过快速排序得到的排序序列为：);print(b, n);printf(快速排序需要的交换次数为：%d次nn, y);实 验 内 容得出结论：希尔排序和快速排序的复杂程度上，对于顺序或基本顺序的序列，两者复杂程度相当；逆序、基本逆序或者乱序的情况下，快速排序都相对优良。实 验 总 结通过本次上机实验，熟练掌握排序的常用算法，并且掌握了希尔