Embedded Files
一、排序簡介
排序（Sort）就是指把一群資料依據某一種特定條件（如銷售量多寡）或順序（如總分高低）重新排列，以便於資料的搜尋或再處理。
資料在經過排序後，會有下列幾點好處：
(1) 資料已完成有規則的排序，較易進行解讀與檢查。
(2) 資料較利於統計及整理。
(3) 可大幅減少資料搜尋的時間。
二、常見的排序演算法
氣泡排序法
排序過程中會依照條件（由小到大或由大到小）比較交換資料，一直到資料排序完成為止。
過程類似水中氣泡慢慢從底部往上浮起般，因此稱為氣泡排序法。
比較方式是由第一個元素開始，逐次依序比較相鄰元素大小，若大小順序有誤，則互相對調後再進行下一個元素的比較。
如此掃瞄過第一回合之後就可確保最後一個元素是位於正確的順序。
接著再逐步進行第二回合掃瞄，直到完成所有元素的排序關係為止。
一資料列共五項，內容分別為6、4、9、8、3。如果要由小到大排序，使用 「氣泡排序法」的步驟過程如下：
實作方式(1)
第一回合掃瞄會先拿第一個元素6和第二個元素4作比較，如果第二個元素小於第一個元素，則作交換的動作（小數往前，大數往後）。
接著再拿6和9作比較。
一直比較相鄰元素並依大小條件交換。
比較完後即可確定最大值在資料列的最後面。
完成第一回合掃瞄後， 可以確定資料列最後一個元素是最大值「9」。
實作方式(2)
第二回合掃瞄亦從頭比較起。
因最後一個元素在第一回合掃瞄時就已確定是資料最大值，故只需再比較3次即可把剩餘資料列元素的最大值，排到剩餘資料列的最後面。
完成第二回合掃瞄後， 也可以確定剩餘資料列元素中的最大值「8」會在倒數第二個位置。
實作方式(3)
第三回合掃瞄完，就會完成三個值（6、8、9）的排序。
實作方式(4)
第四回合掃瞄完，即可完成所有排序。
由此可知5 個元素的氣泡排序法必須執行5-1 回合掃瞄，第一回合掃瞄需比較5-1 次，各回合次數加總共比較4+3+2+1= 10 次。
任意挑選班上五位同學，根據各人身高與體重，計算BMI 值；再以氣泡排序法，由大而小排出BMI 值順序，應該如何進行呢？
執行步驟流程圖
2.選擇排序法
不斷地在未排序的資料列中，找出最小值或最大值，將其放入已排序的資料列中，直到所有的資料均已排序完成為止。
通常「放到已排序的資料末端」，有一個簡便的作法，就是將找到之最小值的元素，與未排序的資料列中第一個元素交換即可。
選擇排序法－流程
(1) 從未排序的資料列中找到最小值的元素。
(2) 將此元素與未排序資料的第一個元素交換。
(3) 重複以上動作直到沒有未排序的資料為止。
例如有一資料列共五項，內容分別為6、4、9、8、3。如果要由小到大排序：
實作方式(1)
首先找到此數列中最小值後與第一個元素交換。
實作方式(2)
接著從第二個值找起，找到此數列中（不包含第一個）的最小值，再和第二個值交換。
實作方式(3)
接著從第三個值找起，找到此數列中（不包含第一、二個）的最小值，再和第三個值交換。
實作方式(3)
最後從第四個值找起，找到此數列中（不包含第一、二、三個）的最小值，再和第四個值交換，則此排序完成。
選擇排序每次交換一對元素，它們當中至少有一個將被移到已排序資料列的末端，因此對n 個元素進行排序總共進行至多n-1 次交換。
實作演練
任意挑選五位同學比較身高（由矮而高排列），依照選擇排序法，可以如何進行或做哪些調整呢？請互相討論並發表分享。
執行步驟流程圖
氣泡排序法分析
最好情況只需完成第一回合的一次掃瞄，所以只做了第一回合的n-1 次比較。
最壞情況及平均情況比較的次數相同：(n-1)+(n-2)+(n-3)+⋯⋯+3+2+1=n(n-1)/2 次。
此排序法適用於資料量小或有部分資料事先就已經過排序（可減少交換次數）。
選擇排序法分析
無論是最好清況、最壞情況及平均情況都需要找到各回合的最大值（或最小值）。
因此其比較次數皆為：(n-1)+(n-2)+(n-3)+⋯⋯+3+2+1=n(n-1)/2 次。
此排序法適用於資料量小或有部分資料事先就已經過排序（可減少交換次數）。
Page updated
Report abuse