7-5 泡沫排序法
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},請利用泡沫排序法編寫一程式由高到低排列,並印出每回合排列的結果;期望操作介面如下:
(B)製作技巧研討: 吾人可利用雙重迴圈製作泡沫排序法的運作程式(如圖 7-7 所示),外迴圈指定第幾回合(i=0, 1, .., a.length),每回合找出一個較大的數值;內迴圈指定每回合所比較的元素(j = i+1, …, a.length)。如果被比較元素大於指定元素(a[j] > a[i]),則兩元素交換,否則不做任何處理。其中較困難的是,兩個元素(或稱兩個變數)的內容如何交換,這也是程式設計中較有趣的問題。兩變數內容交換的情況,就好像有兩個杯子,一個裝啤酒,另一杯裝可樂,這兩個杯子所裝的東西如何交換?其實非常簡單,我們只要再準備第三個杯子(另一個變數),先將第一個杯子的內容(如啤酒)倒入第三個杯子,再將第二杯(如可樂)倒入第一杯,最後再將第三杯(如啤酒)倒入第二杯,如此就完成第一杯與第二杯內容交換。需聲明一下,程式設計並非用倒入,而是用複製的,如圖 7-8 所示。
圖 7-13 兩變數內容交換的運作程序 (C)程式範例:
(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 個交易日的收盤價,請依照價格高低順序(由最低到最高順序)印出其內容;期望操作介面如下:
(B)製作技巧提示:
原 PM7_1 範例將陣列 stock[] 宣告成類別變數,同一類別(PM7_6.class)內所有方法(如 main()、disp_stock()、swap())都可以直接引用它。因此,本範例將兩元素交換的處理程序製作成 swap(i, j) 函數方法,功能是 stock[i] 與 stock[j] 兩元素內容互相交換。程式虛擬碼提示如下:
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)},請依照成績由最高排列到最低印出。期望操作介面如下:
(B)製作技巧提示: 較特殊的地方是泡沫排序法中兩個元素交換程序,必須整筆資料交換,而不是僅成績交換;因此,暫存變數 temp 需宣告成每筆資料的型態(int[2])。演算法重點如下:
|
翻轉工作室:粘添壽
Java 程式設計(一) 含程式邏輯
翻轉電子書系列:
|