#1 TRUSTED LEADER IN INTERNATIONAL EDUCATION

Learn Faster,Study Smarter

Learn For Free Today

企业介绍
创始人寄语
学诚新闻
师资团队
首页 > 关于我们 > 师资团队 > 洪老师

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

【洪老师】  2020-03-05 发布

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

这部分数学模块是很有趣的知识部分,如果同学们在学习的过程中遇到难点的话,可以随时扫码了解。学诚国际教育针对学生的不同年级和不同基础,提供了最丰富的选择;班课和一对一混合学习,科学合理,符合中国学生学习习惯。

cfe2992068c06290c66d6ee75abf770.png