国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

快速排序分治算法解析

FrancisSoung / 2796人閱讀

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

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

文章均為本人技術筆記，轉載請注明出處：https://segmentfault.com/u/yzwall

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


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

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

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

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

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

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

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

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

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

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

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

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

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

2. 快速排序-分治法遞歸實現代碼 
/**
 * http://www.lintcode.com/en/problem/sort-integers-ii/
 * 快速排序一個數組（升序）
 * @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;
        }
        
        // 切分操作時間復雜度O(n)，空間復雜度O(1)
        int leftIndex = start;
        int rightIndex = end;
        int pivot = A[start + (end - start) / 2];
        
        // leftIndex <= rightIndex, < 導致棧溢出
        while (leftIndex <= rightIndex) {
            // 在左側尋找不合法數， A[leftIndex] < pivot，保證切分均勻
            while (leftIndex <= rightIndex && A[leftIndex] < pivot) {
                leftIndex++;
            }
            
            // 在右側尋找不合法數， A[rightIndex] > pivot，保證切分均勻
            while (leftIndex <= rightIndex && A[rightIndex] > pivot) {
                rightIndex--;
            }
            
            // 找到不合法數，將不合法數放入對應區間內
            if (leftIndex <= rightIndex) {
                int temp = A[leftIndex];
                A[leftIndex] = A[rightIndex];
                A[rightIndex] = temp;
                // 繼續查找不合法數
                leftIndex++;
                rightIndex--;
            }
        }
        
        /**
         * 跳出循環，leftIndex與rightIndex已互換位置
         * 分治時間復雜度O(logn), 空間復雜度O(1)
         */
        quickSort(A, start, rightIndex);
        quickSort(A, leftIndex, end);
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70047.html

相關文章

  • 算法學習筆記：排序算法(二)

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

    William_Sang 評論0 收藏0

  • js 排序算法之快速排序

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

    Eidesen 評論0 收藏0

  • 直擊架構本質：優秀架構師必須掌握的幾種架構思維

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

    lijy91 評論0 收藏0

  • 直擊架構本質：優秀架構師必須掌握的幾種架構思維

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

    fjcgreat 評論0 收藏0

發表評論

0條評論

FrancisSoung

男|高級講師

TA的文章

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