大鱼

排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序

先推荐一篇关于排序算法的文章:http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

本文思路部分来源于上篇文章,但测得的结果似乎不大相同,不知是因为java的缘故还是因为我算法的缘故,欢迎拍砖。

 

复习排序,顺便比下各种算法的速度,榜单如下:

1、冒泡排序

2、简单选择排序

3、直接插入排序

4、折半插入排序

5、希尔排序

6、堆排序

7、归并排序

8、快速排序

当然这是慢速排行,哈哈~~

 

 

直接上图:单位毫秒

 

数量

冒泡排序

简单选择排序

直接插入排序

折半插入排序

希尔排序

堆排序

归并排序

快速排序

10000

1578

1250

672

250

0

15

16

0

15000

3453

2765

1563

531

16

15

16

0

20000

6140

4547

2453

828

16

16

15

16

25000

10079

7171

3969

1313

31

16

15

16

30000

14641

10313

5578

1906

31

31

16

31

35000

20141

14328

7890

2563

31

31

32

15

40000

25766

18359

10094

3422

47

31

31

32

45000

32469

24063

13062

4359

47

47

31

47

 

 

由于"希尔排序","堆排序","归并排序","快速排序"太快,以至于在上图几乎是条直线,故有了下面转为他们准备的加强版

 

数量

希尔排序

堆排序

归并排序

快速排序

100000个

172

140

110

93

200000个

469

406

235

234

300000个

812

703

422

375

400000个

1125

1031

516

531

500000个

1406

1282

719

656

600000个

1828

1703

860

859

700000个

2531

2063

1000

968

800000个

2735

2453

1140

1188

900000个

3047

2843

1391

1266

1000000个

3375

3187

1516

1422

1100000个

3922

3500

1625

1609

1200000个

4421

3954

1969

1812

1300000个

4797

4422

2000

1953

1400000个

5391

4797

2547

2094

1500000个

5437

5219

2625

2328

1600000个

6203

5546

2469

2485

1700000个

6532

5953

2844

2672

1800000个

7125

6421

2984

2844

 

补上代码:

 

Java代码 复制代码 收藏代码
  1. import java.util.ArrayList;   
  2. import java.util.Arrays;   
  3. import java.util.List;   
  4.   
  5. /**  
  6.  * 插入排序:直接插入排序、折半插入排序和系尔排序  
  7.  * 交换排序:冒泡排序和快速排序  
  8.  * 选择排序:简单选择排序和堆排序  
  9.  * 归并排序:归并排序  
  10.  *   
  11.  * 基本思想  
  12.  * 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。  
  13.  * 交换排序:按照某种顺序比较两个记录的关键字大小,然后根据需要交换两个记录的位置。  
  14.  * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录,放到适当的位置。  
  15.  *   
  16.  * 排序方法比较  
  17.  * 排序方法         平均时间        最坏时间         辅助存储  
  18.  * 直接插入排序      O(N2)          O(N2)           O(1)  
  19.  * 起泡排序         O(N2)          O(N2)           O(1)  
  20.  * 快速排序         O(Nlog2N)      O(N2)           O(Nlog2N)  
  21.  * 简单选择排序      O(N2)          O(N2)           O(1)  
  22.  * 堆排序           O(Nlog2N)      O(Nlog2N)       O(1)  
  23.  * 归并排序         O(Nlog2N)      O(Nlog2N)       O(n)  
  24.  * 基数排序         O(d(n+radix))  O(d(n+radix))   O(radix)  
  25.  *   
  26.  *   
  27.  *   
  28.  * @author Administrator  
  29.  *  
  30.  */  
  31. public class SortTest {   
  32.   
  33.     public static void main(String[] args)throws Exception {   
  34.         //测试排序是否正确   
  35.         //String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};   
  36.         //new SortTest().testErr(testErr);   
  37.            
  38.         //排序1(全部)   
  39.         String[] strs=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"};   
  40.         new SortTest().test(strs,10000,50000,5000);   
  41.            
  42.         //排序2(加强)   
  43.         String[] strs2=new String[]{"希尔排序","堆排序","归并排序","快速排序"};   
  44.         new SortTest().test(strs2,100000,1900000,100000);   
  45.            
  46.     }   
  47. private  void testErr(String[] strings) throws Exception{   
  48.            
  49.         //System.out.println(Arrays.toString(old));   
  50.         System.out.println(Arrays.toString(strings));   
  51.            
  52.             Number[] old=getRundom(50);   
  53.             Integer[] oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};   
  54.             old=oo;   
  55.             for(String s:strings){   
  56.                 Number[] testNum=Arrays.copyOf(old, old.length);   
  57.                 long begin=System.currentTimeMillis();   
  58.                 SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);   
  59.                    
  60.                 long end=System.currentTimeMillis();   
  61.                 System.out.println(s+":"+(end-begin)+"\t");   
  62.                 System.out.println(Arrays.toString(testNum));   
  63.             }   
  64.             System.out.println();   
  65.            
  66.            
  67.     }   
  68.        
  69.     private  void test(String[] strings,long begin,long end,long step) throws Exception{   
  70.         System.out.print("数量\t");   
  71.         for(String str:strings){   
  72.             System.out.print(str+"\t");   
  73.         }   
  74.         System.out.println();   
  75.         for(long i=begin;i<end;i=i+step){   
  76.             System.out.print(i+"个\t");   
  77.             Number[] old=getRundom(i);   
  78.             for(String s:strings){   
  79.                 Number[] testNum=Arrays.copyOf(old, old.length);   
  80.                 long beginTime=System.currentTimeMillis();   
  81.                 SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);   
  82.                    
  83.                 long endTime=System.currentTimeMillis();   
  84.                 System.out.print((endTime-beginTime)+"\t");   
  85.                 //System.out.println(Arrays.toString(testNum));   
  86.             }   
  87.             System.out.println();   
  88.         }   
  89.            
  90.     }   
  91.   
  92.     private static Integer[] getRundom(long num) {   
  93.         List<Integer> list=new ArrayList<Integer>();   
  94.         for(long i=0;i<num;i++){   
  95.             int k;   
  96.             if(Math.random()>0.5){   
  97.                 k=(int)(Math.random()*Integer.MAX_VALUE);   
  98.             }else{   
  99.                 k=(int)(Math.random()*Integer.MIN_VALUE);   
  100.             }   
  101.             list.add(k);   
  102.         }   
  103.         return list.toArray(new Integer[list.size()]);   
  104.     }   
  105.        
  106.        
  107.        
  108.        
  109.     /**  
  110.      * 插入排序————直接插入排序  
  111.      * @param data  
  112.      */  
  113.     public static  void  直接插入排序(Number[] data)   
  114.     {   
  115.         Number tmp=null ;   
  116.            
  117.       for(int i=1;i<data.length;i++){   
  118.           tmp = data[i];   
  119.           int j=i-1;   
  120.           while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){   
  121.               data[j+1]=data[j];   
  122.               j--;   
  123.           }   
  124.           data[j+1]=tmp;   
  125.       }   
  126.     }   
  127.     /**  
  128.      * 插入排序————折半插入排序  
  129.      * @param data  
  130.      */  
  131.     public static  void  折半插入排序(Number[] data)   
  132.     {   
  133.         Number tmp=null ;   
  134.           for(int i=1;i<data.length;i++){   
  135.               tmp = data[i];   
  136.               int smallpoint=0;    
  137.               int bigpoint=i-1;   
  138.                    
  139.               while(bigpoint>=smallpoint){   
  140.                   int mid=(smallpoint+bigpoint)/2;   
  141.                   if(tmp.doubleValue()>data[mid].doubleValue()){   
  142.                       smallpoint=mid+1;   
  143.                   }else{   
  144.                       bigpoint=mid-1;   
  145.                   }   
  146.               }   
  147.               for(int j=i;j>smallpoint;j--){   
  148.                   data[j]=data[j-1];   
  149.               }   
  150.               data[bigpoint+1]=tmp;   
  151.           }   
  152.     }   
  153.        
  154.     /**  
  155.      * 插入排序————希尔排序  
  156.      * @param data  
  157.      */  
  158.     public static  void  希尔排序(Number[] data)   
  159.     {   
  160.         int span=data.length/7;   
  161.         if(span==0)span=1;   
  162.         while(span>=1){   
  163.             for(int i=0;i<span;i++){   
  164.                 for(int j=i;j<data.length;j=j+span){   
  165.                     //组内直接插入排序     
  166.                     int p = j-span;   
  167.                     Number temp = data[j];   
  168.                     while( p >=0 && data[p].doubleValue() > temp.doubleValue()){   
  169.                         data[p+span] = data[p];   
  170.                         p -=span;   
  171.                     }      
  172.                     data[p + span] = temp;   
  173.                 }   
  174.             }   
  175.             span=span/2;   
  176.         }   
  177.            
  178.          
  179.     }   
  180.        
  181.     /**  
  182.      * 交换排序————冒泡排序  
  183.      *   
  184.      * @param data  
  185.      */  
  186.     public static void  冒泡排序(Number[] data)   
  187.     {   
  188.          for (int i = 0; i < data.length; i++) {   
  189.              //将相邻两个数进行比较,较大的数往后冒泡   
  190.              for (int j = 0; j < data.length - i-1; j++) {   
  191.                     if (data[j].doubleValue()> data[j + 1].doubleValue()) {   
  192.                            //交换相邻两个数   
  193.                            swap(data, j, j + 1);   
  194.                     }   
  195.              }   
  196.       }   
  197.     }   
  198.     /**  
  199.      * 交换排序————快速排序  
  200.      * @param data  
  201.      */  
  202.     public static void  快速排序(Number[] data)   
  203.     {   
  204.         QuickSort(data,0,data.length-1);   
  205.     }   
  206.         
  207.      private static void QuickSort(Number[] data, int begin, int end) {   
  208.         // System.out.println(begin+":"+end);   
  209.          if(begin<end){   
  210.              //取中点   
  211.              int mid=(begin+end)/2;   
  212.              if(data[end].doubleValue()<data[begin].doubleValue()){   
  213.                  swap(data, end, begin);   
  214.              }   
  215.              if(data[end].doubleValue()<data[mid].doubleValue()){   
  216.                  swap(data, end, mid);   
  217.              }   
  218.              if(data[mid].doubleValue()<data[begin].doubleValue()){   
  219.                  swap(data, mid, begin);   
  220.              }   
  221.                 
  222.              swap(data, mid, begin);   
  223.                
  224.             // System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );   
  225.             int min=begin+1;   
  226.             int big=end;   
  227.                 
  228.              while(true){   
  229.                 while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}   
  230.                 while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}   
  231.                 if(min>=big){   
  232.                     break;   
  233.                 }   
  234.                 swap(data, min, big);   
  235.             }   
  236.              if(data[begin].doubleValue()>data[min].doubleValue()){   
  237.                  swap(data, begin, min);   
  238.              }   
  239.                 
  240.             if(min>1)   
  241.              QuickSort(data,begin,min-1);   
  242.             //if(min<end)   
  243.              QuickSort(data,min,end);   
  244.          }   
  245.     }   
  246.     /**  
  247.          * 选择排序————简单选择排序  
  248.          * @param data  
  249.          */  
  250.         public static void  简单选择排序(Number[] data)   
  251.         {   
  252.              for (int i = 0; i < data.length-1; i++) {   
  253.                  int smallPoint=i;   
  254.                  for (int j = i+1; j < data.length; j++) {   
  255.                         if (data[smallPoint].doubleValue()> data[j].doubleValue()) {   
  256.                             smallPoint=j;   
  257.                         }   
  258.                  }   
  259.                  swap(data, i, smallPoint);   
  260.           }   
  261.              
  262.         }   
  263.            
  264.          /**  
  265.          * 选择排序————堆排序  
  266.          * @param data  
  267.          */  
  268.         public static void  堆排序(Number[] data)   
  269.         {   
  270.   
  271.              int n = data.length;   
  272.             for(int i=n/2;i>=0;i--){   
  273.                  keepHeap(data, n, i);   
  274.             }   
  275.               while (n > 0) {   
  276.                   swap(data, 0, n-1);   
  277.                   keepHeap(data, --n, 0);   
  278.               }   
  279.         }   
  280.            
  281.            
  282.          private static void keepHeap(Number[] a, int n, int i) {   
  283.              Number x = a[i];   
  284.               int j = 2 * i + 1;   
  285.               while (j <= n - 1) {   
  286.                if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())   
  287.                 ++j;   
  288.                if (a[j].doubleValue() > x.doubleValue()) {   
  289.                 a[i] = a[j];   
  290.                 i = j;   
  291.                 j = 2 * i ;   
  292.                } else{   
  293.                 break;   
  294.                 }   
  295.               }   
  296.               a[i] = x;   
  297.              }   
  298.            
  299.             
  300.             
  301.             
  302.          /**  
  303.              * 归并排序法————归并排序  
  304.              * @param data  
  305.              */  
  306.             public static void  归并排序(Number[] data)   
  307.             {   
  308.                  Number[] result = merge_sort(data,0,data.length-1);   
  309.                  for(int i=0;i<result.length;i++){   
  310.                      data[i]=result[i];   
  311.                  }   
  312.             }   
  313.          private static  Number[] merge_sort(Number[] array, int start, int end){   
  314.              Number[] result = new Number[end-start+1];   
  315.                 if(start< end){   
  316.                     int mid= (start+end)/2;   
  317.                     Number[] left= merge_sort(array, start, mid);   
  318.                     Number[] right =  merge_sort(array, mid+1, end);   
  319.                    result= merge(left,right);   
  320.                 } else if (start == end) {   
  321.                     result[0] = array[start];   
  322.                 return result;   
  323.                 }   
  324.                 return result;   
  325.             }   
  326.            private static Number[]  merge(Number[] left, Number[] right) {   
  327.                Number[] result = new Number[left.length+right.length];   
  328.                 int i=0;   
  329.                 int j=0;   
  330.                 int k=0;   
  331.                 while(i< left.length&&j< right.length){   
  332.                     if(left[i].doubleValue()< right[j].doubleValue()){   
  333.                         result[k++] = left[i++];   
  334.                     }else{   
  335.                         result[k++] = right[j++];   
  336.                            
  337.                     }   
  338.                 }   
  339.                 while(i< left.length){   
  340.                     result[k++] = left[i++];    
  341.                 }   
  342.                 while (j< right.length) {   
  343.                    result[k++]= right[j++];   
  344.                 }   
  345.                 return result;   
  346.             }   
  347.             
  348.            /**  
  349.             * 交换数组中指定的两元素的位置  
  350.             * @param data  
  351.             * @param x  
  352.             * @param y  
  353.             */  
  354.            private static void swap(Number[] data, int x, int y) {   
  355.                Number temp = data[x];   
  356.                   data[x] = data[y];   
  357.                   data[y] = temp;   
  358.            }   
  359. }  

posted on 2011-05-24 23:58 大鱼 阅读(1796) 评论(0)  编辑  收藏 所属分类: j2se


只有注册用户登录后才能发表评论。


网站导航: