现在的位置: 首页 > 综合 > 正文

Java常用排序算法及性能测试集合

2013年01月26日 ⁄ 综合 ⁄ 共 3130字 ⁄ 字号 小 中 大 ⁄ 评论关闭

转载自：http://blog.csdn.net/sunxing007/article/details/9005471

周末天气不好，在家无事，把常用排序算法理了一遍，收获不小，特写文章纪念。这些算法在学校的时候学过一遍，很多原理都忘记了。现在再回过头理解，结合自己的体会， 选用最佳的方式描述这些算法，以方便理解它们的工作原理和程序设计技巧。本文适合做java面试准备的材料阅读。

先附上一个测试报告：

[css] view
plaincopy

  1. Array length: 20000  
  2. bubbleSort : 766 ms  
  3. bubbleSortAdvanced : 662 ms  
  4. bubbleSortAdvanced2 : 647 ms  
  5. selectSort : 252 ms  
  6. insertSort : 218 ms  
  7. insertSortAdvanced : 127 ms  
  8. insertSortAdvanced2 : 191 ms  
  9. binaryTreeSort : 3 ms  
  10. shellSort : 2 ms  
  11. shellSortAdvanced : 2 ms  
  12. shellSortAdvanced2 : 1 ms  
  13. mergeSort : 3 ms  
  14. quickSort : 1 ms  
  15. heapSort : 2 ms  

通过测试，可以认为，冒泡排序完全有理由扔进垃圾桶。它存在的唯一理由可能是最好理解。希尔排序的高效性是我没有想到的；堆排序比较难理解和编写，要有宏观的思维。

[java] view
plaincopy

  1. package algorithm.sort;  
  2.   
  3. import java.lang.reflect.Method;  
  4. import java.util.Arrays;  
  5. import java.util.Date;  
  6.   
  7. /** 
  8.  * Java常用排序算法及性能测试集合 
  9.  *  
  10.  * 本程序集合涵盖常用排序算法的编写，并在注释中配合极其简单的特例讲解了各种算法的工作原理，以方便理解和吸收； 
  11.  * 程序编写过程中吸收了很多维基百科和别人blog上面的例子，并结合自己的思考，选择或改进一个最容易让人理解的写法。 
  12.  * 同时包含一个集中式的性能测试和正确性测试方法，方便观测。 
  13.  * @author http://blog.csdn.net/sunxing007 
  14.  * 转载请注明来自http://blog.csdn.net/sunxing007 
  15.  */  
  16. public class SortUtil {  
  17.     // 被测试的方法集合  
  18.     static String[] methodNames = new String[]{  
  19.         "bubbleSort",  
  20.         "bubbleSortAdvanced",  
  21.         "bubbleSortAdvanced2",  
  22.         "selectSort",  
  23.         "insertSort",  
  24.         "insertSortAdvanced",  
  25.         "insertSortAdvanced2",  
  26.         "binaryTreeSort",  
  27.         "shellSort",  
  28.         "shellSortAdvanced",  
  29.         "shellSortAdvanced2",  
  30.         "mergeSort",  
  31.         "quickSort",  
  32.         "heapSort"  
  33.     };  
  34.     public static void main(String[] args) throws Exception{  
  35.         //correctnessTest();  
  36.         performanceTest(20000);  
  37.     }  
  38.       
  39.     /** 
  40.      * 正确性测试<br> 
  41.      * 简单地测试一下各个算法的正确性<br> 
  42.      * 只是为了方便观测新添加的算法是否基本正确；<br> 
  43.      * @throws Exception 主要是反射相关的Exception；<br> 
  44.      */  
  45.     public static void correctnessTest() throws Exception{  
  46.         int len = 10;  
  47.         int[] a = new int[len];  
  48.         for(int i=0; i<methodNames.length; i++){  
  49.             for(int j=0; j<a.length; j++){  
  50.                 a[j] = (int)Math.floor(Math.random()*len*2);  
  51.             }  
  52.             Method sortMethod = null;  
  53.             sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());  
  54.             Object o = sortMethod.invoke(null, a);  
  55.             System.out.print(methodNames[i] + " : ");  
  56.             if(o==null){  
  57.                 System.out.println(Arrays.toString(a));  
  58.             }  
  59.             else{  
  60.                 //兼顾mergeSort，它的排序结果以返回值的形式出现；  
  61.                 System.out.println(Arrays.toString((int[])o));  
  62.             }  
  63.         }  
  64.     }  
  65.       
  66.     /** 
  67.      * 性能测试<br> 
  68.      * 数组长度用参数len传入，每个方法跑20遍取耗时平均值；<br> 
  69.      * @param len 数组长度 建议取10000以上，否则有些算法会显示耗时为0；<br> 
  70.      * @throws Exception 主要是反射相关的Exception；<br> 
  71.      */  
  72.     public static void performanceTest(int len) throws Exception{  
  73.         int[] a = new int[len];  
  74.         int times = 20;  
  75.           
  76.         System.out.println("Array length: " + a.length);  
  77.         for(int i=0; i<methodNames.length; i++){  
  78.             Method sortMethod = null;  
  79.             sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞