一、快速排序的遞歸探尋

1.思路

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

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

2.書寫

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

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

3.搭建

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

3.1設計過掉不符情況（在最底層時）

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

3.2查驗能實現(xiàn)基礎結果（在最底層往上點時）

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

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

4.實質(zhì)

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

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

二、快速排序的基準排序

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

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

1.1原理

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

1.2實現(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>=

遇到與基準值相等大小的元素時直接作為可行的路過掉的因為與基準值相等大小的元素到最后排序在此作為基準元素左右兩邊都是可以的，所以此時排放在基準的左右兩路最后成兩部分都是可以的

1.2.2先右再左

基準為路的相遇點，要設置在屬于左路因為最后基準交換放到相遇點，基準值放到相遇點進去排序，相遇點的值會交換放到第一個位置即基準值的左邊需要是左路的部分，所以每輪的鋪路都是先進行右路的鋪完到左邊停再進行左路的鋪

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

2.1原理

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

2.2實現(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原理

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

3.2實現(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;
 }

三、快速排序的復雜度

基準排序的特點

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

1.時間復雜度

遞歸的調(diào)用語句算的是調(diào)用里面執(zhí)行的內(nèi)容(調(diào)用本身不算)，每次調(diào)用里面的常量次數(shù)執(zhí)行語句不算(因為乘常量常量可忽略的)，只算里面的找調(diào)基準排的非常量級的時間復雜度，算時間復雜度時就一層層地算每層里面所有遞歸調(diào)用的時間和：

1.1完全順序逆序

1.1.1結構影響

當元素完全順序或完全逆序排時，其呈現(xiàn)的二叉樹結構為單分支的二叉樹：

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

1.1.2時間

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

1.2完全二叉樹序

1.2.1結構影響

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

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

1.2.2時間

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

2.空間復雜度

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

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

3.優(yōu)化

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

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

3.1三數(shù)取中

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

3.2插入排序

3.2.1棧溢出原因

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

3.2.2利與弊

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

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

總結

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

最新評論