一、快速排序的遞歸探尋

1.思路

左斷開結(jié)果與右斷開結(jié)果加上突兀根如何實(shí)現(xiàn)上一層的結(jié)果：

左斷開有序+右斷開有序加突兀根實(shí)現(xiàn)它比左部分都大、它比右部分都小就可以實(shí)現(xiàn)上一層的有序

2.書寫

書寫時(shí)是突兀根先實(shí)現(xiàn)再遞歸實(shí)現(xiàn)左右斷開結(jié)果：

書寫時(shí)反著來先實(shí)現(xiàn)突兀根一個(gè)節(jié)點(diǎn)左邊都比都比它小、右邊都比它大，再用遞歸實(shí)現(xiàn)它斷開的左右有序結(jié)果

3.搭建

突兀根從底層向上的回搭搭建二叉樹：

3.1設(shè)計(jì)過掉不符情況（在最底層時(shí)）

• if(array == null) return， 沒有元素不用排，下面是有元素
• if(strat == end) return，只有一個(gè)元素不用排，下面是多個(gè)元素
• if(strat > end) return，排不了不要排的，之后下面是符合正常情況的多個(gè)元素 

3.2查驗(yàn)?zāi)軐?shí)現(xiàn)基礎(chǔ)結(jié)果（在最底層往上點(diǎn)時(shí)）

當(dāng)突兀根來到倒數(shù)第二層，當(dāng)共有兩個(gè)元素下突兀根去作為在上層的會(huì)去操作實(shí)現(xiàn)上層與下兩層結(jié)果的表示連接時(shí)，左邊、右邊都是有序的結(jié)果，要實(shí)現(xiàn)它這層的有序結(jié)果要突兀根去操作實(shí)現(xiàn)為它的值比左邊的都大、比右邊的都小，操作具體實(shí)現(xiàn)為與1節(jié)點(diǎn)的值進(jìn)行交換完成突兀根的實(shí)現(xiàn)操作，實(shí)現(xiàn)了突兀根所在的上層結(jié)果與下層左右兩斷開結(jié)果的連接表示，說明突兀根的實(shí)現(xiàn)操作在底層確實(shí)是能完成基礎(chǔ)排序的

3.3跳轉(zhuǎn)結(jié)果繼續(xù)往上回搭

4.實(shí)質(zhì)

用二叉樹遞歸實(shí)現(xiàn)排序?qū)嵸|(zhì)上還是確定元素大小排在的數(shù)組位置遞歸完一個(gè)個(gè)來排的：

它排的位置左邊都比它小、右邊都比它大，它排的位置就是它在數(shù)組中排的大小位置，同時(shí)也確定著其它元素的相對大小排位位置，所以最后一層元素不去找基準(zhǔn)排位置也是相對已確定下來的不用去排，所以if(start == end)return的

二、快速排序的基準(zhǔn)排序

待排序元素將其所在的待排序區(qū)域調(diào)整劃分成以它為基準(zhǔn)值左邊都比它小、右邊都比它大的兩部分，并將它基準(zhǔn)值放入兩部分的中間就完成了此元素的排序

1.雙路雙向交換鋪（Hoare法）

1.1原理

要去排的元素基準(zhǔn)值在待排序區(qū)域里面任意取好后，在待排序區(qū)域左右兩端往內(nèi)相遇鋪路，右端往內(nèi)鋪遇小不符等停，左端往內(nèi)鋪遇大換過去交換，直至路頭遇相等，此時(shí)路頭位置即基準(zhǔn)元素大小排在的位置，最后將基準(zhǔn)元素交換過去就完成了此元素的排序

1.2實(shí)現(xiàn)

private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap(array, i, j);
        }
        swap(array, i, left);
        return i;
    }

1.2.1>=

遇到與基準(zhǔn)值相等大小的元素時(shí)直接作為可行的路過掉的因?yàn)?strong>與基準(zhǔn)值相等大小的元素到最后排序在此作為基準(zhǔn)元素左右兩邊都是可以的，所以此時(shí)排放在基準(zhǔn)的左右兩路最后成兩部分都是可以的

1.2.2先右再左

基準(zhǔn)為路的相遇點(diǎn)，要設(shè)置在屬于左路因?yàn)樽詈蠡鶞?zhǔn)交換放到相遇點(diǎn)，基準(zhǔn)值放到相遇點(diǎn)進(jìn)去排序，相遇點(diǎn)的值會(huì)交換放到第一個(gè)位置即基準(zhǔn)值的左邊需要是左路的部分，所以每輪的鋪路都是先進(jìn)行右路的鋪完到左邊停再進(jìn)行左路的鋪

2.雙路雙向覆蓋鋪（挖坑法）

2.1原理

要去排的元素基準(zhǔn)值在待排序區(qū)域內(nèi)任意取好并挖成坑，從左右端先左或右都行往同向內(nèi)互相埋坑時(shí)又挖坑地推坑，推坑時(shí)始終是一端路停在坑位等著另一端路往內(nèi)鋪路挖到坑填上，所以左右路兩端相遇時(shí)一定遇在坑位，此位置就是基準(zhǔn)元素大小排序的位置排好

2.2實(shí)現(xiàn)

private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] <= pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        return i;
    }

3.雙路單向交換鋪（前后指針法）

3.1原理

要去排序的基準(zhǔn)元素在待排序區(qū)間任意選好后，定義prev與cur兩前后指針，在排序區(qū)間的一端開始同向往另一端通過前后交換動(dòng)態(tài)維護(hù)prev及之前的區(qū)間為小路、cur及到prev之前的區(qū)間為大路，這樣當(dāng)cur遍歷完排序區(qū)間時(shí)，數(shù)組就被分好了小路與大路兩部分，再將基準(zhǔn)元素交換放到prev指針位置處，一個(gè)基準(zhǔn)元素就在待排序區(qū)間排好了

3.2實(shí)現(xiàn)

private static int partition(int[] array, int left, int right) {
    int prev = left ;
    int cur = left+1;
    while (cur <= right) {
        if(array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(array,cur,prev);
        }
        cur++;
    }
    swap(array,prev,left);
    return prev;
 }

三、快速排序的復(fù)雜度

基準(zhǔn)排序的特點(diǎn)

• 元素的直接位置排好也排好著其它元素的間接位置排好、減少著其它元素剩下的需要排的量
• 每一個(gè)節(jié)點(diǎn)的出現(xiàn)，就是其完成它所在待排區(qū)域的基準(zhǔn)排位標(biāo)志 

1.時(shí)間復(fù)雜度

遞歸的調(diào)用語句算的是調(diào)用里面執(zhí)行的內(nèi)容(調(diào)用本身不算)，每次調(diào)用里面的常量次數(shù)執(zhí)行語句不算(因?yàn)槌顺Ａ砍Ａ靠珊雎缘?，只算里面的找調(diào)基準(zhǔn)排的非常量級(jí)的時(shí)間復(fù)雜度，算時(shí)間復(fù)雜度時(shí)就一層層地算每層里面所有遞歸調(diào)用的時(shí)間和：

1.1完全順序逆序

1.1.1結(jié)構(gòu)影響

當(dāng)元素完全順序或完全逆序排時(shí)，其呈現(xiàn)的二叉樹結(jié)構(gòu)為單分支的二叉樹：

• 一層層下來每層里面只劃分出了一個(gè)的遞歸調(diào)用，它這樣排能間接排出不用去排的元素只有一個(gè)(即只有一個(gè)葉子節(jié)點(diǎn)的元素)

1.1.2時(shí)間

最開始第一層時(shí)間是n-1，再下層一個(gè)元素已經(jīng)排好了時(shí)間是n-2，到最后一層時(shí)最后一個(gè)元素被間接排好遞歸調(diào)用函數(shù)里面是直接return的，所以一共有n層，n-1層要去算時(shí)間，從上往下每層的時(shí)間從n-1減到1的等差數(shù)列和，最后大O算成的時(shí)間復(fù)雜度為O(n^2)，實(shí)際上的時(shí)間會(huì)比n^2少

1.2完全二叉樹序

1.2.1結(jié)構(gòu)影響

當(dāng)數(shù)組呈完全二叉樹排列時(shí)：

• 每個(gè)節(jié)點(diǎn)排時(shí)都有間接最大地去排著其它元素的位置，一層層下來在每層里剩下區(qū)域會(huì)越來越多地被劃分著去排的，在一層中將會(huì)去完成更多的在區(qū)間中的排序，到最后一層能間接排出不用去排的元素會(huì)有很多
• 一個(gè)區(qū)間里，元素去基準(zhǔn)排劃分的次數(shù)固定是元素個(gè)數(shù)少1的，劃分成更多的區(qū)間里去排，排序本身就會(huì)減這么區(qū)間多個(gè)的次數(shù)完成

1.2.2時(shí)間

因?yàn)?strong>每一層往下已排好的元素越來越多，每一層中所有基準(zhǔn)區(qū)間總的去排的次數(shù)會(huì)越來越少，到最后一層里會(huì)有許多通過間接排就排好的元素不需要去排的，但大O算時(shí)的最后結(jié)果是偏大地算為每層所有找基準(zhǔn)排的時(shí)間為固定的n，然后樹的高度為log(n)，時(shí)間復(fù)雜度為O(n*log(n))，實(shí)際上的時(shí)間會(huì)比它少很多（根節(jié)點(diǎn)高度視為0的）

2.空間復(fù)雜度

因?yàn)檫f歸調(diào)用的?？臻g是動(dòng)態(tài)復(fù)用的，所以空間復(fù)雜度為遞歸樹的最大高度下算每層開辟的空間，因?yàn)檫@里每層遞歸函數(shù)里面開辟的空間是常量級(jí)的，所以大O算排序遞歸的空間復(fù)雜度就為遞歸調(diào)用棧的深度即二叉樹的高度：

• 當(dāng)數(shù)組完全順序或逆序時(shí)，二叉樹的高度為n-1,空間復(fù)雜度為O(n)
• 當(dāng)數(shù)組呈完全二叉樹排列時(shí)，二叉樹的高度為log(n)，空間復(fù)雜度為O(log(n))

3.優(yōu)化

二叉樹每層分支得越多裝得越滿：

• 每個(gè)元素節(jié)點(diǎn)都會(huì)去間接排其它元素的兩部分位置、更多的在區(qū)間的排序減的次數(shù)會(huì)更多、以層單位去算時(shí)間的層的量會(huì)更少、從上往下已排出剩下的待排序元素會(huì)越來越少很多、最后通過間接排出位置不用去排的元素就會(huì)更多，時(shí)間復(fù)雜度會(huì)更低
• 二叉樹的高度更小下，空間復(fù)雜度也會(huì)更低

3.1三數(shù)取中

在每個(gè)待排序區(qū)間雖然是可以任意取元素作基準(zhǔn)，但我們盡量取大小排在中間的元素使生成的樹分支更多樹更矮時(shí)間復(fù)雜度與空間復(fù)雜度都更低，我們采用三數(shù)取中法，即得到待排序區(qū)間后，在區(qū)間的首中尾的三個(gè)數(shù)比較下拿更小值更有可能得使得取的基準(zhǔn)值大小更偏中一點(diǎn)

3.2插入排序

3.2.1棧溢出原因

當(dāng)二叉樹經(jīng)上層已排好序節(jié)點(diǎn)能確定往下再分更多的更小的待排序區(qū)間去排序時(shí)，在二叉樹下幾層會(huì)分出很多的待排序子區(qū)間去排序，除了最底層的不需要去排序，其它在上層的每個(gè)區(qū)間的一次排序函數(shù)里都會(huì)執(zhí)行到再調(diào)用下層的兩個(gè)遞歸，在此時(shí)由于待排序子區(qū)間被分的特別多，會(huì)連續(xù)調(diào)用特別多的函數(shù)，一時(shí)間開辟特別多的函數(shù)棧幀，很有可能會(huì)造成棧溢出

3.2.2利與弊

因此在最后幾層的許多待排序子區(qū)間去排序時(shí)，我們可以直接在倒數(shù)的上幾層中就開始截?cái)?/strong>，不再往下通過分更多的子區(qū)間去基準(zhǔn)排序了，直接在這一層將待排序區(qū)域用插入排序直接排好，因?yàn)?strong>經(jīng)過上層的有很多元素已經(jīng)排好了位置，剩下的待排序元素也是間接地比較有序的，用插入排序也可以高效地完成，就不用去開辟下層大量聚集的函數(shù)棧幀避免了棧溢出，降低了開辟空間的成本

但是由于快速排序原本最后一層的元素通過上層元素的排好序全部可以間接地不用去排直接排好的，改成了插入排序后時(shí)間復(fù)雜度可能會(huì)比原來的純快速排序更高了

總結(jié)

到此這篇關(guān)于Java算法之快速排序的文章就介紹到這了,更多相關(guān)java算法快速排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論