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>java Ex7_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

 

public class Ex7_4 {

    public static void main(String args[]) {

        int a[] = {45, 12, 89, 76, 34, 65, 77, 93};

        int temp;

 

        System.out.printf("陣列內容 : ");  //顯示原來陣列內容

        for(int j=0; j<a.length; j++)

             System.out.printf("%d  ", a[j]);

        System.out.printf("\n");

 

        for (int i=0; i<a.length; i++) {

            for (int j=i+1; j<a.length; j++) {

                if (a[i] < a[j]) {

                    temp = a[i];

                    a[i] = a[j];

                    a[j] = temp;

                }

            }

            System.out.printf("第 %d 回合: ", i);

            for(int j=0; j<a.length; j++)

                System.out.printf("%d  ", a[j]);

            System.out.printf("\n");

        }

    }

}

(D)程式重點說明：

(1) 第 13~25 行：『for(int i=0; i<a.length; i++) { ….}』。外迴圈，指定排序的回合。

(2) 第 14~20 行：『for(int j=i+1; j<a.length; j++) {…}』。內迴圈，指定每回合依序比較的元素。

(3) 第 15~19 行：『if(a[i] <a[j] { …})。基準元素比被比較元素小的話，則兩元素內容交換。

(4) 第 16~18 行：『temp=a[i]; a[i] = a[j]; a[j]=temp』。利用 temp 變數，將元素內容交換。

7-5-3 自我挑戰：列印股票高低排序

（A）程式功能：PM7_8.java

延續 PM3_1 範例，增加一項功能；其利用陣列 stock[] = {78, 72, 61, 56, 87, 66, 74, 88, 76, 58, 65, 57, 90, 78, 67, 89, 56, 77, 56, 87, 67, 80, 77, 86, 67, 75, 86, 98, 88, 78}; 儲存台積電最近 30 個交易日的收盤價，請依照價格高低順序（由最低到最高順序）印出其內容；期望操作介面如下：

G:\Examples\chap7>java PM7_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 double stock[]={78, 72,…}）；

主方法範圍（main()）：

呼叫列印陣列函數（disp_stock()）；

泡沫排序演算法（需呼叫 swap(i, j) 函數）；

呼叫列印陣列函數（disp_stock()）；

列印陣列函數範圍（static void disp_stock()）：

        for(int j=0; j<stock.length; j++) {

             System.out.printf("%.1f  ", stock[j]);

             if((j+1)%10 == 0)

                 System.out.printf("\n");

        }

元素交換函數範圍（static void swap(int x, int y)）：

        double temp;

        temp = stock[x];

        stock[x] = stock[y];

        stock[y] = temp;

7-5-4 自我挑戰：印出數學成績單

（A）程式功能：PM7_9.java

數學老師利用一個二維陣列儲存某一班級學生的成績，score[][] = {{411101, 70}, {411102, 80}, {411103, 75}, {411104, 90}, {411105, 85}, {4111106, 65}, {411107, 83}, {411108, 78}, {411109, 67}, (411110, 72)}，請依照成績由最高排列到最低印出。期望操作介面如下：

G:\Examples\chap7>java PM7_7

== 列印排序後成績單 ==

411104 = 90

411105 = 85

411107 = 83

411102 = 80

411108 = 78

411103 = 75

411101 = 70

411106 = 65

（B）製作技巧提示：

較特殊的地方是泡沫排序法中兩個元素交換程序，必須整筆資料交換，而不是僅成績交換；因此，暫存變數 temp 需宣告成每筆資料的型態（int[2]）。演算法重點如下：

int[] temp = new int[2];

for(int i=0; i<score.length; i++) {

for(int j=i+1; j<score.length; j++) {

if(score[i][1] < score[j][1]) {

temp = score[i];

score[i] = score[j];

score[j] = temp;

}

}

}

翻轉工作室：粘添壽

 

Java 程式設計(一) 含程式邏輯

 

 

翻轉電子書系列：