好再下來我們介紹所謂的
泡沫排序法。那什麼叫排序?排序就是說把一些數字 由小到大,或者由大到小的順序把它排好。那
這要怎,在計算機裡怎麼做呢?首先我們要說,到底這些數字放哪裡?那之前我們沒辦法做,- 是因為我們
不知道那麼多數字要怎麼辦。那現在我們有陣列以後,我們就知道要怎麼辦。我們就把這些數- 字,要排序的數字
放在一個陣列裡頭,然後我們對這個陣列做排序,這樣就可以達到這個效果。那
做泡沫排序法怎麼做呢?就是說,我們由左到右,比較兩個相鄰元素。
如果注標比較小的元素比較大,那就交換元素值。換句話說, 你就想想看,如果說,我們有一排同學啊,站在那邊,我們按照高矮調,
調順序的話,我們就從左邊看過來。如果第一個同學跟第二個同學啊 順序不對的話,高矮,那個高矮的順序不對,我們把他調過來。
那基本上就是按照這樣的方法來做。那啊
我們會用兩個迴圈來做,用兩個迴圈來做。第一個迴圈呢,
決定說兩兩交換的範圍,因為我們如果啊,按照由左到右這樣兩兩交換
的方法來做的話,我們就知道說最高的同學會被分配到最右邊去,如果
我們希望就是說左邊比較矮,右邊比較高的話,那我們從左邊到右邊這樣掃過來,每次兩兩- 換的話,
那最高的同學就跑到最右邊去了。但是第二次呢, 在第二次的時候,我們已經知道最高的同學在最右邊了,所以事實上我們
迴圈的範圍呢,跟第一次是不一樣的。我們第二次迴圈的範圍就比較小,會小一個。
所以我們第一層的迴圈呢,決定說做兩兩交換的範圍是在哪裡。
第二層呢就實際上作,說第一層已經決定那個兩兩交換迴圈的範圍,
啊實際上去做這個交換的動作啊。那這實際上的code呢,會長得像這個樣子。
那一開始呢,我們先把我們到底有幾個元素讀進來,這會放到 m 裡頭。
再來呢,我們把這些要排序的數字讀進來。好我們讀進哪裡呢?讀進一個陣列,叫做 n
,所以 n 裡頭呢,就是這些要排序的啊數字。
然後我們進入剛剛所謂的泡沫排序法,這個整個泡沫排序法呢,程式到這裡。
從第9行到第15行,這非常簡單。我們剛剛說第一個
迴圈是決定說你的範圍到哪裡,啊你的範圍到哪裡。
所以呢,我們就看一下說,我們內部迴圈的範圍到哪裡。我們事實上是比較 j , 跟 j+1,
然後呢,我們每一次決定一個 i ,讓 j 從 0一直跑,跑到
i 哈。所以我們就可以想像說,那我們第一次迴圈,那 i 要設多少呢?
答案是設成 m-2, 為什麼是 m-2, 不是 m-1 呢?是因為說 我們將來
i 會當作 j 的上限,所以 我們要比的是 j 跟
j+1, 那 自然而然我們最後一次比的啊,在這個第
一次迴圈最後一個比較,應該是 m-2 跟 m-1。
因為我們這邊有加1,所以說我們的 i 在這個範圍裡頭,就要設成
m-2, 讓這個 裡面這迴圈最後一次執行的時候呢,剛好是比到 m-2 跟 m-1。
好那下一次呢,這個位置迴圈 的比較,的對象就會是
m-3 跟 m-2, 就是剛好符合我們想要的事情,因為
注意到我們陣列是從啊0開始,所以如果你有 m
個元素的話,事實上最後一個 是 m-1, 那 m-1 前面那個呢,是m-2,
就剛好拿來 當裡面這個迴圈的上界啊,就在這裡。
那 m-2 之後呢,它就要每次的遞減,一直往下減。減到什麼時候呢?
減到 i 還大於等於0的時候,所以最後一次呢,i 會等於0。那 i
等於0的時候呢,就是在 0跟1之間交換,就可以了。所以我們這個上下界都把它設好,那裡面就很簡單,就是說你看
n 跟 j, 跟 j+1 的範圍是不是反過來了,如果說 j
比較大的話,那你就把它往右調啊,就是把這 兩個數字把它換過來。那這個換法呢,我們之前也學習過,這是一個相當於片語這樣
的東西。我們另外宣告一個啊暫存的基,那個變數,把它調過來,這樣就可以了。
所以在這邊特別要注意的就是,這些上下界要怎麼設。比如說這個 m-2,那想清楚
到底說最後一次,我到底是讓誰跟誰先交換,那這些上界,下界,把它想清楚來呵。
那這樣程式就不會弄錯了。通常一開始初學者很容易犯的錯誤,就是說這些上下界
設的差異啊並不是很清楚說,到底從哪裡到哪裡。或者說對 陣列從0到
m-1 這個範圍,這個,這個,這個,這個數位結構不清楚。
這很容易寫錯,把它想清楚來,最好是用那個啊 實際上去模擬演練一遍,這個程式怎麼執行,這樣你就清楚了。
那到了最後呢,我們再把 m 啊再把這個 m
個元素全部印出來,就可以了。這時候呢,這個 n [ i
] 就已經全部按照順序排好了。所以如果我們實際上執行的話,
比如說我們輸入10個數字呵,這個10是剛剛的 m,
總共有10個,我們這邊隨便排,隨便排,然後叫它輸出。
那輸出的時候,就按順序排好了,這是一種泡沫排序法啊。那注意到這邊。我們為了方便起見,
就把它們全部寫在一行。那事實上,寫在不同行也是可以的,因為我們之前講過,scanf- 會啊,把這些數字,
反正它就是想辦法,一個一個讀到,讀到為止,這個行讀不到,下一行就要想辦法去讀。
所以啊,那這個結果泡沫排序法就是按照這樣子的要領。
啊,我再強調一次,最重要的就是說它那個兩個迴圈的 上界跟下界,要把它想清楚,這樣程式就不會有問題。
[聲音] [空白_錄音]