Java 内置的排序方法无法在异步线程下进行工作,因为没有 Callback 的机制,如果将排序工作丢给另外一个线程运行的话,会不知道排序程序究竟何时会跑完。写程序的时候,有时必须排序庞大的数据,如果未将排序单独丢给另一个线程的话,会造成程序停顿,又因 Java 内置的排序方法,会使用到递归,在数据量大的时候,会用到很多 Stack(堆栈)空间,有可能会导致 Stack Overflow。所以为了解决 Java 内置的排序方式太阳春的问题,就需要 MagicSort 来帮忙了。
MagicSort 可以排序任何型态的对象数组(不能排序 Collection),有 Callback 的机制,支持异步排序。使用了非递归的快速排序法(Iterative Quick Sort)加上选择排序法(Selection Sort)来排序数据,排序速度还算不错。除此之外,它还能实时回报排序进度。
下载 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 来排序。
补充一下。StringWithNumberComparator 的排序方式其实也可以称为「自然排序」,但是在 Java 编程语言中,「自然排序」其实已有内置比较器,即 Comparator.naturalOrder(),不过 Java 内置的这个自然排序实际上是字典排序。
依照文件类型和文件名称来排序文件
使用 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
深入认识排序算法
若您想要了解排序算法的原理,可以参考这篇文章:
