Stella Crazy A-level Decision mathematics属于A-Level数学中比较小众的模块，它介绍了算法（algorithm）的一般概念和利用流程图或者文本实现算法。今天要介绍的是如何通过算法来给数字排序。
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 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 intodescending 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 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 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。
■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
这部分数学模块是很有趣的知识部分，如果同学们在学习的过程中遇到难点的话，可以随时来找主页君咨询。
