当前位置: 安卓之星 -> Java开发 -> Java使用二分插入排序竟然和直接插入排序速度相差不多

Java使用二分插入排序竟然和直接插入排序速度相差不多

作者:网络 发表于: 2016-11-21 点击: 245 次

程序如下:

public class test{
    public static void main(String []args){
       Date d1 = new Date();
       int[] a = new int[200000];
       for(int i=0;i<200000;i++)
       {
    	   a[i]=100-i;
       }

       InsertSort(a);
       Date d2 = new Date();
       System.out.println("InsertSort total milliseconds:"+(d2.getTime()-d1.getTime())); 
 //printing the elements
 //for(int i=0;i<a.length;i++){
 //System.out.println(i+" : "+a[i]);
 //}

       Date d3 = new Date();
       int[] a2 = new int[200000];
       for(int i=0;i<200000;i++)
       {
    	   a2[i]=100-i;
       }

       InsertSortWithBinarySerach(a2);
       Date d4 = new Date();
       System.out.println("InsertSortWithBinarySerach total milliseconds:"+(d4.getTime()-d3.getTime())); 
 //printing the elements
 //for(int j=0;j<a2.length;j++){
 //System.out.println(j+" : "+a2[j]);
 //}
    }

   public static void InsertSort(int[] A){
     for(int i = 1; i < A.length; i++){
       int value = A[i];
       int j = i - 1;
       while(j >= 0 && A[j] > value){
         A[j + 1] = A[j];
         j = j - 1;
       }
       A[j + 1] = value;
     }
   }
 public static void InsertSortWithBinarySerach(int[] A){
    for(int i=1;i<A.length;i++){
     int key=A[i];
     int pos=binarySearch(A,0,i-1,key); //finds where the element will be stored
     for(int j=i;j>pos;j--) //shifts the other elements by 1 position to the right
     A[j]=A[j-1];
     A[pos]=key; //places the key element in the pos position
     }
 }
 //uses binary search technique to find the position where the element will be inserted
 public static int binarySearch(int[] A,int low,int high,int key){
     int mid;
     while(low<=high){
         mid=(low+high)/2;
         if(key>A[mid])
             low=mid+1;
         else if(key<A[mid])
             high=mid-1;
         else
             return mid;
    }
    return low;
 }
}

现在测试下 Java,Linux测试结果如下:

javac test.java
java test
InsertSort total milliseconds:15769
InsertSortWithBinarySerach total milliseconds:15657

莫非这两个算法在JVM中运行差别很小?

相关文章

相关文章

赶快留言冒泡

  • 评论 (0)
  • 引用通告 (0)
目前还没有任何评论.
目前还没有任何Trackbacks和Pingbacks.
吐个泡浮上去.