一、前言

快速排序，聽這個名字也知道這是一個性能比較好的排序算法。最壞情況下時間復(fù)雜度為O(n2），雖然最壞時間復(fù)雜度很差，但是快速排序通常是實際排序中最好的選擇，因為它平均性能最好：它的期望時間復(fù)雜度O(nlgn)，而且隱含的常數(shù)因子非常小。快速排序主要利用

二、實現(xiàn)

整個實現(xiàn)思路可以這樣理解：①找到一個基準(zhǔn)，例如將最后一個元素當(dāng)做基準(zhǔn)②從第一個元素依次和基準(zhǔn)比較，如果小于基準(zhǔn)則不動，如果大于基準(zhǔn)則將該元素放到該基準(zhǔn)的后面。這樣一來，就可以在一次比較完成之后該基準(zhǔn)前面的元素都小于基準(zhǔn)，后面的元素都大于基準(zhǔn)。然后就依次遞歸即可實現(xiàn)。

快速排序整個過程可分為partition+遞歸實現(xiàn)兩部分。

partition過程

代碼實現(xiàn)

public class QuickSort {

    public static void main(String[] args) {
        QuickSort qs = new QuickSort();
        int[] a = { 2, 8, 7, 1, 3, 5, 6, 4 };
        int p = 0, r = a.length - 1;
        qs.quickSort(a, p, r);
        CommonUtil.print(a);
    }

    public void quickSort(int[] a, int p, int r) {
        if (p < r) {
            int q = partition(a, p, r);
            quickSort(a, p, q - 1);
            quickSort(a, q + 1, r);
        }
    }

    /**
     * 對數(shù)組進(jìn)行原址重排 2, 8, 7, 1, 3, 5, 6, 4
     */
    public int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (a[j] <= x) {
                i = i + 1;
                CommonUtil.swap(a, i, j);
            }
        }
        CommonUtil.swap(a, i + 1, r);
        return i + 1;
    }

}

三、總結(jié)

快速排序應(yīng)該是面試中問的比較多的，有時候會要求手寫實現(xiàn)，因此還需要重點掌握吧~~~