06. 排序演算法

電腦時常被使用來把資料依序排列。舉例來說，把名字依字母順序排列、依日期排序電子郵件或行程，或是依數量多寡排列物品等等。排序除了可使得我們在找東西時更快速之外，還有許多顯著的好處。例如把全班的成績依高低排序，最低分與最高分就很明顯了。

但若使用錯誤的方法，即使有設備很好、很快速的電腦，將大量的資料正確排序可能還是會花很多時間。還好，有幾種快速的演算法非常適合使用於排序。

【問題】

1. 什麼樣的資料會需要排序？

2. 為什麼排序很重要？

3. 如果資料沒有排序會怎麼樣？

排序概念操作程式 - 以天平找出容器的重量順序

http://bk.chjh.hc.edu.tw/html5/html5_sort_scale/sort_scale.html

按下「開始」之後，利用畫面中央的天平，將畫面上八個瓶子按照大小順序排列，排列後按下「完成」，並檢查你的答案是否正確。

對於順序的排列，如果有更好的方法，可以有效地減少完成所需的時間，以下介紹幾種不同的排序演算法，在每學會一種演算法之後，重新操作一次程式進行瓶子重量的排列

1. 選擇排序法(Selection sort)

先找到最輕的容器並擺在一邊。接下來，再從剩下的容器中挑出最輕的，並也擺到一邊。重復此動作直到所有的容器都被擺到同一邊。

2. 快速排序法(Quick sort)

從全部的物件中隨機挑出一個物件，然後把它放在天平的一端。

然後將它與其他剩餘的物件一一比較，將較輕的放在左側，隨機選出的物件放在中間，較重的則分放在右側。(有可能在結束比較時，兩邊物件的數量不一樣)

選擇其中一側，將該側所有物件重複上面的步驟。再將另一側的物件也做一樣的處理。(記得記住一開始選擇的物件要保持在中間)

剩餘的物件群一直重複這些步驟，直到每一群都只剩一個物件。一旦所有物件群都被分到只剩一個物件，所有物件便會被分成由最輕到最重。

3. 插入排序法(Insertion sort)

從尚未排序的物件群中挑出一個物件，把它插入已排序物件群中正確的位置。隨著一次次的動作，未排序物件群的規模會越來越小，而已排序物件群的規模則會越來越大，直到所有物件都排序完成。玩撲克牌時就常常利用這種方式來理牌。

4. 氣泡排序法(Bubble sort)

一次又一次從頭到尾檢查整個物件群，如果兩個相鄰的物件順序不對，就把它們交換，整個物件群檢查完之後，再重頭開始檢查一次。如果沒有任何物件在檢查名單時被交換，就表示排序完成了。這個方法並不是很有效率，但是對某些人來說這種方法較容易理解。

5. 合併排序法(Merge sort)

首先，將名單隨機分成大小相同的兩個群組(奇數個時則分成大小相近的兩份)。兩個群組都要分別做排序，最後再將兩個群組合併。

合併兩個群組的方法：比較兩個群組最前面的物件，把較小的那個挑出來放入排序群組中。在下圖中，兩組的最前面物件分別是40和60公克，所以下一個就把40公克的物件挑出來放入已排序群組中。

提示：最開始分成兩個群組以後，同樣用合併排序法處理。

快速排序與合併排序都屬於分治法(Divide and Conquer)的一種操作方式，這是目前最好的方法之一。

在已排序的清單中尋找資訊會容易很多。電話簿、字典和書籍索引等都是用字母來排序。試想如果它們沒有經過這樣的排序，我們要找相關資訊時會有多不方便。若是將一串數字(例如一些支出)由小到大進行排列，就可以輕易的在排序的兩端找到最大和最小的數字，如果有數字重複的話那也是一目了然，因為它們一定會被排在一起。

實際上電腦在執行時花了很多的時間在把資料排序。所以，找到快速又有效率的排序方法一直是資訊科學家的重要工作之一。一些比較慢的方法如插入排序法、選擇排序法和泡沫排序法、合併排序法這些速度較快的排序法。舉例來說：如果有十萬筆資料要排序，快速排序法大概比選擇排序法要快上2000倍。若資料總數上升至一百萬筆，那麼兩種排序法所花的時間會差上20000倍。

電腦常常要同時處理上百萬筆資料(很多網站擁有上百萬的訪客量，甚至連一張從便宜的照相機所拍的照片也有超過百萬的像素要處理)。選擇不同的演算法的差異可能是要花費一秒鐘還是五小時來完成一個完全相同的任務。不僅僅是時間上的延遲令人無法忍受，還有其他的成本，比方說要耗上20000倍的電力(如此浪費電力不僅有違環保理念，而且也會減少可攜式裝置的電池壽命)。所以，選擇合適的演算法才能有好的效果。

快速排序法使用到一種方法叫做分治法。在快速排序法中，我們不斷的把物件群組分成較小的兩個群組，然後再對這些較小的部份執行快速排序法。最後，整個物件群組被反覆的分割，直到它們小到可以被簡易的排序。在快速排序法中，物件群被分割到只剩下一個物件，那還需要排序嗎？儘管這些步驟看似十分複雜，但是在實際運行中，快速排序法卻戲劇性地比其他方法快速。分治法所使用的這種觀念稱為遞迴(Recursion)，就是演算法裡會反覆呼叫自己來解決問題。這聽起來很奇怪，但實作起來卻意外的管用。

【延伸】

試算表軟體中，排序與分析的應用 - 試作成績單。