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

　　 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。

　　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
　　这部分数学模块是很有趣的知识部分，如果同学们在学习的过程中遇到难点的话，可以随时来找主页君咨询。