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

Decision mathematics属于A-Level数学中比较小众的模块，它介绍了算法（algorithm）的一般概念和利用流程图或者文本实现算法。

今天要介绍的是如何通过算法来给数字排序，D1中介绍了两种算法：bubble sort 和 quick sort。

Part.1bubble 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 thelist, 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，所以交换位置。

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

39 = 39

保持不变

39＞17

保持不变

17＜24

交换位置

17＜48

交换位置

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

After 2nd pass: 57 72 39 39 24 48 17After 3nd pass: 72 57 39 48 39 24 17After 4thpass: 72 57 48 39 39 24 17No swaps in next pass, so the list is in order.

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

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

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

Part.2quick 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 eachsub-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】2. 把大于39的数字放在39的左边，小于39的数字放在39的右边。通常我们用方框来表示我们已经固定位置的pivot。

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

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

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

Part.3Exam 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

这部分数学模块是很有趣的知识部分