实验二分治法归并排序教学内容

更新时间:2023-05-02 12:02:01 阅读量: 实用文档 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

实验二分治法归并排

实验二分治法归并排序

一、实验目的及要求

(-)实验目的

1、熟悉归并排序算法过程;

2、验证归并排序算法复杂度。

(二)实验要求

1、合理添加计数器

2、实现归并排序算法并验证复杂性

3、掌握递归方法

二、实验内容与步骤

1、设计归并排序算法

2、在算法中添加计数器,累计比较次数(注意计数器要用全局变量)和递归调用次数

3、完成算法分析

4、用JAVA实现算法,分别运行5?10个记录的排序,分析比较次数和规模之间的尖系

5、判断运行结果是否与分析结果一致

6、和实验一的结果比较复杂性差别(用图表)

三、实验结果与分析

1、代码如下:(n=8 )

import java.util.Sea nner;

public class GuiB in gPaiXu {

static int com=0, use =0; //com 表示比较次数,use 表示递归调用次数public static void main ( Stri ng[] args) {

int [] a = new int [8];

Seanner sea n = new Seanner (System, in);

int r=0, t=a. len gth -1;

int num;

System, out .printin ( ”请输入8个整数:”);

〃将输入的每个数记入数组

for (int i=0;i

num = sea n.n ext I nt ();

a[i] = num;

}

〃递归调用归并排序

PaiXu (a,r,t);

仅供学习与交流,如有侵权请联系网站刪除谢谢

〃输出各个数据

System, out .println( ”该8个整数从小到大是:”);

for (int i=0;i

System, out .print(a[i]+ ””);

}

System, out .println( "\n 比较次数:"+com);

System, out .println( ”递归调用次数:”+use );

}

〃归并排序

public static void PaiXu( int b[], int r, int t){ use ++; 〃每递归调用一次,加一int s;

int [] temp = new int [b. Iength ];

if (r==t) return ;

else {

s=(r+t)/2;

PaiXu (b,r,s);

PaiXu (b,s+1 ,t);

GuiBing (b,temp,r,s,t);

for (int i=r;iv=t;i++) b[i]=temp[i];

}

}

〃归并

public static void GuiB ing( int b[], int temp[], int r, int

s, int t){

int i=r,j=s+1 ,k=r; while (i<=s && j<=t){

if (b[i]<=b01)

temp[k++]=b[i++];

else

temp[k++]=b[j++];

com++; 〃每比较一次,加一

}

while (i<=s)

temp[k++]=b[i++];

while (j<=t)

temp[k++]=b[j++];

}

、算法分析:设待排序记录个数为,该算法的基本语句是归并算法的循环体的比较语句

“if (b[i]<=b[j]) temp[k++]=b[i++];

else temp[k++]=b[j++]; ”‘

其执行次数为:0(n],即执行一趟归并算法的时间复杂度为0(D)则归并排序算法存在以下推式:k(D)= { 2T(n/2) + n n> 1所以,归并排序算法的时间复杂度为'I ■ 12。

另外,归并排序算法递归调用次数为II 。

3、结果如下:

:应间霆独詔OC㈣离明呈控制台乂v已蜒止a GuiBingPaiXu [J A va应凫序I D:\Pn n=5

|L闫圖@ Javadoc空,芦明胃輦制台总1

卜已蟀止》GuiB ngPaiXu [Java应用程请愉人5个藝厂

陳5个整数从小到犬是;

12 3 4 5

比较次数:7递归调用次数油fEEfiffil @ Javadoc^〉旦疑占戈台帯

GuiB A ngPaiXu [Java 应用琶克请输刃、整数:

4

5

3

怜牙个整数从小到大是:

1 2a4S

比较次数;7递归调用次

数洱

b叵題|磁Javadoc |亀.芦朋貝圜4台滋弐已馆止* GuiBingPaiXu [Jnv□应用程序| 请输入音个整数:

4

6

怪个整勘从小到大站比sass :递归调用

次数:耳

1 <

淤个整對从小到犬是,

12345673

比较次数:L7 递归调用

衣数;久5

JI

n=8

4、与选择排序的对比(时间复杂度)

从时间复杂度上看,归并排序的要小于选择排序,

并且实际上,

在问题规模相同而待排序记录顺序的整齐程度有所差异的 情况下,

选择排序是不论待排序记录顺序的整齐程度如何,其时间复杂度都是固定的;

归并排序是若待排序记录顺序越整齐,其时间复杂度越小,

匚问题刼Javads 声明□控制台疣I

GuiBingPaiXu [Java 直更程书 D:\Proj

请输入丄D 个整数:

1

2

佥问鬆切Javadoc 篦声琥旦控制台亦 R 已舞止* GuiBingPaiXu [Java 应用程序]D;\Pro 请输入丄诃整数: 10

陽丄D 个整数从小到大是:

1234567S9 比较次数:甫

递归调用次数:甫

10 该久0个整数从小到犬是: 1234S67B9 比较次数:凸 递归调用次数;19 由n = 5,6, -,10等数据的运行结果可知'

10

n=10

10

5

随着问题规模n 的增加,其时间复杂度(比较次数的执行)也增加,所以,该算法分析的判断正确。

本文来源:https://www.bwwdw.com/article/mvse.html

Top