锦秋A-Level,雅思+A-Level+英国留学!
咨询热线:400-966-9730
留学院校库
官方微信 官方微信
官方微博 官方微博
ALP

首页 >  考试技巧 > A-level数学:如何通过算法来给数字排序?

A-level数学:如何通过算法来给数字排序?

来源:      浏览:      发布日期:2019-03-29 10:02

返回列表

在A-level数学学习中,有很多的知识点都需要详细了解,比如微积分、统计学等,今天,锦秋小编将要带大家了解的是Decision mathematics部分,它属于A-Level数学中比较小众的模块,它介绍了算法(algorithm)的一般概念和利用流程图或者文本实现算法。如何通过算法来给数字排序,D1中介绍了两种算法: bubble sort 和 quick sort。

Part.1 bubble sort

在bubble sort中,我们通过比较每两个相邻数字来进行排序。

■ 首先介绍一下基本流程:

1. Start at the beginning of the list. Pass through the list and compare adjacent values. For each pair of values

■  If they are in order, leave them

■  If they are not in order, swap them.

2. When you get to the end of the list, repeat step 1.

3. When a pass is completed without any swaps, the list is in order.

从已给列表的最左边开始,比较每两个相邻之间的数字,如果它们有序,保持不变;

如果没有排好序,交换他们的位置。 当你完成一个pass时,再重复前面的步骤直到我们完成了一个不需要任何交换位置的pass。

下面我们通过一个例子来解释一下bubble sort。

Example:Use a bubble sort to arrange these numbers into descending order.

39    57    72    39    17    24    48

■ 首先比较组相邻的数字 39 和 57 ,57>39,所以交换位置。

所以我们的列表变成了57   39    72    39    17    24    48

■ 然后我们比较第二组相邻的数字 39 和 72 ,72>39,所以交换位置。

按照这样的规则我们继续比较剩下的几组相邻的数字。

A-level数学

39 = 39   保持不变

39>17   保持不变

17<24   交换位置

17<48    交换位置

After the first pass:

A-level数学

用这样的方法以此类推完成2nd pass, 3rd pass,4th pass, 5th pass…

After 2nd pass:  57  72  39  39  24  48  17

After 3nd pass:  72  57  39  48  39  24  17

After 4th  pass:  72  57  48  39  39  24  17

No swaps in next pass, so the list is in order.  

下一步没有任何的位置交换,所以列表已经排序完毕。

通过这个例题我们可以看出来,bubble sort 的命名来源了,每一行圈出相邻的一组数字,然后形成了bubble形状。

从这个例题可以看出来,当我们的数据变多之后,这个方法会比较耗费时间, 所以接下来我们来介绍一个更快更有效率的算法:quick sort。

Part.2 quick sort

在quick sort中,我们选取一个pivot把数据分成两个sub-lists, 大于pivot的和小于pivot的数据。然后再在子表中继续选取pivot分成更多的子表。

■ 基本流程:

1. Choose the item at the mid-point of the list to be the first pivot.

2. Write down all the items that are less than the pivot, keeping their order, in a sub-list.

3. Write down the pivot.

4. Write down the remaining items (those greater than the pivot) in a sub-list.

5. Apply steps 1 to 4 to each sub-list.

6. When all items have been chosen as pivots, stop.

下面我们用quick sort来解决上面那道例题。

Example:Use a quick sort to arrange these numbers into descending order.

39    57    72    39    17    24    48

■ Solution:

1. 选择一个pivot ,39, 中间的数字。【通常我们用圈来表示选择的pivot】

A-level数学

2. 把大于39的数字放在39的左边,小于39的数字放在39的右边。通常我们用方框来表示我们已经固定位置的pivot。

A-level数学

3. 继续在两个子表中选择各自的pivot,重复同样的步骤。

A-level数学

Each number has been chosen as a pivot, so the list is in order.

在quick sort里面,如果我们的列表或者子列表的数据为偶数,我们选择中间右边的数字作为pivot,比如说我们一组数据有10个数字,我们就选择第6个数据作为pivot,然后进行quick sort。

Part.3 Exam Tips

■ Exam Tips:

1. 看清题目中的要求,descending or ascending。

2. 在使用bubble sort的时候,注意我们要一直写出一个没有任何swap的pass才可以结束algorithm,不能因为数据已经完成排序就不写出最后的pass。

3. 在quick sort中,我们选择了pivot之后,我们剩下的数据仍然要按照原本的顺序写入sub-list。

介绍完了这两种排序的算法,下面大家就可以尝试着用这两种方法来排序下面的一组数据了。

Use a suitable sort to arrange these numbers into ascending order.

21   24   42   29   23   13   8   39   38

这部分数学模块是很有趣的知识部分,如果同学们在学习的过程中遇到难点的话,可以随时扫码关注锦秋A-level,进行了解。锦秋A-Level学院作为隶属于新航道国际教育集团的高端子品牌,专为有志于申请英国G5及英澳高校的中学生设计,紧抓中国学生理科优势,进行课程组合化。开设数学、物理、化学、生物、经济学、会计学等课程,帮助学生以优异成绩申请更好的大学。

 

推荐阅读

2022年QS世界大学排名(部分院校) more
大学名称 QS排名
A-level考培+雅思+留学申请
爱德思授权考点
助力申请世界大学本科
新航道17年专注于国际化语言教育和留学考培+申请
专职助教+留学服务
专职讲师教学+助教服务

服务热线:400-966-9730

邮箱:alevel@xhd.cn

地址:北京海淀区丹棱街6号丹棱soho九层901