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; } } } }
插入排序的时间复杂度也是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