Java 泡沫排序法 - 翻轉工作室

所謂排序法（Sort）即是將一大堆資料，利用某一關鍵內容由最大到最小，或最小到最大依序排列。

吾人可能會認為排序演算法應該不是很重要才對，如果僅排序 100 筆以下 ...  Java 程式設計(一)  ：第 七章 陣列  上一頁    下一頁   7-5泡沫排序法 內容： 7-5-1泡沫排序演算法 7-5-2 範例研討：成績高低排序 7-5-3 自我挑戰：列印股票高低排序 7-5-4 自我挑戰：印出數學成績單 7-5-1泡沫排序演算法 所謂排序法（Sort）即是將一大堆資料，利用某一關鍵內容由最大到最小，或最小到最大依序排列。

吾人可能會認為排序演算法應該不是很重要才對，如果僅排序100筆以下資料，那用什麼演算法都差不了多少；但如果排序一千筆甚至幾十萬筆以上資料時，演算法的排序速度快或慢就變成很重要了。

在計算機科學裡有許多排序的演算法，各種演算法都有其優缺點，本書僅介紹較常用的『泡沫排序法』，至於其他演算法，請參考有關資料結構的書本。

排序法那麼重要嗎？簡單的運用如學生成績排序、暢銷產品排列、營業員業績排行榜...等等，確實在生活領域裡隨時都會遇到排序的問題。

但在計算機科學裡還有一個更重要的運用，即是如欲由幾千萬筆資料內查詢或變更某一筆資料，如何才能以最快速度搜尋到該筆資料，就牽涉到資料排列的問題，即是資料結構的構思。

試想，如欲由一堆雜亂無章的資料內，找尋某一筆資料，若只能由到頭到尾一筆一筆的比對（順序搜尋法），運氣好，第一筆就找到；運氣差，最後一筆才找到，或發現根本沒有該資料。

如果能將所有資料依照大到小或小到大排序，欲搜尋其中一筆資料也許會快許多；此運用方法，於本章7-7節中有範例說明。

      『泡沫排序法』這種最普遍的排序演算法，是最不聰明卻最簡單的方法。

圖7-7為其運作程序（由大到小排序），由陣列第1元素開始（a[0],i=0），作為基準並一個接一個比較所有其他元素，如果比a[0]大的話，則兩者交換。

當所有資料比對完之後，最後結果是a[0]是所有元素之間的最大值；如此表示第1個泡沫已浮上來。

接著，以第2個元素（a[1]）為基準，往下比較所有元素，如果較大的話，兩者相交換。

往下比對完之後，最後a[1]內容會最大，如此表示第2個泡沫已浮上來。

依此類推，總共需比較陣列元素–1次輪迴（i-1），最後即可得到由大到小的排序；另外，由小到大也是如此。

圖7-12泡沫排序法的運作程序 7-5-2範例研討：成績高低排序 （A）程式功能：Ex7_8.java 張老師利用一維陣列存放了班上數學成績，陣列內容為a[]={45,12,89,76,34,65,77,93,70,65,45,89}，請利用泡沫排序法編寫一程式由高到低排列，並印出每回合排列的結果；期望操作介面如下： D:\Java1_book\chap7>javaEx7_8 陣列內容:45 12 89 76 34 65 77 93 第0 回合:93 12 45 76 34 65 77 89 第1 回合:93 89 12 45 34 65 76 77 第2 回合:93 89 77 12 34 45 65 76 第3 回合:93 89 77 76 12 34 45 65 第4 回合:93 89 77 76 65 12 34 45 第5 回合:93 89 77 76 65 45 12 34 第6 回合:93 89 77 76 65 45 34 12 第7 回合:93 89 77 76 65 45 34 12 （B）製作技巧研討： 吾人可利用雙重迴圈製作泡沫排序法的運作程式（如圖7-7所示），外迴圈指定第幾回合（i=0,1,..,a.length），每回合找出一個較大的數值；內迴圈指定每回合所比較的元素（j=i+1,…,a.length）。

如果被比較元素大於指定元素（a[j]>a[i]），則兩元素交換，否則不做任何處理。

其中較困難的是，兩個元素（或稱兩個變數）的內容如何交換，這也是程式設計中較有趣的問題。

兩變數內容交換的情況，就好像有兩個杯子，一個裝啤酒，另一杯裝可樂，這兩個杯子所裝的東西如何交換？其實非常簡單，我們只要再準備第三個杯子（另一個變數），先將第一個杯子的內容（如啤酒）倒入第三個杯子，再將第二杯（如可樂）倒入第一杯，最後再將第三杯（如啤酒）倒入第二杯，如此就完成第一杯與第二杯內容交換。

需聲明一下，程式設計並非用倒入，而是用複製的，如圖7-8所示。

圖7-13兩變數內容交換的運作程序 （C）程式範例： 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 //Ex7_4.java   publicclassEx7_4{    publicstaticvoidmain(Stringargs[]){        inta[]={45,12,89,76,34,65,77,93};        inttemp;          System.out.printf("陣列內容 :"); //顯示原來陣列內容        for(intj=0;jjavaPM7_9 原股票排序順序 : 78.0 72.0 61.0 56.0 87.0  66.0 74.0 88.0 76.0 58.0 65.0 57.0 90.0 78.0 67.0  89.0 56.0 77.0 56.0 87.0 67.0 80.0 77.0 86.0 67.0  75.0 86.0 98.0 88.0 78.0   排序後股票順序: 56.0 56.0 56.0 57.0 58.0  61.0 65.0 66.0 67.0 67.0 67.0 72.0 74.0 75.0 76.0  77.0 77.0 78.0 78.0 78.0 80.0 86.0 86.0 87.0 87.0  88.0 88.0 89.0 90.0 98.0 （B）製作技巧提示： 原PM7_1範例將陣列stock[]宣告成類別變數，同一類別（PM7_6.class）內所有方法（如main()、disp_stock()、swap()）都可以直接引用它。

因此，本範例將兩元素交換的處理程序製作成swap(i,j)函數方法，功能是stock[i]與stock[j]兩元素內容互相交換。

程式虛擬碼提示如下： 宣告類別陣列變數（static doublestock[]={78,72,…}）； 主方法範圍（main()）： 呼叫列印陣列函數（disp_stock()）； 泡沫排序演算法（需呼叫 swap(i,j) 函數）； 呼叫列印陣列函數（disp_stock()）； 列印陣列函數範圍（static voiddisp_stock()）：         for(intj=0;jjavaPM7_7 == 列印排序後成績單 == 411104=90 411105=85 411107=83 411102=80 411108=78 411103=75 411101=70 411106=65 （B）製作技巧提示： 較特殊的地方是泡沫排序法中兩個元素交換程序，必須整筆資料交換，而不是僅成績交換；因此，暫存變數temp需宣告成每筆資料的型態（int[2]）。

演算法重點如下： int[]temp= newint[2]; for(inti=0; i