分数的比较和排序

沈阳化工大学实验报告

课程名称 算法设计与分析

项目名称 归并排序(分治)和插入排序的比较

学 院 应用技术学院

专 业 计中职1401

指导教师 张雪

报 告 人 张庭浩 学号 **********

实验时间 2016.11.05

提交时间 2016.11.05

一、实验目的

1.理解和掌握分治算法的相关内容。

2.具体完成插入排序和归并排序性能的比较。

二、实验内容

编写一个真随机函数，随机产生大量数字。在产生相同的一组大量随机数字后，分别用归并排序和插入排序两种算法进行排序，并通过时间函数分别计算出运行的时间。

三、伪代码

1.归并排序

/*数组a[]是原始数组，数组b[]是目标数组*/

归并排序（数组 a[],数组 b[]）{

`分割与归并（数组 a[],0, a.length,数组 b[])

}

/*通过递归把要排序的子序列分的足够小*/

分割与归并（数组 a[],起始位置,结束位置,数组 b[]){

if(结束位置 - 起始位置 < 2)

返回

中间位置 = （起始位置+结束位置）/2

分割与归并（数组 a[],起始位置,中间位置,数组 b[])

分割与归并（数组 a[],中间位置,结束位置,数组 b[])

归并（数组 a[],起始位置，中间位置，结束位置，数组 b[])

分数的大小比较与排序

在我们日常生活和学习中，分数的大小比较和排序是一项非常重要的任务。通过对分数的比较和排序，我们可以对学生的学术表现进行评估，也可以对各种评奖评优进行排名和比较。本文将介绍分数的大小比较和排序的方法，并探讨其在实际应用中的意义。

一、分数的大小比较方法

1. 直接比较法

最简单直接的方法是将两个分数进行比较。例如对于两个分数a/b和c/d，可以通过求其通分，然后比较a*d和c*b的大小，来判断两个分数的大小关系。如果a*d大于c*b，那么a/b大于c/d，反之则小于。这种方法的优点是简单直接，适用于两个分数的大小比较。然而，当涉及到多个分数的排序时，这种方法就不太适用了。

2. 转化为小数比较法

另一种常用的比较方法是将分数转化为小数进行比较。对于一个分数a/b，可以将其转化为小数形式a÷b。然后比较转化后的小数的大小关系，即可确定分数的大小。这种方法的优点是简单易懂，适用于多个分数的大小比较和排序。但是需要注意的是，在转化为小数时可能会出现无限循环小数，需要注意精确性和舍入规则的选择，以确保比较结果的准确性。

二、分数的排序方法 1. 冒泡排序法

冒泡排序法是一种常用的排序算法，适用于多个分数的排序。它的基本思想是通过多次比较和交换，将待排序的分数按照从小到大（或从大到小）的顺序逐步排列。具体步骤包括：

- 从第一个分数开始，依次比较相邻的两个分数，如果前者大于后者，则交换它们的位置；

- 继续进行第一步的比较和交换，直到最后一个分数；

- 重复上述步骤，直至所有的分数都按照顺序排列。

2. 插入排序法

插入排序法也是一种常见的排序算法，适用于多个分数的排序。它的基本思想是将待排序的分数逐个插入到已经排序好的部分中，形成一个有序的序列。具体步骤包括：

- 将第一个分数视为已排序序列；

- 取出下一个分数，与已排序序列中的分数从后往前依次比较，找到合适的位置插入；

- 重复上述步骤，直到所有的分数都插入到有序序列中。

百分数和分数的大小比较及互化

一、复习加情境，引入新课

师：同学们，前面我们已经学习了小数、分数、百分数，以及小数和分数的互化，那么我们来回顾一下，如何把53化成小数？如何把0.07化成分数？我们最近又学习了百分数，关于百分数你都知道哪些知识呢？

生：表示一个数是另一个数的百分之几的数，叫做百分数，它也叫百分比、百分率，它是一种特殊的书写方式。

二、探索新知。

1、理解题意。

师：看来同学们对学过的知识掌握地非常不错，老师奖励大家一张知识小卡片，谁来读一读？（你读得非常清楚、流利，请坐！）

师：大家根据你的生活经验来猜一猜，爬行类和兽类哪种动物比较多呢？

生1：爬行类。

生2：兽类。

师：大家都不要着急，老师这里有两条线索，谁来读一读？

生：爬行类约占脊椎动物的6%，兽类约占脊椎动物的2/25

师：你是怎么理解题意的？

生：就是来比较252和6%的大小。

师：接下来就请同学们用自己的方法比一比写在练习本上，看谁想出的方法多？

2、自主探究。 学生尝试比较，教师巡视指导，了解学生的比较方法。

3、汇报交流。

（1）（分数化成百分数）

师：谁愿意汇报一下你的比较方法，说一说是怎样想的，怎样做的。

生： 把252化成百分数。

252＝2×4/25×4=8/100=8％(根据分数的基本性质)

252＝2÷25＝0.08＝8％

因为8％>6％，所以，兽类动物比较多。

师：你能想出这种好办法，真不简单！谁还是这样做的？请来说一说。

师板书。

（2）化成小数。

师：你们还有不同方法吗？

生：可以把它们都化成小数。(根据分数和除法的关系)

2/25＝2÷25＝0.08

6％＝6÷100＝0.06

因为0.08>0.06，所以，2/25>6％，兽类动物比较多。

师：你的想法很有创意，真棒！谁也用了这种方法？

存储管理、查找和排序

班级：软件101 姓名：xxx 学号：xxxxxx 完成日期：2011-12-15

题目：内部排序算法比较

一、 需求分析...

问题描述：通过随机数据比较各算法的关键字比较次数与移动次数。

基本要求：至少比较快速排序与堆排序。对结果进行简单分析

1)、通过随机数据比较各算法的关键字比较次数与移动次数，并对结果进行简单分析。

2)、测试数据：5、8、8、3、9、7

二、概要设计...

快速排序算法：

void QSort (RedType & R[], int s, int t ) {

// 对记录序列R[s..t]进行快速排序

if (s < t-1) { // 长度大于1

pivotloc = Partition(R, s, t);

// 对 R[s..t] 进行一次划分

QSort(R, s, pivotloc-1);

// 对低子序列递归排序，pivotloc是枢轴位置

QSort(R, pivotloc+1, t); // 对高子序列递归排序

}

} // QSort

归并排序算法：

void Merge (RcdType SR[], RcdType &TR[], int i, int m, int n)

{

// 将有序的记录序列 SR[i..m] 和 SR[m+1..n]

// 归并为有序的记录序列 TR[i..n]

for (j=m+1, k=i; i<=m && j<=n; ++k)

{ // 将SR中记录由小到大地并入TR

if (SR[i].key<=SR[j].key) TR[k] = SR[i++];

else TR[k] = SR[j++];