1、冒泡排序是排序里面最简单的了,但性能也最差,数量小的时候还可以,数量一多,是非常慢的。
它的时间复杂度是O(n*n),空间复杂度是O(1)
代码如下,很好理解。
public void bubbleSort(int[] arr){ int temp=0;
for(int i=0;i<arr.length;i++){
for(int j=arr.length-1;j>0;j--){
if(arr[j-1]>arr[j]){
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
} }
2、选择排序
选择排序的时间复杂度还有空间复杂度跟冒泡是一样的。
public void chooseSort(int[] arr){
int temp=0;
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
3、插入排序
插入排序的时间复杂度也是O(n*n),空间复杂度也是O(1)。
public void insertSort(int[] arr){
int tmp=0;
for(int j=1;j<arr.length;j++){
for(int i=0;i<j;i++){
if(arr[i]>arr[j]){
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
见识到快速排序的威力了吧~不过他也是付出了内存空间的代价,如果数据量过大,会出现著名的*栈溢出异常哦~