成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

快速排序分治算法解析

FrancisSoung / 2806人閱讀

摘要：快速排序分治算法解析聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處快速排序分治算法思路復(fù)雜度分析由于切分算法性能不穩(wěn)定，快排最差時間復(fù)雜度為，平均時間復(fù)雜度為，空間復(fù)雜度為快速排序劃分算法需要升序排序條件下，對于一個軸點(diǎn)，一次切分操作完成后保

快速排序分治算法解析 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處：https://segmentfault.com/u/yzwall

1.快速排序-分治算法思路


復(fù)雜度分析：由于切分算法性能不穩(wěn)定，快排最差時間復(fù)雜度為$O(n ^ 2)$，平均時間復(fù)雜度為$O(nlog(n))$，空間復(fù)雜度為$O(1)$；

2. 快速排序-劃分算法(Partition)

需要升序排序條件下，對于一個軸點(diǎn)$pivot$，一次切分操作完成后保證：

$<= pivot$的都在$pivot$左邊，$>= pivot$的都在$pivot$右邊

反之，在降序排序條件下，保證

$>= pivot的都在$pivot$左邊, $<= pivot$的都在$pivot$右邊
2.1 快速排序不穩(wěn)定性

快速排序的不穩(wěn)定性在于軸點(diǎn)$pivot$的選擇上，如果$pivot$選擇數(shù)組一邊，排序退化為冒泡排序($O(n^2)$)，因此$pivot$盡量選擇均勻，通常進(jìn)行二者取中：
$$
pivot = nums[start + (end - start) / 2]
$$

2.2 leftIndex <= rightIndex辨析 
while (leftIndex <= rightIndex) {
    // 在左側(cè)尋找不合法數(shù)， A[leftIndex] < pivot，保證切分均勻
    while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
        ...
    }
    
    // 在右側(cè)尋找不合法數(shù)， A[rightIndex] > pivot，保證切分均勻
    while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
        ...
    }
    
    // 找到不合法數(shù)，將不合法數(shù)放入對應(yīng)區(qū)間內(nèi)
    if (leftIndex <= rightIndex) {
        ...
    }
    quickSort(A, start, rightIndex);
    quickSort(A, leftIndex, end);
}

leftIndex <= rightIndex操作保證分治快排時，分治子數(shù)組沒有重疊部分，因此如果將
leftIndex <= rightIndex改成leftIndex < rightIndex，遞歸找不到出口，造成StackOverFlow
當(dāng)劃分操作完成后，必然有：
$$
rightIndex < leftIndexnums
$$

$$
nums[rightIndex] <= nums[leftIndex]
$$

2.3 保證$pivot$切分均勻 
// 在左側(cè)尋找不合法數(shù)， A[leftIndex] < pivot，保證切分均勻
while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
     leftIndex++;
}

// 在右側(cè)尋找不合法數(shù)， A[rightIndex] > pivot，保證切分均勻
while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
    rightIndex--;
}

$=pivot$的數(shù)在切分過程中可以放在$pivot$左右兩邊：為了防止當(dāng)$=pivot$在數(shù)組中大量出現(xiàn)時，如果嚴(yán)格保證$=pivot$的數(shù)在$pivot$某一側(cè)，會造成$pivot$選擇不均勻，因此必須保證$=pivot$的數(shù)字盡量在$pivot$兩側(cè)均勻分布，因此整體有序的判斷條件為A[leftIndex] < pivot和A[rightIndex] > pivot；

2. 快速排序-分治法遞歸實(shí)現(xiàn)代碼 
/**
 * http://www.lintcode.com/en/problem/sort-integers-ii/
 * 快速排序一個數(shù)組（升序）
 * @author yzwall
 */
class Solution {
    
    public void sortIntegers2(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[]A, int start, int end) {
        //　遞歸出口　單元素不做排序
        if (start >= end) {
            return;
        }
        
        // 切分操作時間復(fù)雜度O(n)，空間復(fù)雜度O(1)
        int leftIndex = start;
        int rightIndex = end;
        int pivot = A[start + (end - start) / 2];
        
        // leftIndex <= rightIndex, < 導(dǎo)致棧溢出
        while (leftIndex <= rightIndex) {
            // 在左側(cè)尋找不合法數(shù)， A[leftIndex] < pivot，保證切分均勻
            while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
                leftIndex++;
            }
            
            // 在右側(cè)尋找不合法數(shù)， A[rightIndex] > pivot，保證切分均勻
            while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
                rightIndex--;
            }
            
            // 找到不合法數(shù)，將不合法數(shù)放入對應(yīng)區(qū)間內(nèi)
            if (leftIndex <= rightIndex) {
                int temp = A[leftIndex];
                A[leftIndex] = A[rightIndex];
                A[rightIndex] = temp;
                // 繼續(xù)查找不合法數(shù)
                leftIndex++;
                rightIndex--;
            }
        }
        
        /**
         * 跳出循環(huán)，leftIndex與rightIndex已互換位置
         * 分治時間復(fù)雜度O(logn), 空間復(fù)雜度O(1)
         */
        quickSort(A, start, rightIndex);
        quickSort(A, leftIndex, end);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70047.html

相關(guān)文章

  • 算法學(xué)習(xí)筆記：排序算法(二)

    摘要：上一篇中已經(jīng)介紹了幾個簡單的排序算法，這一篇文章我將繼續(xù)向大家介紹排序算法相關(guān)的內(nèi)容，本篇的會介紹希爾排序快速排序歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。 上一篇中已經(jīng)介紹了幾個簡單的排序算法，這一篇文章我將繼續(xù)向大家介紹排序算法相關(guān)的內(nèi)容，本篇的會介紹希爾排序、快速排序、歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。 希爾排序...

    William_Sang 評論0 收藏0

  • js 排序算法之快速排序

    摘要：快速排序是一種劃分交換排序?？焖倥判蚧诿芭葸f歸分治。他在大數(shù)據(jù)情況下是最快的排序算法之一，平均事件復(fù)雜度很低而且前面的系數(shù)很小，在大量隨機(jī)輸入的情況下最壞情況出現(xiàn)的概率是極小的。 快速排序是一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法。 分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。...

    Eidesen 評論0 收藏0

  • 直擊架構(gòu)本質(zhì)：優(yōu)秀架構(gòu)師必須掌握的幾種架構(gòu)思維

    摘要：由于文章內(nèi)容較長，所以我把它分成兩篇小文章，在第一篇優(yōu)秀架構(gòu)師必須掌握的架構(gòu)思維中，我會先介紹抽象分層分治和演化這四種應(yīng)對復(fù)雜性的基本思維。另外，上面的算法是兩路歸并，也可以采用多路歸并，甚至是采用堆排序進(jìn)行優(yōu)化，但是總體分治思路沒有變化。 showImg(https://segmentfault.com/img/bVbeYpP?w=642&h=400); 介紹 架構(gòu)的本質(zhì)是管理復(fù)雜性...

    lijy91 評論0 收藏0

  • 直擊架構(gòu)本質(zhì)：優(yōu)秀架構(gòu)師必須掌握的幾種架構(gòu)思維

    摘要：由于文章內(nèi)容較長，所以我把它分成兩篇小文章，在第一篇優(yōu)秀架構(gòu)師必須掌握的架構(gòu)思維中，我會先介紹抽象分層分治和演化這四種應(yīng)對復(fù)雜性的基本思維。另外，上面的算法是兩路歸并，也可以采用多路歸并，甚至是采用堆排序進(jìn)行優(yōu)化，但是總體分治思路沒有變化。 showImg(https://segmentfault.com/img/bVbeYpP?w=642&h=400); 介紹 架構(gòu)的本質(zhì)是管理復(fù)雜性...

    fjcgreat 評論0 收藏0

發(fā)表評論

0條評論

FrancisSoung

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<