快速排序算法詳解（原理、實(shí)現(xiàn)和時(shí)間復(fù)雜度）

快速排序是對冒泡排序的一種改進(jìn)，由 C.A.R.Hoare（Charles Antony Richard Hoare，東尼·霍爾）在 1962 年提出。

快速排序的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)要小，再按這種方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，使整個(gè)數(shù)據(jù)變成有序序列。

快速排序的原理

排序算法的思想非常簡單，在待排序的數(shù)列中，我們首先要找一個(gè)數(shù)字作為基準(zhǔn)數(shù)（這只是個(gè)專用名詞）。為了方便，我們一般選擇第 1 個(gè)數(shù)字作為基準(zhǔn)數(shù)（其實(shí)選擇第幾個(gè)并沒有關(guān)系）。接下來我們需要把這個(gè)待排序的數(shù)列中小于基準(zhǔn)數(shù)的元素移動到待排序的數(shù)列的左邊，把大于基準(zhǔn)數(shù)的元素移動到待排序的數(shù)列的右邊。這時(shí)，左右兩個(gè)分區(qū)的元素就相對有序了；接著把兩個(gè)分區(qū)的元素分別按照上面兩種方法繼續(xù)對每個(gè)分區(qū)找出基準(zhǔn)數(shù)，然后移動，直到各個(gè)分區(qū)只有一個(gè)數(shù)時(shí)為止。

這是典型的分治思想，即分治法。下面我們對一個(gè)實(shí)際例子進(jìn)行算法描述，講解快速排序的排序步驟。

快速排序詳解

以 “6 1 2 7 9 3 4 5 10 8” 的待排序的數(shù)列為例進(jìn)行排序

接下來開始移動元素。怎么移動呢？其實(shí)冒泡排序也涉及對元素的移動，但是那樣移動起來很累，比如把最后一個(gè)元素移動到第 1 個(gè)，就需要比較 n-1 次，同時(shí)交換 n-1 次，效率很低。其實(shí)，只需把第 1 個(gè)元素和最后一個(gè)元素交換就好了，這種思想是不是在排序時(shí)可以借鑒呢？之前說快速排序就是對冒泡排序的一個(gè)改進(jìn)，就是這個(gè)原因。

快速排序的操作是這樣的：首先從數(shù)列的右邊開始往左邊找，我們設(shè)這個(gè)下標(biāo)為 i，也就是進(jìn)行減減操作（i–），找到第 1 個(gè)比基準(zhǔn)數(shù)小的值，讓它與基準(zhǔn)值交換；接著從左邊開始往右邊找，設(shè)這個(gè)下標(biāo)為 j，然后執(zhí)行加加操作（j++），找到第 1 個(gè)比基準(zhǔn)數(shù)大的值，讓它與基準(zhǔn)值交換；然后繼續(xù)尋找，直到 i 與 j 相遇時(shí)結(jié)束，最后基準(zhǔn)值所在的位置即 k 的位置，也就是說 k 左邊的值均比 k 上的值小，而 k 右邊的值都比 k 上的值大。

假如用 “6 1 2 7 9 3 4 5 10 8” 這個(gè)初始序列來進(jìn)行快速排序

分別從初始序列“6 1 2 7 9 3 4 5 10 8”兩端開始“探測”。先從右往左找一個(gè)小于6的數(shù)，再從左往右找一個(gè)大于6的數(shù)，然后交換他們。這里可以用兩個(gè)變量i和j，分別指向序列最左邊和最右邊。我們?yōu)檫@兩個(gè)變量起個(gè)好聽的名字“哨兵i”和“哨兵j”。剛開始的時(shí)候讓哨兵i指向序列的最左邊（即i=1），指向數(shù)字6。讓哨兵j指向序列的最右邊（即=10），指向數(shù)字。

首先哨兵j開始出動。因?yàn)榇颂幵O(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)，所以需要讓哨兵j先出動，這一點(diǎn)非常重要（請自己想一想為什么）。哨兵j一步一步地向左挪動（即j–），直到找到一個(gè)小于6的數(shù)停下來。接下來哨兵i再一步一步向右挪動（即i++），直到找到一個(gè)數(shù)大于6的數(shù)停下來。最后哨兵j停在了數(shù)字5面前，哨兵i停在了數(shù)字7面前。

現(xiàn)在交換哨兵i和哨兵j所指向的元素的值。交換之后的序列如下：
6 1 2 5 9 3 4 7 10 8


到此，第一次交換結(jié)束。接下來開始哨兵j繼續(xù)向左挪動（再友情提醒，每次必須是哨兵j先出發(fā)）。他發(fā)現(xiàn)了4（比基準(zhǔn)數(shù)6要小，滿足要求）之后停了下來。哨兵i也繼續(xù)向右挪動的，他發(fā)現(xiàn)了9（比基準(zhǔn)數(shù)6要大，滿足要求）之后停了下來。此時(shí)再次進(jìn)行交換，交換之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交換結(jié)束，“探測”繼續(xù)。哨兵j繼續(xù)向左挪動，他發(fā)現(xiàn)了3（比基準(zhǔn)數(shù)6要小，滿足要求）之后又停了下來。哨兵i繼續(xù)向右移動，糟啦！此時(shí)哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。說明此時(shí)“探測”結(jié)束。我們將基準(zhǔn)數(shù)6和3進(jìn)行交換。交換之后的序列如下：

3 1 2 5 4 6 9 7 10 8

到此第一輪“探測”真正結(jié)束。此時(shí)以基準(zhǔn)數(shù)6為分界點(diǎn)，6左邊的數(shù)都小于等于6，6右邊的數(shù)都大于等于6?；仡櫼幌聞偛诺倪^程，其實(shí)哨兵j的使命就是要找小于基準(zhǔn)數(shù)的數(shù)，而哨兵i的使命就是要找大于基準(zhǔn)數(shù)的數(shù)，直到i和j碰頭為止。

OK，解釋完畢?，F(xiàn)在基準(zhǔn)數(shù)6已經(jīng)歸位，它正好處在序列的第6位。此時(shí)我們已經(jīng)將原來的序列，以6為分界點(diǎn)拆分成了兩個(gè)序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”。接下來還需要分別處理這兩個(gè)序列。因?yàn)?左邊和右邊的序列目前都還是很混亂的。不過不要緊，我們已經(jīng)掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可?，F(xiàn)在先來處理6左邊的序列現(xiàn)吧。

左邊的序列是“3 1 2 5 4”。請將這個(gè)序列以3為基準(zhǔn)數(shù)進(jìn)行調(diào)整，使得3左邊的數(shù)都小于等于3，3右邊的數(shù)都大于等于3。好了開始動筆吧

如果你模擬的沒有錯(cuò)，調(diào)整完畢之后的序列的順序應(yīng)該是：

2 1 3 5 4

OK，現(xiàn)在3已經(jīng)歸位。接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”。對序列“2 1”以2為基準(zhǔn)數(shù)進(jìn)行調(diào)整，處理完畢之后的序列為“1 2”，到此2已經(jīng)歸位。序列“1”只有一個(gè)數(shù)，也不需要進(jìn)行任何處理。至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”。序列“5 4”的處理也仿照此方法，最后得到的序列如下：

1 2 3 4 5 6 9 7 10 8

對于序列“9 7 10 8”也模擬剛才的過程，直到不可拆分出新的子序列為止。最終將會得到這樣的序列，如下

1 2 3 4 5 6 7 8 9 10

到此，排序完全結(jié)束。細(xì)心的同學(xué)可能已經(jīng)發(fā)現(xiàn)，快速排序的每一輪處理其實(shí)就是將這一輪的基準(zhǔn)數(shù)歸位，直到所有的數(shù)都?xì)w位為止，排序就結(jié)束了。下面上個(gè)霸氣的圖來描述下整個(gè)算法的處理過程。

這是為什么呢？

快速排序之所比較快，因?yàn)橄啾让芭菖判颍看谓粨Q是跳躍式的。每次排序的時(shí)候設(shè)置一個(gè)基準(zhǔn)點(diǎn)，將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放到基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會像冒泡排序一樣每次只能在相鄰的數(shù)之間進(jìn)行交換，交換的距離就大的多了。因此總的比較和交換次數(shù)就少了，速度自然就提高了。當(dāng)然在最壞的情況下，仍可能是相鄰的兩個(gè)數(shù)進(jìn)行了交換。因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(N2)，它的平均時(shí)間復(fù)雜度為O(NlogN)。其實(shí)快速排序是基于一種叫做“二分”的思想。我們后面還會遇到“二分”思想，到時(shí)候再聊。先上代碼，如下

快速排序代碼實(shí)現(xiàn)

其實(shí)快速排序有一個(gè)比較簡單的思想，就是遞歸。對于每一趟排序都是一樣的思想，只不過需要進(jìn)行排序的數(shù)組的范圍越來越小了，使用遞歸實(shí)現(xiàn)這種排序最適合不過了。

import com.sun.deploy.util.StringUtils;

public class tets {
    
    public static void main(String[] args) {

        int[] data = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));

        quickSort(data, 0, data.length - 1);

        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }


    public static void quickSort(int[] data, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp就是基準(zhǔn)位
        temp = data[low];
        System.out.println("基準(zhǔn)位：" + temp);

        while (i < j) {
            //因?yàn)樗帕许樞蚴沁f增，而且每次哨兵排查結(jié)束在于左右哨兵是否相遇，所以右邊哨兵負(fù)責(zé)尋找大于基準(zhǔn)的數(shù)，左邊哨兵尋找小于基準(zhǔn)的數(shù)
            // ，如若需要改變快排后的結(jié)果順序只需要改變左右哨兵對于基準(zhǔn)數(shù)的大小判斷
            //先看右邊，依次往左遞減 在未和左邊哨兵相遇前尋找大于或者等于基準(zhǔn)的數(shù)
            while (temp <= data[j] && i < j) {
                j--;
            }
            //再看左邊，依次往右遞增 在未和右邊哨兵相遇前尋找小于或者等于基準(zhǔn)的數(shù)
            while (temp >= data[i] && i < j) {
                i++;
            }
            //如果滿足條件則交換  左右哨兵未相遇的情況下尋找到滿足條件的數(shù)
            if (i < j) {
                System.out.println("交換：" + data[i] + "和" + data[j]);
                t = data[j];
                data[j] = data[i];
                data[i] = t;
                System.out.println(java.util.Arrays.toString(data));
            }
        }
        //最后將基準(zhǔn)位與i和j相等位置的數(shù)字交換 左右哨兵相遇
        System.out.println("基準(zhǔn)位" + temp + "和i、j相遇的位置" + data[i] + "交換");
        data[low] = data[i];
        data[i] = temp;
        System.out.println(java.util.Arrays.toString(data));

        //此時(shí)基準(zhǔn)數(shù)左邊都比基準(zhǔn)數(shù)小，右邊都比基準(zhǔn)數(shù)大，故而基準(zhǔn)數(shù)位置不變，基準(zhǔn)數(shù)左右兩邊重新進(jìn)行快排
        //遞歸調(diào)用左半數(shù)組
        quickSort(data, low, j - 1);
        //遞歸調(diào)用右半數(shù)組
        quickSort(data, j + 1, high);
    }
}

快速排序的特點(diǎn)及性能
快速排序是在冒泡排序的基礎(chǔ)上改進(jìn)而來的，冒泡排序每次只能交換相鄰的兩個(gè)元素，而快速排序是跳躍式的交換，交換的距離很大，因此總的比較和交換次數(shù)少了很多，速度也快了不少。

但是快速排序在最壞情況下的時(shí)間復(fù)雜度和冒泡排序一樣，是 O(n2)，實(shí)際上每次比較都需要交換，但是這種情況并不常見。我們可以思考一下如果每次比較都需要交換，那么數(shù)列的平均時(shí)間復(fù)雜度是 O(nlogn)，事實(shí)上在大多數(shù)時(shí)候，排序的速度要快于這個(gè)平均時(shí)間復(fù)雜度。這種算法實(shí)際上是一種分治法思想，也就是分而治之，把問題分為一個(gè)個(gè)的小部分來分別解決，再把結(jié)果組合起來。

快速排序只是使用數(shù)組原本的空間進(jìn)行排序，所以所占用的空間應(yīng)該是常量級的，但是由于每次劃分之后是遞歸調(diào)用，所以遞歸調(diào)用在運(yùn)行的過程中會消耗一定的空間，在一般情況下的空間復(fù)雜度為 O(logn)，在最差的情況下，若每次只完成了一個(gè)元素，那么空間復(fù)雜度為 O(n)。所以我們一般認(rèn)為快速排序的空間復(fù)雜度為 O(logn)。

快速排序是一個(gè)不穩(wěn)定的算法，在經(jīng)過排序之后，可能會對相同值的元素的相對位置造成改變。

快速排序基本上被認(rèn)為是相同數(shù)量級的所有排序算法中，平均性能最好的。文章來源地址http://www.zghlxwxcb.cn/news/detail-640155.html

到了這里，關(guān)于快速排序算法詳解（原理，時(shí)間復(fù)雜度，實(shí)現(xiàn)代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！