Quick Sort Back

Overview

  • 快速排序: 分治思想(Divide, Conquer and Combination)
  • Divide: pivot(可隨機選定)
  • Conquer: 直到只有一個的時候合併
  • Combination: None
  • 时间复杂度:
    • (最好平均情況)
    • (最壞情況)
  • 空間複雜度:
  • 稳定性: 不稳定
  • 适用情况: 数据多的且無序
  • 最壞情況下的比較次數:

Example

Code

void QUICKSORT(int A[], int p, int q)
{
    if (p < q)
    {
        int m = PARTITION(A, p, q);
        QUICKSORT(A, p, m - 1);
        QUICKSORT(A, m + 1, q);
    }
}

int PARTITION(int A[], int p, int q)
{
    int x = A[q];        //pivot
    int i = p - 1;
    for (int j = p; j <= q - 1; j++)
    {    
        count++;
        if (A[j] <= x)
        {
            i++;
            exchange(A, i, j);
        }
    }
    exchange(A, i + 1, q);
    return i + 1;
}

results matching ""

    No results matching ""