排序——快速排序

快速排序

基本思想

• 任取一個元素 (如第一個) 為中心
• 所有比它小的元素一律前放，比它大的元素一律後放，形成左右兩個子表；
• 對各子表重新選擇中心元素并依此規則調整，直到每個子表的元素隻剩一個

算法實作

int Partition(SqList &L, int low, int high){
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while(low < high){
        while(low < high && L.r[high].key >= pivotkey)
            --high;  // 從右向左搜尋
        L.r[low] = L.r[high];
        while(low < high && L.r[low].key <= pivotkey)
            ++low;  // 從左向右搜尋
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}

void QSort(SqList &L, int low, int high){
     // 對記錄序列L[low..high]進行快速排序
    if(low < high){
        // 長度大于1
        pivotkey = Partition(L, low, high);  // 對 L[low..high] 進行一次劃分
        QSort(L, low, pivotloc-1);  // 對低子表遞歸排序，pivotloc是樞軸位置
        QSort(L, pivotloc+1, high); // 對高子表遞歸排序
    }
}

// 第一次調用函數 Qsort 時，待排序記錄序列的上、下界分别為 1 和 L.length。
void QuickSort( SqList & L) {
    // 對順序表進行快速排序
    QSort(L.r, 1, L.length);
}           

算法分析

• 時間複雜度：O(n^2)
  • 最好： O(n log2n )
  • 最壞：O(n^2)
  • 平均：O(nlogn)
• 空間複雜度：O(n)
  • O（log2n）—遞歸要用到棧空間
  • 最壞情況下，遞歸樹的高度為O(n)
• 穩定性：不穩定