快速排序及其分析

Gavin-book 2011-10-03

展開全文

前言

快速排序的平均情況下是O(nlogn)，但是一般都比其他運行時間為O(nlogn)的算法都要快，因為它隱藏的常數(shù)因子比較小，但是在最壞情況之下，快速排序的運行時間是O(n²)。

快速排序過程

快速排序采用的思想是分治思想，就像合并排序算法的思想一樣，合并排序算法是從數(shù)組的中間開始分治，直到分為N個分組，最后分別合并N個分組的解。如下圖，有原始數(shù)組A = {1, 3, 4, 5, 7, 2, 6, 8, 0}

快速排序是找出一個元素（理論上可以隨便找一個）作為基準(zhǔn)(pivot),然后對數(shù)組進行分區(qū)操作,使基準(zhǔn)左邊元素的值都不大于基準(zhǔn)值,基準(zhǔn)右邊的元素值都不小于基準(zhǔn)值，如此作為基準(zhǔn)的元素調(diào)整到排序后的正確位置。遞歸快速排序，將其他n-1個元素也調(diào)整到排序后的正確位置。最后每個元素都是在排序后的正確位置，排序完成。所以快速排序算法的核心算法是分區(qū)操作，即如何調(diào)整基準(zhǔn)的位置以及調(diào)整返回基準(zhǔn)的最終位置以便分治遞歸。

基準(zhǔn)

基準(zhǔn)的挑選會影響到算法的性能，一般情況將序列的第一個元素作為基準(zhǔn)。

分區(qū)算法

設(shè)兩個指針left和right，一個從左往右掃描，一個從右往左掃描；對于左指針，如果左指針?biāo)傅脑氐闹敌∮诨蛘叩扔诨鶞?zhǔn)值，那么指針往右移一位，如果大于基準(zhǔn)值，則和基準(zhǔn)值交換；同理，對于右指針，如果右指針?biāo)傅脑氐闹荡笥诨蛘叩扔诨鶞?zhǔn)值，那么指針往左移一位，如果小于基準(zhǔn)值，則和基準(zhǔn)值交換。代碼如下：




view plaincopy to clipboardprint?


    int Partition(int A[], int p, int r)  
    {  
        int privot = A[p];  //基準(zhǔn)   
        // 設(shè)兩個指針   
        int left = p;   //從左往右掃描   
        int right = r;  //從右往左掃描   
          
        while (right > left)  
        {  
            while (right > left && A[right] >= privot)    
            {  
                right--;  
            }  
      
            A[left] = A[right];  
      
            while (right > left && A[left] <= privot)  
            {  
                left++;  
            }  
      
            A[right] = A[left];  
        }  
      
        A[left] = privot;  
        return left;  
    }  
      
    void QuickSort(int A[], int p, int r)  
    {  
        int pivot;  
      
        if (r > p)  
        {  
            pivot = Partition(A, p, r);  
            QuickSort(A, p, pivot-1);  
            QuickSort(A, pivot+1, r);  
        }  
    }

性能分析

最好情況

每次基準(zhǔn)的最終位置都是在數(shù)組中間位置，從而使規(guī)模為N的問題分為2個規(guī)模為N/2的問題，即T(n) = 2T(n/2) + Θ(n)，用遞歸樹分析或者主定理得到時間T(n) = O(nlogn)。

最壞情況

每次基準(zhǔn)的最終位置都是第一個位置，從而規(guī)模為N的問題分為一個規(guī)模為N-1的問題，即T(n) = T(n-1) + Θ(n),用遞歸樹分析可得運行時間T(n) = O(n²)。

平均情況

假設(shè)規(guī)模為N的問題分為一個規(guī)模為9/10N的問題和規(guī)模為1/10N的問題，即T(n) = T(9n/10) + T(n/10) + Θ(n),用遞歸樹分析可得T(n) = O(nlogn)，而且比分區(qū)9:1要更平均（也就是情況更好）的概率為80%，所以在絕大部分情況下快速排序算法的運行時間為O(nlogn)。