[PAT]c语言程序快速排序的代码看不懂,这片代码不像网上的快速排序代码啊。

在做PAT的是时候,用普通的快速排序,在评分后会出现运行超时。

而在网上找到的这种代码不会出现,但是看不懂代码是什么意思,还求前辈解释。

 #include <stdio.h>

#define MAXN 10
typedef float ElementType;

ElementType Median(ElementType A[], int N);

int main()
{
    ElementType A[MAXN];
    int N, i;

    scanf("%d", &N);
    for (i = 0; i<N; i++)
        scanf("%f", &A[i]);
    printf("%.2f\n", Median(A, N));
    return 0;
}

/*您的代码将被嵌在这里*/

void Swap(ElementType *a, ElementType *b) 
{
    ElementType temp = *a;
    *a = *b;
    *b = temp;
}

ElementType Median3(ElementType A[], int left, int right) 
{
    int Center = (left + right) / 2;
    if (A[left] > A[Center])
        Swap(&A[left], &A[Center]);
    if (A[left] > A[right])
        Swap(&A[left], &A[right]);
    if (A[Center] > A[right])
        Swap(&A[Center], &A[right]);
    Swap(&A[Center], &A[right - 1]);
    return A[right - 1];
}

void QSort(ElementType A[], int left, int right) 
{
    if (left >= right) return;
    ElementType Pivot = Median3(A, left, right);
    int i = left, j = right - 1;
    while (1) {
        while (A[++i] < Pivot) {}
        while (A[--j] > Pivot) {}
        if (i < j){
            Swap(&A[i], &A[j]);
        }
        else break;
    }
    Swap(&A[i], &A[right - 1]);
    QSort(A, left, i - 1);
    QSort(A, i + 1, right);
}

ElementType Median(ElementType A[], int N) 
{
    QSort(A, 0, N - 1);
    return A[N / 2];
}

1个回答

典型的快速排序代码,快速排序代码的特征,先将数据分区,然后移动成两堆,最后对两堆再递归调用快速排序。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!