java實現冒泡排序，選擇排序，插入排序，快速排序（簡潔版）及性能測試

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;
                }
            }
        }

    }

選擇排序的時間復雜度還有空間復雜度跟冒泡是一樣的。

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;
                }
            }
        }
    }

快速排序通常情況下是最快的，名不虛傳啊~平均時間復雜度是 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