摘要：快速排序的介紹來源百度百科快速排序由在年提出?？焖倥判蚴敲嬖嚦霈F(xiàn)的可能性比較高的，也是經(jīng)常會用到的一種排序，應(yīng)該重點(diǎn)掌握。前面一個(gè)章節(jié)已經(jīng)講了遞歸了，那么現(xiàn)在來看快速排序就非常簡單了。

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

來源百度百科：

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

快速排序是面試出現(xiàn)的可能性比較高的，也是經(jīng)常會用到的一種排序，應(yīng)該重點(diǎn)掌握。

前面一個(gè)章節(jié)已經(jīng)講了遞歸了，那么現(xiàn)在來看快速排序就非常簡單了。

通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小

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

現(xiàn)在我們有一個(gè)數(shù)組：int arr[]={1,4,5,67,2,7,8,6,9,44};

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

那么就實(shí)現(xiàn)了支點(diǎn)左邊的數(shù)比支點(diǎn)小，支點(diǎn)右邊的數(shù)比支點(diǎn)大

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

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

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

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

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

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

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

    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   指向數(shù)組第一個(gè)元素
     * @param R   指向數(shù)組最后一個(gè)元素
     */
    public static void quickSort(int[] arr, int L, int R) {
        int i = L;
        int j = R;

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

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

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

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

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


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

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

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

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

隨機(jī)選取基準(zhǔn)值base(支點(diǎn)隨機(jī)選取)

配合著使用插入排序(當(dāng)問題規(guī)模較小時(shí)，近乎有序時(shí)，插入排序表現(xiàn)的很好)

當(dāng)大量數(shù)據(jù)，且重復(fù)數(shù)多時(shí)，用三路快排

原理都是一樣的，在細(xì)節(jié)上有些變化而已

它是交換完畢后記錄支點(diǎn)的角標(biāo)，然后再劈開兩半進(jìn)行遞歸調(diào)用

C語言代碼實(shí)現(xiàn)：

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

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