MagicSort─支援非同步排序與計算排序進度的Java排序函式庫


Java內建的排序方法無法在非同步執行緒下進行工作,因為沒有Callback的機制,如果將排序工作丟給另外一個執行緒執行的話,會不知道排序程式究竟何時會跑完。寫程式的時候,有時必須排序龐大的資料,如果未將排序單獨丟給另一個執行緒的話,會造成程式停頓,又因Java內建的排序方法,會使用到遞迴,在資料量大的時候,會用到很多Stack(堆疊)空間,有可能會導致Stack Overflow。所以為了解決Java內建的排序方式太陽春的問題,就需要MagicSort來幫忙了。

MagicSort可以排序任何型態的物件陣列(不能排序Collection),有Callback的機制,支援非同步排序。使用了非遞迴(Recursive)的快速排序法(Iterative Quick Sort)加上選擇排序法(Selection Sort)來排序資料,排序速度還算不錯。除此之外,它還能即時回報排序進度。

下載MagicSort

https://github.com/magiclen/MagicSort

本站下載

使用MagicSort

MagicSort的用法很簡單,以下舉幾個例子:

排序數值

執行結果:

排序包含數字的字串

將含有數字的字串(例如:圖片1,圖片2,第1章,第2章)做排序,應該是許多人寫程式都會經歷的項目。但是如果您有在注意的話,會發現許多程式語言內建的排序功能,在排序字串的時候,會有很奇怪的情形發生。舉個例子,若有個字串清單,假設正確排序的結果應該要是「1,2,3,10,11,20,21」,但許多程式跑出來卻會得到「1,10,11,2,20,21,3」這種結果,而這同時也是很多檔案瀏覽器排序檔名時會出現的問題。

那究竟是什麼原因造成這種詭異的排序現象呢?答案就是排序字串時用的演算法啦,一般程式在排序字串,是取兩個字串出來,從左到右比較字串中的每個字元的字元值大小,如果是遞增排序,那麼就是字元值先比出較小者會排在前面。如果這兩個字串還沒比出結果就有一個字串已經先把字元讀完了,如果是遞增排序,較長的字串就會被排在後面。

這樣的演算法會有很大的問題,那就是字串中的數字,並沒有數值的概念,就算數字看起來很大,甚至是將「111111111」拿來跟「2」比,在遞增排序的情況下,因為字元「2」的值大於字元「1」的值,所以會發現2被排在111111111之前,這樣的結果真是讓人看得匪夷所思。

為了解決這個問題,使用別的演算法來排序字串是必須的。通常我們在排序東西,會參考那些東西身上的一些屬性,判斷誰應該要在前面誰應該要在後面。舉幾個實際的例子:「身高高的站後面,矮的站前面」,這就是一個藉由「身高」排序「人」的演算法;「重的擺下面,輕的擺上面」,這就是一個藉由「重量」排序「物體」的演算法;「長相好看的薪水拿多一點」,這是一個藉由「長相」排序「人」的演算法。「身高」、「重量」,都是很明確的數值,只要知道大小,自然就可以排序。但是「長相」就比較抽象了,沒辦法直接講出明確的數值,因此要想辦法將它數值化(雙眼皮的加一分、笑起來有酒窩加一分),才能夠進行排序。同樣的,「字串」也要先經過數值化才有辦法排序,但是數值化的方式絕對不是像最一開始提到的,直接取所有的字元值出來比較,而是要將數字和非數字分開來計算。

MagicSort函式庫提供了StringWithNumberComparator,可以用來排序包含數字的字串,舉例:

程式執行結果為:

當然,也可以將資料轉成陣列使用MagicSort排序

依照檔案類型和檔案名稱排序檔案

使用OrderComparator來合併多個Comparator。

執行結果為:

深入認識排序演算法

若您想要了解排序演算法的原理,可以參考這篇文章:

https://magiclen.org/sorting-algorithm/

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章