Sort

Sort

做排序的手段目前主要有兩種:一、透過交換元素、放置元素的排序演算法:例如quick sort、Shell sort、counting sort、radix sort;二、利用特殊的資料結構:例如priority queue、van Emde Boas tree,只要將資料整個倒進去、整個倒出來即排序完畢。以下只介紹第一種手段的各種演算法。至於第二種手段,可參考本站文件「Data Structure─Priority Queue」。

利用第一種手段來排序時,要先將資料放在array、linked list這種循序性(sequential)的資料結構裡面,然後再實行演算法。如果資料是放在其他資料結構裡面(例如tree),那麼就沒辦法直接利用這種方法排序了。

排序的用處非常多,甚至有些演算法在排序時都會運用到Sort,例如Graham's Scan。

Selection Sort

【待補文字】

Insertion Sort

【待補文字】

Bubble Sort

【待補文字】

Merge Sort

Merge Sort是個利用D&C的例子。言簡意賅吧。【待補文字】

這一題雖然不是 Merge Sort,但是它的解法很像Merge Sort,也用到了D&C,所以特別舉出來為例。

UVa 10810

Quick Sort

細節請查閱演算法的書籍,或上網搜尋「Quick Sort」。這是很有名的排序法。

Quick Sort演算法的陷阱相當多,須考慮資料數值全都相等、判斷式選用小於或小於等於、分割點恰好選到最大值或最小值、遞迴的區段範圍、遞迴的區段很短、……等等問題。大部分書上、網站上的程式碼都有瑕疵,就算是經過Online Judge驗證通過的程式碼也可能是錯誤的,此非危言聳聽,請各位要小心謹慎。編寫Quick Sort的程式碼時,最好是寫一支窮舉所有n-tuple的程式,嘗試各種數據排列的情形,一一排序、驗證。

如果擔心自己寫的程式碼用在正事上不妥當,也可以採用程式語言函式庫內建的Quick Sort。C++ STL的Quick Sort使用方法可以參考本站文件「C/C++函式庫的運用」。

下面兩支程式使用了不同的手法,請查閱。我不能保證正確無誤,也不能保證效率很好。

如果要我列出簡單的範例題目的話,那就是這題了。

UVa 755

Shell Sort

採用Divide and Conquer,以固定間隔取得資料作為一組,各組各自做Insertion Sort,然後減少間隔大小,重複上述動作。【待補文字】

有類似partition的效果,可以有效減少交換的次數。

Shell是一個人名,是發明這個演算法的人,不是殼的意思。

Counting Sort

【待補文字】

Radix Sort

【待補文字】

Flash Sort

【待補文字】

Introspective Sort(Introsort)

【待補文字】