java实现冒泡排序,选择排序,插入排序,快速排序(简洁版)及性能测试

jopen 10年前

1、冒泡排序是排序里面最简单的了,但性能也最差,数量小的时候还可以,数量一多,是非常慢的。

它的时间复杂度是O(n*n),空间复杂度是O(1)

代码如下,很好理解。

public void bubbleSort(int[] arr){    for(int i=0;i<arr.length-1;i++){     for(int j=arr.length-1;j>i;j--){      if(arr[j-1]>arr[j]){       int temp=arr[j-1];       arr[j-1]=arr[j];       arr[j]=temp;      }     }    }      }

2、选择排序

选择排序的时间复杂度还有空间复杂度跟冒泡是一样的。

public void chooseSort(int[] arr){    for(int i=0;i<arr.length;i++){     for(int j=i+1;j<arr.length;j++){      if(arr[i]>arr[j]){       int temp=arr[i];       arr[i]=arr[j];       arr[j]=temp;      }     }    }   }


3、插入排序

插入排序的时间复杂度也是O(n*n),空间复杂度也是O(1)。

public void insertSort(int[] arr){    for(int j=1;j<arr.length;j++){     for(int i=0;i<j;i++){      if(arr[i]>arr[j]){       int tmp=arr[i];       arr[i]=arr[j];       arr[j]=tmp;       break;      }     }    }   }

4、快速排序

快速排序通常情况下是最快的,名不虚传啊~平均时间复杂度是 O(Nlog2N),最差也是O(N*N),空间复杂度O(Nlog2N) 

public void quickSort(int[] arr,int head,int tail){    int i=head;    int j=tail;    if(i > j){     return;    }    int key=arr[i];    while(i<j){     while(i<j && key<=arr[j]){      j--;     }     if(i<j){      arr[i++]=arr[j];     }     while(i<j && key>=arr[i]){      i++;     }     if(i<j){      arr[j--]=arr[i];     }    }    arr[j]=key;    quickSort(arr,head,j-1);    quickSort(arr,j+1,tail);       }
下面就是性能测试了~

分别为这4个算法生成4个长度为6000的随机数组,然后测排序时间。

代码如下

public static void main(String[] args) throws Exception{      int[] arr1=new int[6000];   for(int i=0;i<arr1.length;i++){    arr1[i]=new Random().nextInt(6000)+1;   }   int[] arr2=new int[6000];   for(int i=0;i<arr2.length;i++){    arr2[i]=new Random().nextInt(6000)+1;   }   int[] arr3=new int[6000];   for(int i=0;i<arr3.length;i++){    arr3[i]=new Random().nextInt(6000)+1;   }   int[] arr4=new int[6000];   for(int i=0;i<arr4.length;i++){    arr4[i]=new Random().nextInt(6000)+1;   }   Test t=new Test();   long m=System.currentTimeMillis();   t.bubbleSort(arr1);   long n=System.currentTimeMillis();   System.out.println("冒泡排序耗时:"+(n-m)+"ms");   long p=System.currentTimeMillis();   t.chooseSort(arr2);   long q=System.currentTimeMillis();   System.out.println("选择排序耗时:"+(q-p)+"ms");   long e=System.currentTimeMillis();   t.insertSort(arr4);   long d=System.currentTimeMillis();   System.out.println("插入排序耗时:"+(d-e)+"ms");   long a=System.currentTimeMillis();   t.quickSort(arr3, 0, arr3.length-1);   long b=System.currentTimeMillis();   System.out.println("快速排序耗时:"+(b-a)+"ms");  }  }

结果如下:

冒泡排序耗时:182ms

选择排序耗时:120ms

插入排序耗时:4ms

快速排序耗时:1ms

见识到快速排序的威力了吧~不过他也是付出了内存空间的代价,如果数据量过大,会出现著名的StackOverFlow栈溢出异常哦~


来自:http://blog.csdn.net/exceptional_derek/article/details/11786913