本文章只是自我總結，鞏固基礎之用，如有錯誤，望大佬不吝賜教。

1.1 快速排序簡介

快速排序的實現(xiàn)原理：

1.先選取一個基準值pivotkey;
2.在頭尾分別定義兩個指針：left，right；
3.兩個指針指向的值分別與基準值進行對比，當left指針的數(shù)組大于基準值，right指針的數(shù)值小于基準值時，兩個元素進行交換。

這樣就實現(xiàn)了，在基準值左邊的都是小于基準值的值，在基準值右邊的都大于基準值的值。如下動畫，以[6，3，8，2，4，7]數(shù)組為例，以6為基準值，介紹了一輪比較的過程：

快速排序

1.2 快速排序&樹結構

如果把快速排序與樹結構進行聯(lián)系，是更加方便對它的理解的。還是以上面的這個數(shù)組為例。

每一輪比較的過程，我們深入的來理解一下。對于找出基準值這個操作，就相當于在樹結構中樹立一個根節(jié)點。一輪比較就是把其他節(jié)點往根節(jié)點左右兩邊來擺放，只是這時左右兩顆子樹并沒有排序好，需要通過下一輪來進行排序。

如下圖，第一輪比較后，比節(jié)點6小的值到了其的左邊，比節(jié)點6大的值到了其的右邊。接下來第二輪比較后，數(shù)組[3，2，4]也已經(jīng)排序完畢。

image.png

1.3 時間復雜度

所以在這里，我們很容易的得出了該種算法的時間復雜度為(nlogn)級別，n為所有每一輪比較過程比較的次數(shù)，logn為比較的輪數(shù)，即為樹的深度。

但是樹的深度和選取的基準值有很大關系，基準值沒有選好，會導致樹退化成鏈表，增加了比較的輪數(shù)，最差深度會變成n，所以此時時間復雜度為(n*n)級別。

image.png

用小小表格總結一下：

快速排序java代碼如下：

public static void quickSort2(int[] a, int low, int high) {
        int pivot;

        if (low < high) {
            // 找出基準位置的同時，進行元素的交換
            pivot = partition(a, low, high);

            quickSort2(a, low, pivot - 1);
            quickSort2(a, pivot + 1, high);
        }
    }

    public static int partition(int[] a, int low, int high) {
        // 因為此處已經(jīng)記錄住了基準，所以low位置的數(shù)值可以被覆蓋掉。
        int pivotKey = a[low];

        while (low < high) {

            while (high > low && a[high] >= pivotKey) {
                high--;
            }

            //直接覆蓋low位置的值，low位置的值已經(jīng)被pivotKey記錄住
            a[low] = a[high];

            while (high > low && a[low] <= pivotKey) {
                low++;
            }

            //此時的a[high]的值被上面最初low位置的值記錄著
            a[high] = a[low];
        }

        //low就是基準值所在的位置
        a[low] = pivotKey;
        return low;
    }