Lab Array

Study Display 6.1, and then write a program that can sort numbers in ascending order.

• 氣泡排序法

顧名思義，就是排序時，最大的元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方法，將大的元素交換至右端，所以大的元素會不斷的往右移動，直到適當的位置為止。

基本的氣泡排序法可以利用旗標的方式稍微減少一些比較的時間，當尋訪完陣列後都沒有發生任何的交換動作，表示排序已經完成，而無需再進行之後的迴圈比較與交換動作，例如：

排序前：95 27 90 49 80 58 6 9 18 50

1. 27 90 49 80 58 6 9 18 50 [95] 95浮出
2. 27 49 80 58 6 9 18 50 [90 95] 90浮出
3. 27 49 58 6 9 18 50 [80 90 95] 80浮出
4. 27 49 6 9 18 50 [58 80 90 95] ......
5. 27 6 9 18 49 [50 58 80 90 95] ......
6. 6 9 18 27 [49 50 58 80 90 95] ......
7. 6 9 18 [27 49 50 58 80 90 95] 由於接下來不會再發生交換動作，排序提早結束

在上面的例子當中，還加入了一個觀念，就是當進行至i與i+1時沒有交換的動作，表示接下來的i+2至n已經排序完畢，這也增進了氣泡排序的效率。

參考網頁
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/SelectionInsertionBubble.htm