1305120411_何彬_实验报告10

《算法与数据结构》实验报告 5
计算机科学与工程学院
{ for (int i = 1; i <= n; i++) { printf("%d ", a[i]); } printf("\n"); } void main() { int a[Max] = { 0 }, b[Max] = { 0 }, n = 0, x, y; getlist(a, n); for (int i = 0; i <= n; i++) b[i] = a[i]; x = ShellSort(a, n); printf("经过希尔排序得到的排序序列为："); print(a, n); printf("希尔排序需要的交换次数为：%d 次\n\n", x); y = quickSort(b, 1, n); printf("经过快速排序得到的排序序列为："); print(b, n); printf("快速排序需要的交换次数为：%d 次\n\n", y); }
void ShellSort(int r[ ], int n) { for (d=n/2; d>=1; d=d/2) //以增量为 d 进行直接插入排序 { for (i=d+1; i<=n; i++) { r[0]=r[i]; //暂存被插入记录 for (j=i-d; j>0 && r[0]<r[j]; j=j-d) r[j+d]=r[j]; r[j+d]=r[0]; } } } //记录后移 d 个位置
《算法与数据结构》实验报告 4
计算机科学与工程学院
int quickSort(int r[], int first, int end) { //在序列 first~end 中递归地进行快速排序 static int x = 0; int pivotpos; if (first < end) { pivotpos = Partition(r, first, end, x); quickSort(r, first, pivotpos - 1); quickSort(r, pivotpos + 1, 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", &a[i]); } } void print(int a[], int n)
实 验 目 的 及 要 求
上机表现
程序与报告 说明：
70 分
评阅教师：
赵卿松 6 月 18 日
日 期： 2015 年
计算机科学与工程学院
实 验 内 容 实验内容：对希尔排序、快速排序、归并排序任意选择两种排序方法进行比较。 任意选择希尔排序、快速排序、归并排序中两种排序方法，对任意给定一组 数据：单增、单减、乱码等，对它们进行比较分析。 实验说明： 希尔排序算法如下：
return x; } void exchange(int a[], int i, int j) {
《算法与数据结构》 temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } int Partition(int r[], int first, int end, int &x) { int i = first, j = end; //初始化 while (i < j) { while (i < j && r[i] <= r[j]) j--; //右侧扫描 if (i < j) { exchange(r, i, j); //将较小记录交换到前面 i++; x++; } while (i < j && r[i] <= r[j]) i++; //左侧扫描 if (i < j) { exchange(r, j, i); //将较大记录交换到后面 j--; x++; } } return i; //i 为轴值记录的最终位置 }
《算法与数据结构》实验报告
8
《算法与数据结构》实验报告
6
计算机科学与工程学院
实 验 内 容
《算法与数据结构》实验报告 7
计算机科学与工程学院
得出结论：希尔排序和快速排序的复杂程度上，对于顺序或基本顺序 的序列，两者复杂程度相当；逆序、基本逆序或者乱序的情况下，快 速排序都相对优良。
实 验 总 结
通过本次上机实验， 熟练掌握排序的常用算法， 并且掌握了希尔排序、 快速排序、基数排序的算法。并且把书上的算法应用到具体的程序设 计中，利用 vc 6.0 平台，结合之前学习的 C 语言的知识，提高了自 己的动手能力。也让自己认识了多种排序的方式，并对几种排序算法 在遇到不同序列时所需的排列次数等进行分析，对排序有了新的认 识。
快速排序算法如下：
void QuickSort(int r[ ], int first, int end) { if (first<end) { //递归结束 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; //初始化 while (i<j) { while (i<j && r[i]<= r[j]) j--； //右侧扫描 if (i<j) { r[i]←→r[j]; //将较小记录交换到前面 i++; } while (i<j && r[i]<= r[j]) i++； //左侧扫描 if (i<j) { r[j]←→r[i]; //将较大记录交换到后面 j--; } } retutn i; //i 为轴值记录的最终位置
}
《算法与数据结构》实验报告
2
计算机科学与工程学院
实 验 内 容
#include<stdio.h> #define Max 100 int 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 <= n; i++) { r[0] = r[i]; //暂存被插入记录 for (int j = i - d; j > 0 && r[0] < r[j]; j = j - d) { r[j + d] = r[j]; //记录后移 d 个位置 x++; } r[j + d] = r[0]; }
计算机科学与工程学院
《算法与数据结构》实验报告(十)
专业班级 学生学号 学生姓名 实验项目 实验类别 2013 网络工程 01 实验地点 指导教师 实验时间 排序技术综合应用 基础性（√） 设计性（） 综合性（） 其它（ ） （1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算 法的方法； （2）深刻理解排序的定义和各种排序方法的特点，并能加以灵 活应用； （3）了解各种方法的排序过程及其依据的原则，并掌握各种排 序方法的时间复杂度的分析方法。 成 绩 评 定 表 类 别 评 分 标 准 积极出勤、遵守纪律 按要求完成设计任务 程序代码规范、功能正确 报告详实完整、体现收获 分值 30 分 得分 合 计 423 机房 赵卿松