摘要：快速排序的介紹來源百度百科快速排序由在年提出。快速排序是面試出現的可能性比較高的，也是經常會用到的一種排序，應該重點掌握。前面一個章節已經講了遞歸了，那么現在來看快速排序就非常簡單了。

從前面已經講解了冒泡排序、選擇排序、插入排序了，本章主要講解的是快速排序，希望大家看完能夠理解并手寫出快速排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。

來源百度百科：

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

快速排序是面試出現的可能性比較高的，也是經常會用到的一種排序，應該重點掌握。

前面一個章節已經講了遞歸了，那么現在來看快速排序就非常簡單了。

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小

百度百科的話并沒有說到重點，更簡單的理解是這樣的：在數組中找一個支點(任意),經過一趟排序后，支點左邊的數都要比支點小，支點右邊的數都要比支點大！

現在我們有一個數組：int arr[]={1,4,5,67,2,7,8,6,9,44};

經過一趟排序之后，如果我選擇數組中間的數作為支點：7(任意的)，那么第一趟排序后的結果是這樣的：{1,4,5,6,2,7,8,67,9,44}

那么就實現了支點左邊的數比支點小，支點右邊的數比支點大

現在我們的數組是這樣的：{1,4,5,6,2,7,8,67,9,44}，既然我們比7小的在左邊，比7大的在右邊，那么我們只要將”左邊“的排好順序，又將”右邊“的排好序，那整個數組是不是就有序了？想一想，是不是？

又回顧一下遞歸：”左邊“的排好順序，”右邊“的排好序，跟我們第一趟排序的做法是不是一致的？

只不過是參數不一樣：第一趟排序是任選了一個支點，比支點小的在左邊，比支點大的在右邊。那么，我們想要”左邊“的排好順序，只要在”左邊“部分找一個支點，比支點小的在左邊，比支點大的在右邊。

..............

在數組中使用遞歸依照我的慣性，往往定義兩個變量：L和R，L指向第一個數組元素，R指向在最后一個數組元素

遞歸出口也很容易找到：如果數組只有一個元素時，那么就不用排序了

所以，我們可以寫出這樣的代碼：

    public static void main(String[] args) {
        int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44};

        quickSort(arr, 0, 9);

        System.out.println("Java3y   " + arr);


    }

    /**
     * 快速排序
     *
     * @param arr
     * @param L   指向數組第一個元素
     * @param R   指向數組最后一個元素
     */
    public static void quickSort(int[] arr, int L, int R) {
        int i = L;
        int j = R;

        //支點
        int pivot = arr[(L + R) / 2];

        //左右兩端進行掃描，只要兩端還沒有交替，就一直掃描
        while (i <= j) {

            //尋找直到比支點大的數
            while (pivot > arr[i])
                i++;

            //尋找直到比支點小的數
            while (pivot < arr[j])
                j--;

            //此時已經分別找到了比支點小的數(右邊)、比支點大的數(左邊)，它們進行交換
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        //上面一個while保證了第一趟排序支點的左邊比支點小，支點的右邊比支點大了。


        //“左邊”再做排序，直到左邊剩下一個數(遞歸出口)
        if (L < j)
            quickSort(arr, L, j);

        //“右邊”再做排序，直到右邊剩下一個數(遞歸出口)
        if (i < R)
            quickSort(arr, i, R);
    }

來源：http://www.cnblogs.com/noKing/archive/2017/11/29/7922397.html

我這里簡單概括一下思路，有興趣的同學可到上面的鏈接上閱讀：

隨機選取基準值base(支點隨機選取)

配合著使用插入排序(當問題規模較小時，近乎有序時，插入排序表現的很好)

當大量數據，且重復數多時，用三路快排

原理都是一樣的，在細節上有些變化而已

它是交換完畢后記錄支點的角標，然后再劈開兩半進行遞歸調用

C語言代碼實現：

        void QuickSort ( int*arr,int low, int high);
        int FindPos ( int*arr,int low, int high);


        int FindPos ( int*arr,int low, int high)
        {
            int val = arr[low];

            while (low < high) {
                while (low < high && arr[high] >= val)
                    --high;
                arr[low] = arr[high];
                while (low < high && arr[low] <= val)
                    ++low;
                arr[high] = arr[low];
            }
            arr[low] = val;
            return low;
        }


        void QuickSort ( int arr[], int low, int high)
        {
            int pos;
            if (low < high) {
                pos = FindPos(arr, low, high);
                QuickSort(arr, low, pos - 1);//劈兩半，左邊 
                QuickSort(arr, pos + 1, high); //右邊 
            }
            return;
        }

        int main ()
        {
            int arr[ 6]={ 5, 3, -88, 77, 44, -1 } ;
            int i;
            QuickSort(arr, 0, 5);
            for (i = 0; i < 6; i++)
                printf("%d   ", arr[i]);
            printf("
");
            return 0;
        }

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y