[演算法] 快速排序法(Quick Sort)
YehYeh\'s Notepad yehyeh@gmail.com 

[演算法(Algorithm)] 快速排序法(Quick Sort)

  • 快速排序法採用分割與征服(Divide and Conquer)策略
    • 將問題分解成較小的子問題,用相同的解決程序一一解決後,再將子問題的結果整合成原問題的答案
  • 快速排序法是最快的排序法之一
    • 依問題的類型而定
  • 快速排序作法:
    • 選定一個基準值(Pivot)
    • 將比基準值(Pivot)小的數值移到基準值左邊,形成左子串列
    • 將比基準值(Pivot)大的數值移到基準值右邊,形成右子串列
    • 分別對左子串列右子串列作上述三個步驟 遞迴(Recursive)
      • 直到左子串列或右子串列只剩一個數值或沒有數值
  • 分割(Partition):將數列依基準值分成三部份(快速排序作法中,第2,3步驟)
    1. 左子數列:比基準值小的數值
    2. 中子數列:基準值
    3. 右子數列:比基準值大的數值
  • 快速排序法的效率和基準值(Pivot)的選擇息息相關
    • 每次選擇的基準值(Pivot)愈接近數列的平均值或中位數愈好
  • 基準值(Pivot)的選擇
    • 固定位置:第一個數值、最後一個數值、中間的數值
      • 基準值可能選到最小或最大的數值,使左、右子串列其中的一個大小為0
    • 亂數選擇:
      • 基準值可能選到最小或最大的數值,使左、右子串列其中的一個大小為0
    • 中位數:
      • 數值依大小排列,位置在最中間的數值
      • 不容易計算,增加複雜度
    • 三選一:第一個、最後一個、中間的數值的中位數
  • 時間複雜度(Time Complexity)
    • Best Case:Ο(n log n)
      • 第一個基準值的位置剛好是中位數,將資料均分成二等份
    • Worst Case:Ο(n2) 
      • 當資料的順序恰好為由大到小或由小到大時
      • 有分割跟沒分割一樣
    • Average Case:Ο(n log n)
  • 空間複雜度(Space Complexity):Ο(log n) ~ Ο(n)
    • 快速排序法的空間複雜度依實作方式而不同
    • 遞迴呼叫需要額外的堆疊空間 因遞迴的深度而異
    • Best Case: Ο(log n)
      • 遞迴呼叫的深度為log n
    • Worst Case: Ο(n)
      • 遞迴呼叫的深度為n-1
  • 穩定性(Stable/Unstable):不穩定(Unstable)
  • Demo:
  • 演算法
    /**
     * 固定第一個數值為基準值(Pivot)
     */ 
    var swap = function(data, i, j){ 
        var tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    };
        
    // 以data[left]為Pivot,left相當於最左邊第一個元素    
    var quickSort = function(data, left, right){    
        if(left < right){
            var i=left, j=right+1;
            while(true){
                // 向右找小於Pivot的數值的位置
                while(i+1 < data.length && data[++i] < data[left]); 
                
                // 向左找大於Pivot的數值的位置
                while(j-1 > -1 && data[--j] > data[left]);
                
                // 若i,j的位置交叉
                //     代表範圍內,Pivot右邊已無比Pivot小的數值
                //     代表範圍內,Pivot左邊已無比Pivot大的數值            
                if(i >= j)    
                    break;
                
                // 將比Pivot大的數值換到右邊,比Pivot小的數值換到左邊
                swap(data, i, j);           
            }
            swap(data, left, j);    // 將Pivot移到中間
            quickSort(data, left, j-1);    // 對左子串列進行快速排序
            quickSort(data, j+1, right);   // 對右子串列進行快速排序
        }
    };
    
    /**
     * 固定最後一個數值為基準值(Pivot)
     */ 
    var swap = function(data, i, j){ 
        var tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    };
    
    /**
     * 將比Pivot小的數值右移,比Pivot大的數值左移
     * 最後回傳Pivot的位置 
     */
    var partition = function(data, left, right){
        var i = left - 1;
        for(var j = left; j < right; j++){
            if(data[j] < data[right]){   // data[right]為Pivot
                i++;                     // 計數有幾個比Pivot小的數值
                swap(data, i, j);
            }
        }
        swap(data, i+1, right);          // 將Pivot移到中間
        return i+1;
    };
    
    var quickSort = function(data, left, right){
        if(left < right){
            var pivotLocation = partition(data, left, right);
            quickSort(data, left, pivotLocation-1);
            quickSort(data, pivotLocation+1, right);
        }
    };