步丶丶 2016-07-23 07:26 采纳率: 0%
浏览 1069

[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条回答 默认 最新

  • threenewbee 2016-07-23 14:58
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题