java冒泡排序和快速排序_ZenDei技術網路在線

幾乎每個人做java開發的都能寫出冒泡排序的演算法，那麼java中的排序是怎麼做的呢？冒泡排序並不是很好的排序方法，一起來瞭解一下吧。 ...

一、冒泡排序

1.演算法介紹

設排序表長為n，從後向前或者從前向後兩兩比較相鄰元素的值，如果兩者的相對次序不對(A[i-1] > A[i])，則交換它們，其結果是將最小的元素交換到待排序序列的第一個位置，我們稱它為一趟冒泡。下一趟冒泡時，前一趟確定的最小元素不再參與比較，待排序序列減少一個元素，每趟冒泡的結果把序列中最小的元素放到了序列的”最前面”。

2.演算法實現

冒泡排序封裝函數的代碼如下

public void bubbleSort(int[] arr) {
    int temp;//定義一個臨時變數
    for(int i=0;i<arr.length-1;i++){//冒泡趟數
        for(int j=0;j<arr.length-i-1;j++){
            //如果順序不對，則交換兩個元素
            if(arr[j+1]<arr[j]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

測試代碼如下

public static void main(String[] args) {
    Test t = new Test();
    int arr[] = new int[]{13,26,22,22,35,18};
    t.bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

運行結果如下

[13, 18, 22, 22, 26, 35]

3.演算法分析

冒泡排序的時間複雜度為O(n^2),空間複雜度為O(1),它是一種穩定的排序演算法。當然了，這也是非常基礎的一種演算法，一般找工作有些公司喜歡出筆試題。

下麵我們來看看java中的Arrays.sort(int []a)方法是怎麼實現的。

二、快速排序

java中Arrays.sort使用了兩種排序方法，快速排序和優化的合併排序。

快速排序主要是對哪些基本類型數據（int,short,long等）排序，而合併排序用於對對象類型進行排序。

使用不同類型的排序演算法主要是由於快速排序是不穩定的，而合併排序是穩定的。這裡的穩定是指比較相等的數據在排序之後仍然按照排序之前的前後順序排列。對於基本數據類型，穩定性沒有意義，而對於對象類型，穩定性是比較重要的，因為對象相等的判斷可能只是判斷關鍵屬性，最好保持相等對象的非關鍵屬性的順序與排序前一直；另外一個原因是由於合併排序相對而言比較次數比快速排序少，移動（對象引用的移動）次數比快速排序多，而對於對象來說，比較一般比移動耗時。

1.實現原理

java1.7之後的版本，開始用雙軸快排取代了以前的排序演算法，現在只實現了8種基本數據類型性的雙軸快排，對象的排序在1.7中還在用老式的，不過都標了過時，估計以後版本中就會被新的雙軸快排取代了。

他的DualPivotQuicksort()方法，裡邊一共寫了三種演算法（不算改進版的插入排序話），對於大數組而且部分高度有序的用歸併排序，其餘的用雙軸快排進行分割，分割到足夠小的時候用插入排序（主要是改進版的pair insertion sort）。

雙軸快排的基本原理是取兩個pivot，所有比pivot1小的放到最左邊，比pivot2大的放到最右邊，然後遞歸下去，就可以把兩端的元素完成排序，之後處理中間部分，中間部分如果過大就繼續遞歸用這種方式繼續分割，如果不大，就用單軸分割對兩部分遞歸調用下去。

2.實現代碼

代碼截取自jdk1.7中的Arrays類

/**
 * Sorts the specified range of the array.
 *
 * @param a the array to be sorted
 * @param left the index of the first element, inclusive, to be sorted
 * @param right the index of the last element, inclusive, to be sorted
 */
public static void sort(int[] a, int left, int right) {
    // Use Quicksort on small arrays
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }

    /*
     * Index run[i] is the start of i-th run
     * (ascending or descending sequence).
     */
    int[] run = new int[MAX_RUN_COUNT + 1];
    int count = 0; run[0] = left;

    // Check if the array is nearly sorted
    for (int k = left; k < right; run[count] = k) {
        if (a[k] < a[k + 1]) { // ascending
            while (++k <= right && a[k - 1] <= a[k]);
        } else if (a[k] > a[k + 1]) { // descending
            while (++k <= right && a[k - 1] >= a[k]);
            for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
            }
        } else { // equal
            for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                if (--m == 0) {
                    sort(a, left, right, true);
                    return;
                }
            }
        }

        /*
         * The array is not highly structured,
         * use Quicksort instead of merge sort.
         */
        if (++count == MAX_RUN_COUNT) {
            sort(a, left, right, true);
            return;
        }
    }

    // Check special cases
    if (run[count] == right++) { // The last run contains one element
        run[++count] = right;
    } else if (count == 1) { // The array is already sorted
        return;
    }

    /*
     * Create temporary array, which is used for merging.
     * Implementation note: variable "right" is increased by 1.
     */
    int[] b; byte odd = 0;
    for (int n = 1; (n <<= 1) < count; odd ^= 1);

    if (odd == 0) {
        b = a; a = new int[b.length];
        for (int i = left - 1; ++i < right; a[i] = b[i]);
    } else {
        b = new int[a.length];
    }

    // Merging
    for (int last; count > 1; count = last) {
        for (int k = (last = 0) + 2; k <= count; k += 2) {
            int hi = run[k], mi = run[k - 1];
            for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                if (q >= hi || p < mi && a[p] <= a[q]) {
                    b[i] = a[p++];
                } else {
                    b[i] = a[q++];
                }
            }
            run[++last] = hi;
        }
        if ((count & 1) != 0) {
            for (int i = right, lo = run[count - 1]; --i >= lo;
                b[i] = a[i]
            );
            run[++last] = right;
        }
        int[] t = a; a = b; b = t;
    }
}

3.源碼分析

源碼中的快速排序，主要做了以下幾個方面的優化：

　　1）當待排序的數組中的元素個數較少時，源碼中的閥值為7，採用的是插入排序。儘管插入排序的時間複雜度為0(n^2)，但是當數組元素較少時，插入排序優於快速排序，因為這時快速排序的遞歸操作影響性能。

　　2）較好的選擇了劃分元（基準元素）。能夠將數組分成大致兩個相等的部分，避免出現最壞的情況。例如當數組有序的的情況下，選擇第一個元素作為劃分元，將使得演算法的時間複雜度達到O(n^2).

源碼中選擇劃分元的方法:

　　　　當數組大小為 size=7 時，取數組中間元素作為劃分元。int n=m>>1;(此方法值得借鑒)

　　　　當數組大小 7<size<=40時，取首、中、末三個元素中間大小的元素作為劃分元。

　　　　當數組大小 size>40 時，從待排數組中較均勻的選擇9個元素，選出一個偽中數做為劃分元。

　　3）根據劃分元 v ，形成不變式 v* (<v)* (>v)* v*

　　普通的快速排序演算法，經過一次劃分後，將劃分元排到素組較中間的位置，左邊的元素小於劃分元，右邊的元素大於劃分元，而沒有將與劃分元相等的元素放在其附近，這一點，在Arrays.sort()中得到了較大的優化。

搜索微信公眾號“java工會”，或者掃碼關註我們，與君共勉！