当前位置:文档之家 > 实验1 归并排序分治策略的设计与实现

实验1 归并排序分治策略的设计与实现

湖南大学算法分析与设计实验报告

实验1 归并排序分治策略的设计与实现

一、实验目的

1、熟悉分治法求解问题的抽象控制策略;

2、熟悉在顺序存储表示下求解分类问题的递归算法设计;

3、通过实例转换, 掌握分治法应用。

二、实验内容

1、学习分治方法的原理;

2、针对分治问题设计递归算法实现归并排序算法;

3、根据归并排序的递归算法改写成迭代算法。

4、测试程序与验收并进一步将程序改写成模块化可用程序。

三、实验程序的功能模块

【模块】

void Merge(int r[],int r1[],int s,int m,int t)

{ 实现数组中的已分好类的两部分进行合并 }

void MergeSort(int r[],int r1[],int s,int t)

{ 对数组中从下标low开始到heigh结束的部分进行分类 }

【递归实现】

//合并数组

void Merge(int r[],int r1[],int s,int m,int t)

// r[]为待排序数列 r1[]用来存放排好序的数列三个int型变量 s m t ,分别为数组的最左,中间,最右

{

int i=s;

int j=m+1;

int k=s;

while(i<=m && j<=t)

{

if(r[i]<=r[j]) //左右两边的数组从头开始比,选择小者放入r1

r1[k++]=r[i++];

else r1[k++]=r[j++];

1

下载Word文档免费下载:

实验1 归并排序分治策略的设计与实现下载

(共5页)