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的用法很簡單,以下舉幾個例子:

排序數值

final int SIZE = 20;
final Integer[] integers = new Integer[SIZE];
for (int i = 0; i < SIZE; ++i) {
    integers[i] = (int) Math.floor(Math.random() * 100);
}
final MagicSort<Integer> ms = new MagicSort<>(integers);

ms.setCallback(data -> {
    System.out.println("排序完成:" + Arrays.toString(data));
});
ms.setComparator((a, b) -> {
    try {
	Thread.sleep(10); //模擬複雜的計算需要的延遲時間
    } catch (Exception ex) {

    }
    return a - b;
});
new Thread(ms::sort).start(); //計算排序的執行緒

new Thread(() -> { //顯示排序進度的執行緒
    while (true) {
	final double progress = ms.getProgress();
	System.out.println("目前進度:" + progress * 100 + "%");
	if (progress == 1) {
	    break;
	}
    }
}).start();

執行結果:

目前進度:0.0%
目前進度:5.0%
目前進度:5.0%
目前進度:20.0%
目前進度:25.0%
目前進度:25.0%
目前進度:25.0%
目前進度:50.0%
目前進度:50.0%
目前進度:55.00000000000001%
目前進度:55.00000000000001%
目前進度:65.0%
目前進度:65.0%
目前進度:100.0%
排序完成:[4, 11, 12, 13, 44, 47, 49, 49, 55, 61, 65, 68, 71, 74, 75, 85, 86, 87, 92, 98]

排序包含數字的字串

將含有數字的字串(例如:圖片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,可以用來排序包含數字的字串,舉例:

final List<String> stringList = new ArrayList<>();
stringList.add("第1章");
stringList.add("第1-2章");
stringList.add("第1-3章");
stringList.add("第1-4章");
stringList.add("第1-10章");
stringList.add("第1-11章");
stringList.add("第2-1章");
stringList.add("第2-2章");
stringList.add("第2-3章");
stringList.add("第2-4章");
stringList.add("第2-10章");
stringList.add("第2-12章");
stringList.add("第2-33章");
stringList.add("第3-1章");
stringList.add("第3-10章");
stringList.add("第10-1章");
stringList.add("第10-2章");
stringList.add("第10-15章");
stringList.add("第10-15-1章");
stringList.add("第10-15-2章");

// 隨機打亂
Collections.shuffle(stringList);
System.out.println("待排序:" + stringList);

// 內建排序
Collections.sort(stringList);
System.out.println("內建排序:" + stringList);

// 使用StringWithNumberComparator來排序
Collections.sort(stringList, StringWithNumberComparator.getInstance());
System.out.println("StringWithNumberComparator排序:" + stringList);

程式執行結果為:

待排序:[第10-15-2章, 第1-2章, 第2-4章, 第2-33章, 第1章, 第1-4章, 第2-3章, 第1-11章, 第10-1章, 第3-1章, 第2-10章, 第2-2章, 第1-3章, 第10-15章, 第10-2章, 第10-15-1章, 第2-1章, 第2-12章, 第1-10章, 第3-10章]
內建排序:[第1-10章, 第1-11章, 第1-2章, 第1-3章, 第1-4章, 第10-15-1章, 第10-15-2章, 第10-15章, 第10-1章, 第10-2章, 第1章, 第2-10章, 第2-12章, 第2-1章, 第2-2章, 第2-33章, 第2-3章, 第2-4章, 第3-10章, 第3-1章]
StringWithNumberComparator排序:[第1章, 第1-2章, 第1-3章, 第1-4章, 第1-10章, 第1-11章, 第2-1章, 第2-2章, 第2-3章, 第2-4章, 第2-10章, 第2-12章, 第2-33章, 第3-1章, 第3-10章, 第10-1章, 第10-2章, 第10-15章, 第10-15-1章, 第10-15-2章]

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

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

使用OrderComparator來合併多個Comparator。

final File directory = new File("/home/magiclen/proguard5.2.1/docs").getAbsoluteFile();
final File[] files = directory.listFiles();
MagicSort<File> ms = new MagicSort<>(files);
ms.setComparator(OrderComparator.getInstance(FileTypeComparator.getInstance(), FileNameComparator.getInstance()));
ms.setCallback(data -> {
    Arrays.stream(data).forEach(System.out::println);
});
new Thread(ms::sort).start();

執行結果為:

/home/magiclen/proguard5.2.1/docs/manual
/home/magiclen/proguard5.2.1/docs/style.css
/home/magiclen/proguard5.2.1/docs/checkmark.gif
/home/magiclen/proguard5.2.1/docs/drop1.gif
/home/magiclen/proguard5.2.1/docs/drop2.gif
/home/magiclen/proguard5.2.1/docs/drop3.gif
/home/magiclen/proguard5.2.1/docs/screenshot_console.gif
/home/magiclen/proguard5.2.1/docs/screenshot_console_small.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui1.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui2.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui3.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui4.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui5.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui6.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui7.gif
/home/magiclen/proguard5.2.1/docs/screenshot_gui8.gif
/home/magiclen/proguard5.2.1/docs/screenshots_gui_small.gif
/home/magiclen/proguard5.2.1/docs/steel.gif
/home/magiclen/proguard5.2.1/docs/title.gif
/home/magiclen/proguard5.2.1/docs/FAQ.html
/home/magiclen/proguard5.2.1/docs/GPL.html
/home/magiclen/proguard5.2.1/docs/GPL_exception.html
/home/magiclen/proguard5.2.1/docs/acknowledgements.html
/home/magiclen/proguard5.2.1/docs/alternatives.html
/home/magiclen/proguard5.2.1/docs/downloads.html
/home/magiclen/proguard5.2.1/docs/feedback.html
/home/magiclen/proguard5.2.1/docs/index.html
/home/magiclen/proguard5.2.1/docs/license.html
/home/magiclen/proguard5.2.1/docs/main.html
/home/magiclen/proguard5.2.1/docs/quality.html
/home/magiclen/proguard5.2.1/docs/results.html
/home/magiclen/proguard5.2.1/docs/screenshots.html
/home/magiclen/proguard5.2.1/docs/sections.html
/home/magiclen/proguard5.2.1/docs/testimonials.html
/home/magiclen/proguard5.2.1/docs/title.html
/home/magiclen/proguard5.2.1/docs/favicon.ico
/home/magiclen/proguard5.2.1/docs/android_shades.png
/home/magiclen/proguard5.2.1/docs/dexguard.png
/home/magiclen/proguard5.2.1/docs/guardsquare.png
/home/magiclen/proguard5.2.1/docs/sflogo.png
/home/magiclen/proguard5.2.1/docs/proguard.appdata.xml

深入認識排序演算法

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

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