■ 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，所以交換位置。

按照這樣的規則我們繼續比較剩下的幾組相鄰的數字。

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 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】

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

這部分數學模塊是很有趣的知識部分，如果同學們在學習的過程中遇到難點的話，可以隨時來找主頁君諮詢。

想在大考中衝A，想了解考前衝刺課，歡迎掃描諮詢！！

聲明：該文觀點僅代表作者本人，搜狐號系信息發佈平臺，搜狐僅提供信息存儲空間服務。