[Java] java.util.Arrays 中使用的 sort 采用的算法 (转)

http://book.douban.com/annotation/15154366/
Q: java.util.Arrays 中使用的 sort 采用的是什么算法?
 
A: java中Arrays.sort使用了两种排序方法,quick sort 和优化的 merge sort。
 
Q: 为什么采用两种排序算法?
 
A: quick sort 主要是对哪些基本类型数据(int, short, long, float, double等)排序, 而 merge sort 用于对对象类型进行排序。
 
Q: quick sort 在统计意义上效率比 merge sort 高,为何不都采用 quick sort ?
 
A: 概括的说,一个是稳定性,一个是移动次数。使用不同类型的排序算法主要是由于 quick sort 是不稳定的,而 merge sort 是 stable 的。这里的 stable 是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列(保序性)。对于基本数据类型,稳定性没有意义。而对于对象类型,稳定性是比较重要的,因为对象相等的判断可能只是判断关键属性,最好保持相等对象的非关键属性的顺序与排序前一直;另外一个原因是由于合并排序相对而言比较次数比快速排序少,移动(对象引用的移动)次数比快速排序多,而对于对象来说,比较一般比移动耗时。
 
merge sort
 
(1)最坏时间复杂度是 O(nlgn);
 
(2)平均时间复杂度是 O(nlgn);
 
(3)空间复杂度是 O(1)。
 
quick sort
 
(1)最坏时间复杂度是 O(n^2);
 
(2)平均时间复杂度是 O(nlgn);
 
(3)空间复杂度是 O(n)。
 
验证了一下 java.util.Arrays.sort(arrayName) 的时间复杂度,程序如下:
 
  1. /* constant variables */
  2. final int NUM = 10;
  3. final int OFFSET = 2;
  4. final int LOOP = 100000;
  5. /* arrays */
  6. int[][] array = new int[NUM][];
  7. long[] start = new long[NUM];
  8. long[] end = new long[NUM];
  9. long[] cost = new long[NUM];
  10. /* initialization */
  11. for (int i = 0; i < array.length; ++i) {
  12. array[i] = new int[1 << (i * OFFSET)];
  13. }
  14. for (int i = 0; i < array.length; ++i) {
  15. for (int j = 0; j < array[i].length; ++j) {
  16. array[i][j] = (int)(Math.random());
  17. }
  18. }
  19. /* sorting */
  20. for (int count = 0; count < LOOP; ++count) {
  21. for (int i = 0; i < array.length; ++i) {
  22. start[i] = System.currentTimeMillis();
  23. Arrays.sort(array[i]);
  24. end[i] = System.currentTimeMillis();
  25. cost[i] += end[i] - start[i];
  26. }
  27. }
  28. /* output */
  29. for (int i = 0; i < cost.length; ++i) {
  30. System.out.println(
  31. "n = " + array[i].length +
  32. ", time = " + cost[i] / 1000.0
  33. );
  34. }
 
对不同规模n的数组,分别进行10万次排序,统计10万次排序的总时间,结果如下:
 
n = 1, time = 0.013s
 
n = 4, time = 0.011s
 
n = 16, time = 0.029s
 
n = 64, time = 0.066s
 
n = 256, time = 0.198s
 
n = 1024, time = 0.797s
 
n = 4096, time = 3.005s
 
n = 16384, time = 12.101s
 
n = 65536, time = 48.101s
 
n = 262144, time = 192.174s
http://book.douban.com/annotation/15154366/
上一篇:Spring Boot (一) 校验表单重复提交


下一篇:【一个小功能】从js判断ie版本,浅谈navigator对象的appName属性