?Stella Crazy A-level Decision mathematics屬于A(yíng)-Level數學(xué)中比較小眾的模塊，它介紹了算法（algorithm）的一般概念和利用流程圖或者文本實(shí)現算法。今天要介紹的是如何通過(guò)算法來(lái)給數字排序。
Part.1 bubble sort
在bubble sort中，我們通過(guò)比較每?jì)蓚€(gè)相鄰數字來(lái)進(jìn)行排序。
■首先介紹一下基本流程：
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.
從已給列表的左邊開(kāi)始，比較每?jì)蓚€(gè)相鄰之間的數字，如果它們有序，保持不變；
如果沒(méi)有排好序，交換他們的位置。 當你完成一個(gè)pass時(shí)，再重復前面的步驟直到我們完成了一個(gè)不需要任何交換位置的pass。
下面我們通過(guò)一個(gè)例子來(lái)解釋一下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:
用這樣的方法以此類(lèi)推完成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.
下一步?jīng)]有任何的位置交換，所以列表已經(jīng)排序完畢。
通過(guò)這個(gè)例題我們可以看出來(lái)，bubble sort 的命名來(lái)源了，每一行圈出相鄰的一組數字，然后形成了bubble形狀。
從這個(gè)例題可以看出來(lái)，當我們的數據變多之后，這個(gè)方比較耗費時(shí)間， 所以接下來(lái)我們來(lái)介紹一個(gè)更快更有效率的算法：quick sort。
Part.2 quick sort
在quick sort中，我們選取一個(gè)pivot把數據分成兩個(gè)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來(lái)解決上面那道例題。
Example：Use a quick sort to arrange these numbers into descending order.
39 57 72 39 17 24 48
■Solution:
1.選擇一個(gè)pivot ，39， 中間的數字?！就ǔＮ覀冇萌?lái)表示選擇的pivot】
2.把大于39的數字放在39的左邊，小于39的數字放在39的右邊。通常我們用方框來(lái)表示我們已經(jīng)固定位置的pivot。
3.繼續在兩個(gè)子表中選擇各自的pivot，重復同樣的步驟。
Each number has been chosen as a pivot, so the list is in order.
在quick sort里面，如果我們的列表或者子列表的數據為偶數，我們選擇中間右邊的數字作為pivot，比如說(shuō)我們一組數據有10個(gè)數字，我們就選擇第6個(gè)數據作為pivot，然后進(jìn)行quick sort。
■Exam Tips:
1. 看清題目中的要求，descending or ascending。
2.在使用bubble sort的時(shí)候，注意我們要一直寫(xiě)出一個(gè)沒(méi)有任何swap的pass才可以結束algorithm，不能因為數據已經(jīng)完成排序就不寫(xiě)出末了的pass。
3.在quick sort中，我們選擇了pivot之后，我們剩下的數據仍然要按照原本的順序寫(xiě)入sub-list。
介紹完了這兩種排序的算法，下面大家就可以嘗試著(zhù)用這兩種方法來(lái)排序下面的一組數據了。
Use a suitable sort to arrange these numbers into ascending order.
21 24 42 29 23 13 8 39 38
這部分數學(xué)模塊是很有趣的知識部分，如果同學(xué)們在學(xué)習的過(guò)程中遇到難點(diǎn)的話(huà)，可以隨時(shí)來(lái)找主頁(yè)君咨詢(xún)。
